1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
public class OpenAddressingHashTable extends HashTable {
private class Element {
int value;
Element(int o) { // only allow integers in this class for similicy of the
this.value = o; // hashing algorithm, real hash tables need to be generic
}
@Override
public int hashCode() {
return value % 13;
}
public String toString() {
return "Element " + value + " with hash " + hashCode();
}
}
// ************************************************************************
// Hash tables have a problem. What to do when there's a hash collision?
// (When two different elements have the same hash) some languages make
// each hash element an arraylist so it can have multiple elements. But
// eventually it will become more and more linear (which defeats the
// purpose of a hash table). These solutions probe another space to put
// the element. This needs to be done in a consistent manner. Removing
// elements it more complicated unfortunately.
// ************************************************************************
private interface Probing {
int increment(int j, int k);
}
// ************************************************************************
// The simplest algorithm for probing the next location, simply find the
// next space. This isn't very good since it leads to clustering
// ************************************************************************
public static class LinearProbing implements Probing {
public int increment(int j, int k) {
return (j + 1);
}
}
// ************************************************************************
// Find the next space in a non-linear way. Therefore each element will
// have its collisions put in a different relative location. This stops
// clustering, but it means that the hash table length needs to be a prime
// number
// ************************************************************************
public static class QuadraticProbing implements Probing {
public int increment(int j, int k) {
if (j == 0) {
return j;
}
System.out.println("j = " + j + "; k = " + k + "; inc(j, k) = " + ((2 * j) - 1));
return ((2 * j) - 1);
}
}
// ************************************************************************
// Another way of probing is to use another hashing algorithm
// ************************************************************************
public static class DoubleHashing implements Probing {
public int increment(int j, int k) {
if (j == 0) {
return j;
}
System.out.println("j = " + j + "; k = " + k + "; inc(j, k) = " + hash2(k));
return hash2(k);
}
private int hash2(int k) {
return 5 - (k % 5);
}
}
private Element[] elements;
Probing probingAlgo;
<T extends Probing> OpenAddressingHashTable(T probingAlgo) {
elements = new Element[capacity];
this.probingAlgo = probingAlgo;
}
public boolean add(int o) {
Element e = new Element(o);
int finalIndex = resolveCollision(e, 0, e.hashCode());
size++;
return true;
}
public boolean contains(int o) {
return true; //TODO
}
public boolean remove(int o) {
return true; //TODO
}
private int resolveCollision(Element e, int numMisses, int index) {
if (elements[index] == null) {
elements[index] = e;
System.out.println(String.format("Placed %d at index %d.", e.value, index));
return index;
} else {
int incr = (index + probingAlgo.increment(numMisses, e.value)) % capacity;
if (index != incr) {
System.out.println(String.format("Couldn't place %d at index %d, trying index %d...", e.value, index, incr));
}
return resolveCollision(e, numMisses + 1, incr);
}
}
public String toString() {
String out = "";
for (int i = 0; i < capacity; i++) {
try {
out += String.format("%d = %d\n", i, elements[i].value);
} catch (NullPointerException e) {
out += String.format("%d = null\n", i);
}
}
return out;
}
public static void main(String[] args) {
OpenAddressingHashTable ht1 = new OpenAddressingHashTable(new LinearProbing());
ht1.add(8);
ht1.add(42);
ht1.add(29);
ht1.add(51);
ht1.add(47);
ht1.add(13);
ht1.add(34);
System.out.println(ht1);
System.out.println("\n\n");
OpenAddressingHashTable ht = new OpenAddressingHashTable(new QuadraticProbing());
ht.add(8);
ht.add(42);
ht.add(29);
ht.add(51);
ht.add(47);
ht.add(13);
ht.add(34);
System.out.println(ht);
System.out.println("\n\n");
OpenAddressingHashTable ht2 = new OpenAddressingHashTable(new DoubleHashing());
ht2.add(8);
ht2.add(42);
ht2.add(29);
ht2.add(51);
ht2.add(47);
ht2.add(13);
ht2.add(34);
System.out.println(ht2);
}
}
|
