-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBetterHashTable.java
More file actions
318 lines (270 loc) · 9.91 KB
/
BetterHashTable.java
File metadata and controls
318 lines (270 loc) · 9.91 KB
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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
package CommonUtils;
import CommonUtils.Interfaces.BetterHashTableInterface;
import java.awt.*;
import java.util.Objects;
/**
* Implements our {@link BetterHashTableInterface} and adds two constructors.
* <p>
* <b>251 students: You are explicitly forbidden from using java.util.Hashtable (including any subclass
* like HashMap) and any other java.util.* library EXCEPT java.util.Arrays and java.util.Objects.
* Write your own implementation of a hash table.</b>
*
* @implNote Implements a hash table using an array with initial capacity 8.
*
* @param <K> Type of key the hash table is holding
* @param <V> Type of value the hash table is holding
*/
public class BetterHashTable<K, V> implements BetterHashTableInterface<K, V> {
/**
* Initial size of hash table.
*/
private static final int INIT_CAPACITY = (1 << 4) + 3; // 16+3
/**
* Determines the maximum ratio of number of elements to array size.
* <p>
* If the number of elements stored is > LOAD_FACTOR, it should increase
* the capacity of the array according to INCREASE_FACTOR.
* <p>
* Our hash table will not decrease its size for the duration of its lifetime.
*/
private static final double LOAD_FACTOR = 0.75;
/**
* Determines how much to increase the array's capacity.
* <p>
* If the array needs to increase in size (see load factor), it should prefer to
* increase by the old capacity * INCREASE_FACTOR. If it cannot increase by
* that much (max int), it should increase by some small quantity (<100).
*/
private static final int INCREASE_FACTOR = 2;
/**
* "some small quantity (<100)"
*/
private static final int CAPACITY_INCREMENT = 1 << 5; // 32
/**
* Simple storage unit for our hash table
*/
private static class Node<K, V> {
final K key;
V value;
Node(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "Node{" + "key=" + key + ", value=" + value + '}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Node)) return false;
Node<?, ?> node = (Node<?, ?>) o;
return Objects.equals(key, node.key) && Objects.equals(value, node.value);
}
}
/**
* Default entry to use when marking a slot as deleted.
*
* <bold>251 students: When you remove an entry in the table, you cannot simply set it to null.
* Because we are using quadratic probing, there could be a "chain" of probing misses
* which would be disrupted if we just set the current node to null. Having a "deleted"
* default value allows us to continue successfully searching for any object whose hash
* matches the object we are deleting. It is up to you to figure out the best way to
* use this field, no further guidance will be given.</bold>
*/
private final Node<K, V> DELETED = new Node<>(null, null);
/**
* Array to store elements (according to the implementation
* note in the class header comment).
*/
Node<K, V>[] table;
private int size;
private int deleted;
/**
* Constructs the hash table with a default size
*
* <bold>251 Students: the syntax for this is a little weird, here is the easiest
* way to create a list of Node<K, V>:
* (Node<K, V>[]) new Node[capacity_here_if_you_need_it]
* </bold>
*/
@SuppressWarnings("unchecked")
public BetterHashTable() {
this(INIT_CAPACITY);
}
/**
* Constructor that initializes the hash table with an initial capacity
* @param initialCapacity initial table capacity
* @throws IllegalArgumentException if the initial capacity is negative
*/
@SuppressWarnings("unchecked")
public BetterHashTable(int initialCapacity) throws IllegalArgumentException {
if (initialCapacity < 0) throw new IllegalArgumentException();
this.table = (Node<K, V>[]) new Node[initialCapacity];
this.size = 0;
this.deleted = 0;
}
private static final double A = (Math.sqrt(5) - 1.0) / 2.0;
private static final double C1 = 0.5;
private static final double C2 = 0.5;
private int hash(K key) {
int k = Math.abs(Objects.hash(key));
return (int) Math.floor(((A * k) % 1) * table.length);
}
private void rehash() {
int newCapacity = table.length;
if (table.length <= Integer.MAX_VALUE / INCREASE_FACTOR)
newCapacity *= INCREASE_FACTOR;
else if (table.length <= Integer.MAX_VALUE - CAPACITY_INCREMENT)
newCapacity += CAPACITY_INCREMENT;
else throw new RuntimeException("Out of memory!");
Node<K, V>[] oldTable = this.table;
this.table = (Node<K, V>[]) new Node[newCapacity];
// this.size = 0;
for (Node<K, V> node : oldTable) {
if (node == null || node == DELETED) continue;
// insert(node.key, node.value);
int p = hash(node.key);
// Quadratic probing for the insertion index
for (int i = 0; i < table.length; i++) {
int k = (p + (int) (C1 * i + C2 * (i * i))) % table.length;
if (table[k] != null) continue;
table[k] = node;
break;
}
}
}
/**
* Places the item in the hash table. Passing key=null will not change the state of the table.
* Passing a key already in the table will modify the original entry in the table.
*
* @param key key to associate with the value
* @param value item to store in the hash table
*/
@Override
public void insert(K key, V value) {
if (key == null) return;
int p = hash(key);
// boolean exists = containsKey(key);
// Quadratic probing for the insertion index
for (int i = 0; i < table.length; i++) {
int k = (p + (int) (C1 * i + C2 * (i * i))) % table.length;
// Element doesn't exist
if (table[k] == null) {
table[k] = new Node<>(key, value);
this.size++;
// Rehash if load factor is above threshold
double loadFactor = (double) (this.size + this.deleted) / table.length;
if (loadFactor > LOAD_FACTOR) rehash();
return;
} else if (table[k] != null && table[k] != DELETED && table[k].key.equals(key)) {
// Element exists, update the old node to the new value
table[k].value = value;
return;
}
}
}
/**
* Removes the key, value pair associated with the given key
*
* @param key key/value to remove
*/
@Override
public void remove(K key) {
int p = hash(key);
// Quadratic probing for the element index
for (int i = 0; i < table.length; i++) {
int k = (p + (int) (C1 * i + C2 * (i * i))) % table.length;
if (table[k] == DELETED) continue;
if (table[k] == null) return;
if (!table[k].key.equals(key)) continue;
table[k] = DELETED;
this.size--;
this.deleted++;
return;
}
}
/**
* Retrieves a value based on the given key
*
* @param key key to search by
* @return value associated with the key, or <code>null</code> if it does not exist
*/
@Override
public V get(K key) {
int p = hash(key);
// Quadratic probing for the element index
for (int i = 0; i < table.length; i++) {
int k = (p + (int) (C1 * i + C2 * (i * i))) % table.length;
if (table[k] == DELETED) continue;
if (table[k] == null) return null;
if (!table[k].key.equals(key)) continue;
return table[k].value;
}
return null;
}
/**
* Returns <code>true</code> if this hash table contains the given key.
*
* @param key key to check for
* @return true iff the hash table contains a mapping for the specified key,
* as ultimately determined by the equals method
*/
@Override
public boolean containsKey(K key) {
int p = hash(key);
// Quadratic probing for the element index
for (int i = 0; i < table.length; i++) {
int k = (p + (int) (C1 * i + C2 * (i * i))) % table.length;
if (table[k] == DELETED) continue;
if (table[k] == null) return false;
if (!table[k].key.equals(key)) continue;
return true;
}
return false;
}
/**
* Empties the hash table.
*/
@Override
@SuppressWarnings("unchecked")
public void clear() {
for (int i = 0; i < table.length; i++) {
this.table[i] = null;
}
this.size = 0;
}
/**
* Returns the number of items in the hash table
*
* @return integer representing the number of elements in the hash table
*/
@Override
public int size() {
return this.size;
}
/**
* DO NOT MODIFY NOR IMPLEMENT THIS FUNCTION
*
* @param g graphics object to draw on
*/
@Override
public void draw(Graphics g) {
//DO NOT MODIFY NOR IMPLEMENT THIS FUNCTION
if(g != null) g.getColor();
//todo GRAPHICS DEVELOPER:: draw the hash table how we discussed
//251 STUDENTS:: YOU ARE NOT THE GRAPHICS DEVELOPER!
}
/**
* DO NOT MODIFY NOR IMPLEMENT THIS FUNCTION
*
* @param g graphics object to draw on
*/
@Override
public void visualize(Graphics g) {
//DO NOT MODIFY NOR IMPLEMENT THIS FUNCTION
if(g != null) g.getColor();
//todo GRAPHICS DEVELOPER:: visualization is to be time-based -- how we discussed
//251 STUDENTS:: YOU ARE NOT THE GRAPHICS DEVELOPER!
}
}