Skip to content

Commit 4bcbfe4

Browse files
benaichbenaich
committed
Cuckoo HashTable
1 parent b4f8aec commit 4bcbfe4

2 files changed

Lines changed: 264 additions & 0 deletions

File tree

‎HashTable/Cuckoo/CuckooHashTable.java‎

Lines changed: 210 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,210 @@
1+
package HashTable.Cuckoo;
2+
3+
import HashTable.HashTableInterface;
4+
import java.util.function.Function;
5+
6+
public class CuckooHashTable<K, V> implements HashTableInterface<K, V> {
7+
8+
private Node[][] array;
9+
private Function<K, Integer>[] foh = new Function[2];
10+
private int tableSize = INITIAL_TABLE_SIZE;
11+
private int size;
12+
private int numCollisions;
13+
private int numResizes = 0;
14+
private int numRehashes = 0;
15+
16+
public CuckooHashTable() {
17+
this.tableSize = HashTableInterface.nextPrime(INITIAL_TABLE_SIZE);
18+
this.clear();
19+
this.hash();
20+
}
21+
22+
public void hash() {
23+
foh[0] = getHashingFunction();
24+
foh[1] = getHashingFunction();
25+
}
26+
27+
@Override
28+
public void clear() {
29+
array = new Node[2][tableSize];
30+
size = 0;
31+
numCollisions = 0;
32+
}
33+
34+
@Override
35+
public int getTableSize() {
36+
return tableSize;
37+
}
38+
39+
@Override
40+
public int getSize() {
41+
return size;
42+
}
43+
44+
@Override
45+
public int getNumCollisions() {
46+
return numCollisions;
47+
}
48+
49+
@Override
50+
public int getNumResizes() {
51+
return numResizes;
52+
}
53+
54+
@Override
55+
public int indexOf(K key) {
56+
int i = foh[0].apply(key);
57+
int j = foh[1].apply(key);
58+
if (array[0][i] != null && array[0][i].getKey().equals(key)) {
59+
return i;
60+
}
61+
62+
if (array[1][j] != null && array[1][j].getKey().equals(key)) {
63+
return j;
64+
}
65+
66+
return -1;
67+
}
68+
69+
public void put(K key, V val) {
70+
if (contains(key)) {
71+
return;
72+
}
73+
74+
if (loadFactor() > LOAD_FACTOR) {
75+
rehache(2 * tableSize);
76+
}
77+
78+
Node<K, V> node = new Node<>(key, val, foh[0].apply(key), foh[1].apply(key));
79+
put(node);
80+
size++;
81+
}
82+
83+
public void put(Node<K, V> node) {
84+
int index = (node.getStatus()) ? 1 : 0;
85+
int hachCode = node.hachCode[index];
86+
Node<K, V> tmp = array[index][hachCode];
87+
array[index][hachCode] = node;
88+
if (tmp == null) {
89+
return;
90+
}
91+
numCollisions++;
92+
tmp.toggleStatus();
93+
put(tmp);
94+
}
95+
96+
@Override
97+
public V get(K key) {
98+
int i = indexOf(key);
99+
if (i == -1) {
100+
return null;
101+
}
102+
if (array[0][i] != null && array[0][i].getKey().equals(key)) {
103+
return (V) array[0][i].getValue();
104+
}
105+
return (V) array[1][i].getValue();
106+
}
107+
108+
@Override
109+
public void delete(K key) {
110+
int i = indexOf(key);
111+
if (i == -1) {
112+
return;
113+
}
114+
if (array[0][i] != null && array[0][i].getKey().equals(key)) {
115+
array[0][i] = null;
116+
} else {
117+
array[1][i] = null;
118+
}
119+
size--;
120+
}
121+
122+
@Override
123+
public void resize() {
124+
throw new UnsupportedOperationException("Not supported yet.");
125+
}
126+
127+
@Override
128+
public void print() {
129+
System.out.println("----------- Print -----------");
130+
System.out.println("id | array 1 | Array 2 ");
131+
Node[] subArray1 = array[0];
132+
Node[] subArray2 = array[1];
133+
134+
for (int i = 0; i < tableSize; i++) {
135+
System.out.println(i + " | " + subArray1[i] + " | " + subArray2[i]);
136+
}
137+
}
138+
139+
@Override
140+
public void printGraph() {
141+
throw new UnsupportedOperationException("Not supported yet.");
142+
}
143+
144+
@Override
145+
public void printStatus() {
146+
System.out.println("------------- Table Status -------------------");
147+
System.out.println("Table size : " + getTableSize());
148+
System.out.println("Actual size : " + getSize());
149+
System.out.println("Numbre of collisions : " + getNumCollisions());
150+
System.out.println("Numbre of resises : " + getNumResizes());
151+
System.out.println("Numbre of rehashes : " + numRehashes);
152+
}
153+
154+
private boolean contains(K key) {
155+
return indexOf(key) != -1;
156+
}
157+
158+
private void rehache(int newLength) {
159+
Node[][] oldArray = array;
160+
this.tableSize = HashTableInterface.nextPrime(newLength);
161+
this.clear();
162+
this.hash();
163+
numRehashes++;
164+
if (newLength != tableSize) {
165+
numResizes++;
166+
}
167+
168+
for (Node[] subArray : oldArray) {
169+
for (Node<K, V> node : subArray) {
170+
if (node != null) {
171+
put(node.getKey(), node.getValue());
172+
}
173+
}
174+
}
175+
}
176+
177+
public static void main(String[] args) {
178+
CuckooHashTable<String, String> ht = new CuckooHashTable<>();
179+
180+
ht.put("banana", "yellow");
181+
ht.put("apple", "green");
182+
ht.put("android", "green");
183+
ht.put("cat", "white");
184+
ht.put("body", "black");
185+
ht.put("glass", "red");
186+
ht.put("jessy", "pinkman");
187+
ht.put("walter", "white");
188+
ht.put("arya", "startk");
189+
ht.put("dexter", "red");
190+
191+
ht.print();
192+
ht.printStatus();
193+
194+
System.out.println("----------- Get -----------");
195+
String deletedKey = "apple";
196+
System.out.println(deletedKey + " : -> " + ht.get(deletedKey));
197+
198+
System.out.println("----------- Delete " + deletedKey +" -----------");
199+
ht.delete(deletedKey);
200+
ht.print();
201+
ht.printStatus();
202+
203+
// Testing
204+
CuckooHashTable<String, String> table = new CuckooHashTable<>();
205+
for (int i = 0; i < 100000; i++) {
206+
table.put(HashTableInterface.randomString(), HashTableInterface.randomString());
207+
}
208+
table.printStatus();
209+
}
210+
}

