· 7 years ago · Nov 07, 2018, 11:12 PM
1package comp2402a5;
2
3
4/**
5 * This class implements the cuckoo hash
6 *
7 * See: Rasmus Pagh, Flemming Friche Rodler, Cuckoo Hashing, Algorithms - ESA 2001,
8 * Lecture Notes in Computer Science 2161, Springer 2001, ISBN 3-540-42493-8
9 *
10 * @param <T>
11 */
12public abstract class CuckooHashTable<T> extends OpenAddressHashTable<T> {
13
14 /* add any attributes you may need here */
15
16 MultiplicativeHashFunction h1 = null;
17 MultiplicativeHashFunction h2 = null;
18
19 int nzz = 0;
20 int[] myZZ;
21 Class<T> myClazz;
22 double maxLoop = 100;
23 int rehashFlag = 0;
24 /**
25 * Create a new empty hash table
26 * @param clazz is the class of the data to be stored in the hash table
27 * @param zz is an array of integer values to be used for the hash functions
28 */
29 public CuckooHashTable(Class<T> clazz, int[] zz) {
30
31 super(clazz);
32 f = new Factory<T>(clazz);
33 d = 4;
34 t = f.newArray(1<<d);
35 n = 0;
36 myZZ = zz;
37 myClazz = clazz;
38
39 h1 = new MultiplicativeHashFunction(myZZ[nzz++], w, d);
40 h2 = new MultiplicativeHashFunction(myZZ[nzz++], w, d);
41 }
42
43 /* define all abstract methods inherited from parent class here */
44
45 /**
46 * Resize the table
47 */
48 protected void resize(){
49
50 }
51
52 /**
53 * Adds element x to the table if there does not already exist an item y
54 * in the table such that x.equals(y) is true.
55 *
56 * @param x is the item to add to the table
57 * @return true if x is successfully added to the table, returns false if there already
58 * an item y in the table such that x.equals(y) is true.
59 */
60 public boolean add(T x) {
61 int count = 0;
62 T movingObject = x;
63 T tempObject;
64
65 if (find(x) == null) {
66 if (((double)n+1 / t.length) > 0.5) {
67 d++;
68 rehash();
69 }
70 while (count < maxLoop) {
71 int i = h1.hash(movingObject);
72 if (t[i] == null) {
73 t[i] = movingObject;
74 n++;
75 return true;
76 } else {
77 tempObject = t[i];
78 t[i] = movingObject;
79 movingObject = tempObject;
80 count++;
81 }
82 i = h2.hash(movingObject);
83 if (t[i] == null) {
84 t[i] = movingObject;
85 n++;
86 return true;
87 } else {
88 tempObject = t[i];
89 t[i] = movingObject;
90 movingObject = tempObject;
91 count++;
92 }
93 }
94 if (rehashFlag == 0){
95 rehash();
96 if (add(movingObject)) return true;
97 }
98 }
99 return false;
100 }
101
102
103 /**
104 * Remove the copy of x stored in this table if it exists.
105 * @param x the item to remove
106 * @return the element y stored in the table such that x.equals(y) is true,
107 * or null if no such element y exists
108 */
109 public T remove(T x){
110 int i = h1.hash(x);
111 if (x.equals(t[i])){
112 t[i] = null;
113 n--;
114 if (((double)n/t.length) < 0.125 && d >= 5) {
115 d--;
116 rehash();
117 }
118 return x;
119 }
120 i = h2.hash(x);
121 if (x.equals(t[i])){
122 t[i] = null;
123 n--;
124 if (((double)n/t.length) < 0.125 && d >= 5) {
125 d--;
126 rehash();
127 }
128 return x;
129 }
130 return null;
131 }
132
133
134
135 /**
136 * Get the copy of x stored in this table.
137 * @param x - the item to get
138 * @return - the element y stored in this table such that x.equals(y)
139 * is true, or null if no such element y exists
140 */
141 public T find(Object x){
142 int i = h1.hash(x);
143 if (x.equals(t[i])) return t[i];
144 i = h2.hash(x);
145 if (x.equals(t[i])) return t[i];
146 return null;
147 }
148
149 public void rehash(){
150 rehashFlag = 1;
151 T[] oldT = t;
152
153 outerloop:
154 while(rehashFlag == 1){
155 h1 = new MultiplicativeHashFunction(myZZ[nzz++], w, d);
156 h2 = new MultiplicativeHashFunction(myZZ[nzz++], w, d);
157 n = 0;
158 t = f.newArray(1<<d);
159
160 for (int k = 0; k < oldT.length; k++){
161 if (oldT[k] != null){
162 if(!(add(oldT[k]))) continue outerloop;
163 }
164 }
165 rehashFlag = 0;
166 }
167 }
168
169/* public static void main(String[] args) {
170 System.out.println("Hello World!");
171 int[] z = {0, 1, 2, 3};
172 int[] zz= {355565525,355515551,351555553,325515555,395155759,355512554,355551555,355513554,355555155,355515054,135555505,255515554,555551555,655513554,755555155,855515054,95555505,45551555,955565525,385515551,357555553,325615555,395145759,355515554,355551535,355513524,355555151,305515054,935555505,855515554,755551555,555513554,655555155,155515054,95055505,45951555};
173 CuckooHashTable c = new CuckooHashTable(Integer.class, zz);
174 for (int i = 0; i < 10; i++){
175 c.add(i);
176 System.out.println("elements in list: " + c.size() + " n = " + c.n + " d = " + c.d + " length = " + c.t.length);
177 }
178 for (int i = 0; i < 10; i++){
179 c.remove(i);
180 System.out.println("elements in list: " + c.size() + " n = " + c.n + " d = " + c.d + " length = " + c.t.length);
181 }
182 }*/
183}