Skip to content

Commit 0abce97

Browse files
haeshedhaeshed
authored
Add Hash Table with Cuckoo Hashing (TheAlgorithms#3191)
1 parent ffd0250 commit 0abce97

File tree

3 files changed

+423
-0
lines changed

3 files changed

+423
-0
lines changed

‎src/main/java/com/thealgorithms/datastructures/hashmap/hashing/HashMapCuckooHashing.java

Lines changed: 254 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,254 @@
1+
package com.thealgorithms.datastructures.hashmap.hashing;
2+
3+
4+
import java.lang.Math;
5+
import java.util.Objects;
6+
7+
/**
8+
* This class is an implementation of a hash table using Cuckoo Hashing It uses
9+
* a dynamic array to lengthen the size of the hash table when load factor > .7
10+
*
11+
* <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing">...</a>
12+
*/
13+
public class HashMapCuckooHashing {
14+
15+
private int tableSize; // size of the hash table
16+
private Integer[] buckets; // array representing the table
17+
private final Integer AVAILABLE;
18+
private int size; // number of elements in the hash table
19+
20+
private int thresh; // threshold for infinite loop checking
21+
22+
/**
23+
* Constructor initializes buckets array, hsize, and creates dummy object
24+
* for AVAILABLE
25+
*
26+
* @param tableSize the desired size of the hash map
27+
*/
28+
public HashMapCuckooHashing(int tableSize) {
29+
this.buckets = new Integer[tableSize];
30+
this.tableSize = tableSize;
31+
this.AVAILABLE = Integer.MIN_VALUE;
32+
this.size = 0;
33+
this.thresh = (int) (Math.log(tableSize) / Math.log(2)) + 2;
34+
}
35+
36+
/**
37+
* The 2 Hash Functions takes a given key and finds an index based on its data, 2 distinctive ways to minimize collisions
38+
*
39+
* @param key the desired key to be converted
40+
* @return int an index corresponding to the key
41+
*/
42+
43+
public int hashFunction1(int key) {
44+
int hash = key % tableSize;
45+
if (hash < 0) {
46+
hash += tableSize;
47+
}
48+
return hash;
49+
}
50+
51+
public int hashFunction2(int key) {
52+
int hash = key / tableSize;
53+
hash %= tableSize;
54+
if (hash < 0) {
55+
hash += tableSize;
56+
}
57+
return hash;
58+
}
59+
60+
/**
61+
* inserts the key into the hash map by wrapping it as an Integer object, then uses while loop to insert new key
62+
* if desired place is empty, return.
63+
* if already occupied, continue while loop over the new key that has just been pushed out.
64+
* if while loop continues more than Thresh, rehash table to new size, then push again.
65+
*
66+
* @param key the desired key to be inserted in the hash map
67+
*/
68+
69+
public void insertKey2HashTable(int key) {
70+
Integer wrappedInt = key, temp;
71+
int hash, loopCounter = 0;
72+
73+
if (isFull()) {
74+
System.out.println("Hash table is full, lengthening & rehashing table");
75+
reHashTableIncreasesTableSize();
76+
}
77+
78+
if (checkTableContainsKey(key)) {
79+
throw new IllegalArgumentException("Key already inside, no duplicates allowed");
80+
}
81+
82+
while (loopCounter <= thresh) {
83+
loopCounter++;
84+
hash = hashFunction1(key);
85+
86+
if ((buckets[hash] == null) || Objects.equals(buckets[hash], AVAILABLE)) {
87+
buckets[hash] = wrappedInt;
88+
size++;
89+
checkLoadFactor();
90+
return;
91+
}
92+
93+
temp = buckets[hash];
94+
buckets[hash] = wrappedInt;
95+
wrappedInt = temp;
96+
hash = hashFunction2(temp);
97+
if (Objects.equals(buckets[hash], AVAILABLE)) {
98+
buckets[hash] = wrappedInt;
99+
size++;
100+
checkLoadFactor();
101+
return;
102+
} else if (buckets[hash] == null) {
103+
buckets[hash] = wrappedInt;
104+
size++;
105+
checkLoadFactor();
106+
return;
107+
}
108+
109+
temp = buckets[hash];
110+
buckets[hash] = wrappedInt;
111+
wrappedInt = temp;
112+
}
113+
System.out.println("Infinite loop occurred, lengthening & rehashing table");
114+
reHashTableIncreasesTableSize();
115+
insertKey2HashTable(key);
116+
}
117+
118+
/**
119+
* creates new HashMapCuckooHashing object, then inserts each of the elements in the previous table to it with its new hash functions.
120+
* then refers current array to new table.
121+
*
122+
*/
123+
public void reHashTableIncreasesTableSize() {
124+
HashMapCuckooHashing newT = new HashMapCuckooHashing(tableSize * 2);
125+
for (int i = 0; i < tableSize; i++) {
126+
if (buckets[i] != null && !Objects.equals(buckets[i], AVAILABLE)) {
127+
newT.insertKey2HashTable(this.buckets[i]);
128+
}
129+
}
130+
this.tableSize *= 2;
131+
this.buckets = newT.buckets;
132+
this.thresh = (int) (Math.log(tableSize) / Math.log(2)) + 2;
133+
}
134+
135+
136+
/**
137+
* deletes a key from the hash map and adds an available placeholder
138+
*
139+
* @param key the desired key to be deleted
140+
*/
141+
public void deleteKeyFromHashTable(int key) {
142+
Integer wrappedInt = key;
143+
int hash = hashFunction1(key);
144+
if (isEmpty()) {
145+
throw new IllegalArgumentException("Table is empty");
146+
}
147+
148+
if (Objects.equals(buckets[hash], wrappedInt)) {
149+
buckets[hash] = AVAILABLE;
150+
size--;
151+
return;
152+
}
153+
154+
hash = hashFunction2(key);
155+
if (Objects.equals(buckets[hash], wrappedInt)) {
156+
buckets[hash] = AVAILABLE;
157+
size--;
158+
return;
159+
}
160+
throw new IllegalArgumentException("Key " + key + " already inside, no duplicates allowed");
161+
}
162+
163+
/**
164+
* Displays the hash table line by line
165+
*/
166+
public void displayHashtable() {
167+
for (int i = 0; i < tableSize; i++) {
168+
if ((buckets[i] == null) || Objects.equals(buckets[i], AVAILABLE)) {
169+
System.out.println("Bucket " + i + ": Empty");
170+
} else {
171+
System.out.println("Bucket " + i + ": " + buckets[i].toString());
172+
}
173+
}
174+
System.out.println();
175+
}
176+
177+
/**
178+
* Finds the index of location based on an inputted key
179+
*
180+
* @param key the desired key to be found
181+
* @return int the index where the key is located
182+
*/
183+
public int findKeyInTable(int key) {
184+
Integer wrappedInt = key;
185+
int hash = hashFunction1(key);
186+
187+
if (isEmpty()) {
188+
throw new IllegalArgumentException("Table is empty");
189+
}
190+
191+
if (Objects.equals(buckets[hash], wrappedInt)) return hash;
192+
193+
hash = hashFunction2(key);
194+
if (!Objects.equals(buckets[hash], wrappedInt))
195+
throw new IllegalArgumentException("Key " + key + " not found in table");
196+
else {
197+
return hash;
198+
}
199+
}
200+
/**
201+
* checks if key is inside without any output other than returned boolean.
202+
*
203+
* @param key the desired key to be found
204+
* @return int the index where the key is located
205+
*/
206+
public boolean checkTableContainsKey(int key){
207+
return ((buckets[hashFunction1(key)] != null && buckets[hashFunction1(key)].equals(key)) || (buckets[hashFunction2(key)] != null && buckets[hashFunction2(key)] == key));
208+
}
209+
210+
/**
211+
* Checks the load factor of the hash table if greater than .7,
212+
* automatically lengthens table to prevent further collisions
213+
*/
214+
public double checkLoadFactor() {
215+
double factor = (double) size / tableSize;
216+
if (factor > .7) {
217+
System.out.printf("Load factor is %.2f , rehashing table\n", factor);
218+
reHashTableIncreasesTableSize();
219+
}
220+
return factor;
221+
}
222+
223+
/**
224+
* isFull returns true if the hash map is full and false if not full
225+
*
226+
* @return boolean is Empty
227+
*/
228+
public boolean isFull() {
229+
boolean response = true;
230+
for (int i = 0; i < tableSize; i++) {
231+
if (buckets[i] == null || Objects.equals(buckets[i], AVAILABLE)) {
232+
return false;
233+
}
234+
}
235+
return response;
236+
}
237+
238+
/**
239+
* isEmpty returns true if the hash map is empty and false if not empty
240+
*
241+
* @return boolean is Empty
242+
*/
243+
public boolean isEmpty() {
244+
boolean response = true;
245+
for (int i = 0; i < tableSize; i++) {
246+
if (buckets[i] != null) {
247+
response = false;
248+
break;
249+
}
250+
}
251+
return response;
252+
}
253+
public int getNumberOfKeysInTable(){return size;}
254+
}

‎src/main/java/com/thealgorithms/datastructures/hashmap/hashing/MainCuckooHashing.java

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package com.thealgorithms.datastructures.hashmap.hashing;
2+
3+
import java.util.Scanner;
4+
5+
public class MainCuckooHashing {
6+
public static void main(String[] args) {
7+
8+
int choice, key;
9+
10+
HashMapCuckooHashing h = new HashMapCuckooHashing(7);
11+
Scanner In = new Scanner(System.in);
12+
13+
while (true) {
14+
System.out.println("_________________________");
15+
System.out.println("Enter your Choice :");
16+
System.out.println("1. Add Key");
17+
System.out.println("2. Delete Key");
18+
System.out.println("3. Print Table");
19+
System.out.println("4. Exit");
20+
System.out.println("5. Search and print key index");
21+
System.out.println("6. Check load factor");
22+
System.out.println("7. Rehash Current Table");
23+
24+
choice = In.nextInt();
25+
26+
switch (choice) {
27+
case 1: {
28+
System.out.println("Enter the Key: ");
29+
key = In.nextInt();
30+
h.insertKey2HashTable(key);
31+
break;
32+
}
33+
case 2: {
34+
System.out.println("Enter the Key delete: ");
35+
key = In.nextInt();
36+
h.deleteKeyFromHashTable(key);
37+
break;
38+
}
39+
case 3: {
40+
System.out.println("Print table:\n");
41+
h.displayHashtable();
42+
break;
43+
}
44+
case 4: {
45+
In.close();
46+
return;
47+
}
48+
case 5: {
49+
System.out.println("Enter the Key to find and print: ");
50+
key = In.nextInt();
51+
System.out.println("Key: " + key + " is at index: " + h.findKeyInTable(key) + "\n");
52+
break;
53+
}
54+
case 6: {
55+
System.out.printf("Load factor is: %.2f\n", h.checkLoadFactor());
56+
break;
57+
}
58+
case 7: {
59+
h.reHashTableIncreasesTableSize();
60+
break;
61+
}
62+
}
63+
}
64+
}
65+
}

0 commit comments

Comments
 (0)