‎HashTable/Cuckoo/Node.java‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package HashTable.Cuckoo;
2+
3+
import HashTable.LinearProbing.*;
4+
5+
public class Node<K, V> {
6+
7+
private K key;
8+
private V value;
9+
private boolean status = false;
10+
11+
public int[] hachCode = new int[2];
12+
public Node(K key, V value) {
13+
setKey(key);
14+
setValue(value);
15+
}
16+
public Node(K key, V value, int vh1, int vh2) {
17+
this(key, value);
18+
hachCode[0] = vh1;
19+
hachCode[1] = vh2;
20+
}
21+
22+
public V getValue() {
23+
return value;
24+
}
25+
26+
public void setValue(V value) {
27+
this.value = value;
28+
}
29+
30+
public K getKey() {
31+
return key;
32+
}
33+
34+
public void setKey(K key) {
35+
this.key = key;
36+
}
37+
38+
public void setStatus(boolean status) {
39+
this.status = status;
40+
}
41+
public boolean getStatus() {
42+
return status;
43+
}
44+
public void toggleStatus(){
45+
status = !status;
46+
}
47+
48+
@Override
49+
public String toString() {
50+
//return "(" + key + ", " + value + ")";
51+
return "(" + key + ", [" + hachCode[0] + "," + hachCode[1] + "])";
52+
}
53+
}
54+

0 commit comments

Comments
 (0)