· 8 years ago · Jan 09, 2018, 07:30 PM
1package ci284.ass2.htable;
2
3//The complexity of the put function can be split into 3 different stages. These stages are: Comparing
4//the LoadFactor to the maxLoad, checking if the key exists and inserting the items.
5//An item will always have to be inserted, this can be represented as O1 because the insert time
6//of most hash tables is constant and does not change. This is the same for get because the time for the
7//search of data is the same, O1.
8//The best case will be where there is only one step to take and therefore we can just put the data inside.
9//Just like the get, if there is only one piece of data then it will only have one to sort through.
10//In the worst case scenario, it will take O(n) time where n is the size of the hash.
11//So it will take double the amount of time for a hash twice the size. For the get, it will also take O(n)
12//because if n is large than it has more to sort through as well as the put since looking for space in a larger table takes longer.
13//As the LoadFactor increase it decrease the amount of overhead space and in doing so will increase the cost
14//to look up the get and put functions. If you were to increase the LoadFactor to 1.0 the capacity would increase.
15//Because of this the amount of collisions would increase (When multiple keys both have the same hash).
16//Doing this would therefore increase the look up time even more since each key would have to be check individually.
17/**
18 * A HashTable with no deletions allowed. Duplicates overwrite the existing value. Values are of
19 * type V and keys are strings -- one extension is to adapt this class to use other types as keys.
20 *
21 * The underlying data is stored in the array `arr', and the actual values stored are pairs of
22 * (key, value). This is so that we can detect collisions in the hash function and look for the next
23 * location when necessary.
24 */
25
26import java.math.BigInteger;
27import java.util.ArrayList;
28import java.util.Arrays;
29import java.util.Collection;
30
31public class Hashtable<V> {
32
33 private Object[] arr; //an array of Pair objects, where each pair contains the key and value stored in the hashtable
34 private int max; //the size of arr. This should be a prime number
35 private int itemCount; //the number of items stored in arr
36 private final double maxLoad = 0.6; //the maximum load factor
37
38 public static enum PROBE_TYPE {
39 LINEAR_PROBE, QUADRATIC_PROBE, DOUBLE_HASH;
40 }
41
42 PROBE_TYPE probeType; //the type of probe to use when dealing with collisions
43 private final BigInteger DBL_HASH_K = BigInteger.valueOf(8);
44
45 /**
46 * Create a new Hashtable with a given initial capacity and using a given probe type
47 * @param initialCapacity
48 * @param pt
49 */
50 public Hashtable(int initialCapacity, PROBE_TYPE pt) {
51 max = nextPrime(initialCapacity); //sets the size
52 arr = new Object[max]; //creates the new Hashtable set to the max size
53 this.probeType = pt; //uses the given probe type
54 }
55
56 /**
57 * Create a new Hashtable with a given initial capacity and using the default probe type
58 * @param initialCapacity
59 */
60 public Hashtable(int initialCapacity) {
61 max = nextPrime(initialCapacity); //sets the size
62 arr = new Object[max]; //creates the new Hashtable set to the max size
63 probeType = PROBE_TYPE.LINEAR_PROBE; //uses the default probe type
64 }
65
66 /**
67 * Store the value against the given key. If the loadFactor exceeds maxLoad, call the resize
68 * method to resize the array. the If key already exists then its value should be overwritten.
69 * Create a new Pair item containing the key and value, then use the findEmpty method to find an unoccupied
70 * position in the array to store the pair. Call findEmmpty with the hashed value of the key as the starting
71 * position for the search, stepNum of zero and the original key.
72 * containing
73 * @param key
74 * @param value
75 */
76 public void put(String key, V value) {
77 int h = hash(key) % max;
78 if (getLoadFactor() > maxLoad) //checks if the LoadFactor exceeds the maxLoad and if it does resizes
79 {
80 resize(); //calls the resize
81 }
82 int place = 0;
83 if (hasKey(key) == true)
84 { //checks if the key exists
85 boolean running = true;
86 while (running)
87 {
88 if (arr[place].equals(key))
89 {
90 Pair newPair = new Pair(key, value); //creates the new Pair
91 arr[place] = newPair;
92 }
93 place++;
94 }
95 }
96 else //if there is no key it finds an empty spot and fills it in
97 {
98 if (arr[h] == null)
99 {
100 Pair newPair = new Pair(key, value);//creates the new pair
101 arr[h] = newPair;
102 itemCount++; //increases the amount of items
103 }
104 else
105 {
106 int pos = findEmpty(h, 0, key); //finds an empty place
107 Pair newPair = new Pair(key, value);
108 arr[pos] = newPair;
109 itemCount++; //increases the amount of items
110 }
111 }
112 }
113
114 /**
115 * Get the value associated with key, or return null if key does not exists. Use the find method to search the
116 * array, starting at the hashed value of the key, stepNum of zero and the original key.
117 * @param key
118 * @return
119 */
120 public V get(String key) {
121
122 return find(hash(key), key, 0); //returns the key and if there is no key it returns 0 (null)
123 }
124
125 /**
126 * Return true if the Hashtable contains this key, false otherwise
127 * @param key
128 * @return
129 */
130 public boolean hasKey(String key) {
131 if (find(hash(key), key, 0)== null)
132 {
133 return false; //if the hashtable contains no key it returns false
134 }
135 return true; //hence it will return true when a key is present
136
137 }
138
139 /**
140 * Return all the keys in this Hashtable as a collection
141 * @return
142 */
143 public Collection<String> getKeys() {
144 Collection<String> col = new ArrayList<String>(); //col is the collection of keys
145 for (int i = 0; i <this.max; i++)
146 { //counts to the max which is the size of the hashtable
147 if ( arr[i] != null)
148 { //counts down
149 Hashtable<V>.Pair pair = (Hashtable<V>.Pair)arr[i];
150 String key = pair.key;
151 col.add(key); //adds the key to the collection
152 }
153 }
154 return col; //returns the collection of keys
155
156
157 }
158
159 /**
160 * Return the load factor, which is the ratio of itemCount to max
161 * @return
162 */
163 public double getLoadFactor() { //devides the ammount of items by the max size which calculates the ratio
164 double loadFactor = (itemCount * 1.0) / max;
165 return loadFactor;
166 }
167
168 /**
169 * return the maximum capacity of the Hashtable
170 * @return
171 */
172 public int getCapacity() {
173 return max; //returns the max which is the maximum capacity
174 }
175
176 /**
177 * Find the value stored for this key, starting the search at position startPos in the array. If
178 * the item at position startPos is null, the Hashtable does not contain the value, so return null.
179 * If the key stored in the pair at position startPos matches the key we're looking for, return the associated
180 * value. If the key stored in the pair at position startPos does not match the key we're looking for, this
181 * is a hash collision so use the getNextLocation method with an incremented value of stepNum to find
182 * the next location to search (the way that this is calculated will differ depending on the probe type
183 * being used). Then use the value of the next location in a recursive call to find.
184 * @param startPos
185 * @param key
186 * @param stepNum
187 * @return
188 */
189 private V find(int startPos, String key, int stepNum) { //to find where the key matches
190
191 if (arr[startPos] == null) //if the start pos in null then it will return nothing
192 {
193 return null;
194 }
195 else if(arr[startPos] == key) //if the startpos is eqaul to the key then it will return the pair
196 {
197 return (V) ((Pair) arr[hash(key)]).value;
198
199 }
200 else //otherwise it will move to the next location
201 {
202 return find(getNextLocation(startPos, stepNum , key), key, stepNum);
203 }
204
205 }
206
207 /**
208 * Find the first unoccupied location where a value associated with key can be stored, starting the
209 * search at position startPos. If startPos is unoccupied, return startPos. Otherwise use the getNextLocation
210 * method with an incremented value of stepNum to find the appropriate next position to check
211 * (which will differ depending on the probe type being used) and use this in a recursive call to findEmpty.
212 * @param startPos
213 * @param stepNum
214 * @param key
215 * @return
216 */
217 private int findEmpty(int startPos, int stepNum, String key) { //to find an empty space
218 if (arr[startPos] == null) // if the startpos is empty then it will return the startpos
219 {
220 return startPos;
221 }
222 else //otherwise it wil continue down the list to the next free space
223 {
224 return findEmpty(getNextLocation(startPos, stepNum , key), stepNum, key);
225 }
226
227 }
228
229 /**
230 * Finds the next position in the Hashtable array starting at position startPos. If the linear
231 * probe is being used, we just increment startPos. If the double hash probe type is being used,
232 * add the double hashed value of the key to startPos. If the quadratic probe is being used, add
233 * the square of the step number to startPos.
234 * @param i
235 * @param stepNum
236 * @param key
237 * @return
238 */
239 private int getNextLocation(int startPos, int stepNum, String key) {
240 int step = startPos;
241 switch (probeType) {
242 case LINEAR_PROBE:
243 step++;
244 break;
245 case DOUBLE_HASH:
246 step += doubleHash(key);
247 break;
248 case QUADRATIC_PROBE:
249 step += stepNum * stepNum;
250 break;
251 default:
252 break;
253 }
254 return step % max;
255 }
256
257 /**
258 * A secondary hash function which returns a small value (less than or equal to DBL_HASH_K)
259 * to probe the next location if the double hash probe type is being used
260 * @param key
261 * @return
262 */
263 private int doubleHash(String key) {
264 BigInteger hashVal = BigInteger.valueOf(key.charAt(0) - 96);
265 for (int i = 1; i < key.length(); i++) {
266 BigInteger c = BigInteger.valueOf(key.charAt(i) - 96);
267 hashVal = hashVal.multiply(BigInteger.valueOf(27)).add(c);
268 }
269 return DBL_HASH_K.subtract(hashVal.mod(DBL_HASH_K)).intValue();
270 }
271
272 /**
273 * Return an int value calculated by hashing the key. See the lecture slides for information
274 * on creating hash functions. The return value should be less than max, the maximum capacity
275 * of the array
276 * @param key
277 * @return
278 */
279 private int hash(String key) {
280 int value = key.charAt(0) - 31;
281 for (int i = 0; i<key.length(); i++) //Calculates the new int by hashing the key and in doing this creates a new unique key
282 {
283 int c = key.charAt(i) - 31;
284 value = (value * 94 + c) % this.max;
285 }
286 return value; //returns the new int
287 }
288
289 /**
290 * Return true if n is prime
291 * @param n
292 * @return
293 */
294 private boolean isPrime(int n) {
295 int stop = (int) Math.sqrt(n);
296 for (int a = 2; a < stop; a++) {
297 if (n % a == 0) {
298 return false;
299 }
300 }
301 return true;
302 }
303
304 /**
305 * Get the smallest prime number which is larger than n
306 * @param n
307 * @return
308 */
309 private int nextPrime(int n) {
310
311 for (int a = 2; a <= n; a++) {
312 if (n % a == 0 && a != n) {
313 n++;
314 nextPrime(n);
315 }
316 }
317 return n;
318 }
319
320 /**
321 * Resize the hashtable, to be used when the load factor exceeds maxLoad. The new size of
322 * the underlying array should be the smallest prime number which is at least twice the size
323 * of the old array.
324 */
325 private void resize() {
326 Object[] temp = arr;
327 max = nextPrime(max * 2);//sets the new max which is the next smallest prime number
328 arr = new Object[max];
329
330 for (int j = 0; j < temp.length; j++)
331 {
332 if (temp[j] != null) //checks to make sure j is not null
333 {
334 Hashtable<V>.Pair pair = (Hashtable<V>.Pair) temp[j]; //adds j to the hashtable
335 String str = pair.key;
336 V value = (V) pair.value;
337 put(str, value); //inserts the pair
338 }
339 }
340 }
341
342
343
344
345 /**
346 * Instances of Pair are stored in the underlying array. We can't just store
347 * the value because we need to check the original key in the case of collisions.
348 * @author jb259
349 *
350 */
351 private class Pair {
352 private String key;
353 private Object value;
354
355 public Pair(String key, Object value) {
356 this.key = key;
357 this.value = value;
358 }
359 }
360
361}