· 6 years ago · Aug 05, 2019, 10:34 PM
1// QuadraticProbing Hash table class
2//
3// CONSTRUCTION: an approximate initial size or default of 101
4//
5// ******************PUBLIC OPERATIONS*********************
6// bool insert( x ) --> Insert x
7// bool remove( x ) --> Remove x
8// bool contains( x ) --> Return true if x is present
9// void makeEmpty( ) --> Remove all items
10
11
12/**
13 * Probing table implementation of hash tables.
14 * Note that all "matching" is based on the equals method.
15 * @author Mark Allen Weiss
16 */
17public class QuadraticProbingHashTable<AnyType>
18{
19 /**
20 * Construct the hash table.
21 */
22 public QuadraticProbingHashTable( )
23 {
24 this( DEFAULT_TABLE_SIZE );
25 }
26
27 /**
28 * Construct the hash table.
29 * @param size the approximate initial size.
30 */
31 public QuadraticProbingHashTable( int size ){
32 allocateArray( size );
33 doClear( );
34 }
35
36 /**
37 * Insert into the hash table. If the item is
38 * already present, do nothing.
39 * @param x the item to insert.
40 */
41 public boolean insert( AnyType x ){
42 // Insert x as active
43 int currentPos = findPos( x );
44 if( isActive( currentPos ) )
45 return false;
46
47 if( array[ currentPos ] == null )
48 ++occupied;
49 array[ currentPos ] = new HashEntry<>( x, true );
50 theSize++;
51
52 // Rehash; see Section 5.5
53 if( occupied > array.length / 2 )
54 rehash( );
55
56 return true;
57 }
58
59 /**
60 * Expand the hash table.
61 */
62 private void rehash( )
63 {
64 HashEntry<AnyType> [ ] oldArray = array;
65
66 // Create a new double-sized, empty table
67 allocateArray( 2 * oldArray.length );
68 occupied = 0;
69 theSize = 0;
70
71 // Copy table over
72 for( HashEntry<AnyType> entry : oldArray )
73 if( entry != null && entry.isActive )
74 insert( entry.element );
75 }
76
77 /**
78 * Method that performs quadratic probing resolution.
79 * @param x the item to search for.
80 * @return the position where the search terminates.
81 */
82 private int findPos( AnyType x ){
83 int offset = 1;//I HAVE NO IDEA WHATS HAPPENING, BUT SOMETHING TO DO WITH THE OFFSET BETWEEN PROBES
84 int currentPos = myhash( x );
85
86 while( array[ currentPos ] != null &&
87 !array[ currentPos ].element.equals( x ) )
88 {
89 currentPos += offset; // Compute ith probe
90 offset += 2;
91 if( currentPos >= array.length )
92 currentPos -= array.length;
93 }
94
95 return currentPos;
96 }
97
98 /**
99 * Remove from the hash table.
100 * @param x the item to remove.
101 * @return true if item removed
102 */
103 public boolean remove( AnyType x )
104 {
105 int currentPos = findPos( x );
106 if( isActive( currentPos ) )
107 {
108 array[ currentPos ].isActive = false;
109 theSize--;//BUT DONT DECREMENT THE OCCUPIED
110 return true;
111 }
112 else
113 return false;
114 }
115
116 /**
117 * Get current size.
118 * @return the size.
119 */
120 public int size( )
121 {
122 return theSize;
123 }
124
125 /**
126 * Get length of internal table.
127 * @return the size.
128 */
129 public int capacity( )
130 {
131 return array.length;
132 }
133
134 /**
135 * Find an item in the hash table.
136 * @param x the item to search for.
137 * @return the matching item.
138 */
139 public boolean contains( AnyType x )
140 {
141 int currentPos = findPos( x );
142 return isActive( currentPos );
143 }
144
145 /**
146 * Return true if currentPos exists and is active.
147 * @param currentPos the result of a call to findPos.
148 * @return true if currentPos is active.
149 */
150 private boolean isActive( int currentPos )
151 {//YOU WON'T GET A NPE BECAUSE THE AND OPERATOR ONLY CHECKS THE SECOND CONDITION IF THE FIRST IS TRUE
152 return array[ currentPos ] != null && array[ currentPos ].isActive;
153 }
154
155 /**
156 * Make the hash table logically empty.
157 */
158 public void makeEmpty( )
159 {
160 doClear( );
161 }
162
163 private void doClear( )
164 {
165 occupied = 0;
166 for( int i = 0; i < array.length; i++ )
167 array[ i ] = null;
168 }
169
170 private int myhash( AnyType x )
171 {
172 int hashVal = x.hashCode( );
173
174 hashVal %= array.length;
175 if( hashVal < 0 )
176 hashVal += array.length;
177
178 return hashVal;
179 }
180
181 private static class HashEntry<AnyType>
182 {
183 public AnyType element; // the element
184 public boolean isActive; // false if marked deleted
185
186 public HashEntry( AnyType e )
187 {
188 this( e, true );
189 }
190
191 public HashEntry( AnyType e, boolean i )
192 {
193 element = e;
194 isActive = i;
195 }
196 }
197
198 private static final int DEFAULT_TABLE_SIZE = 101;
199
200 private HashEntry<AnyType> [ ] array; // The array of elements
201 private int occupied; // The number of occupied cells
202 private int theSize; // Current size
203
204 /**
205 * Internal method to allocate array.
206 * @param arraySize the size of the array.
207 */
208 private void allocateArray( int arraySize )
209 {
210 array = new HashEntry[ nextPrime( arraySize ) ];
211 }
212
213 /**
214 * Internal method to find a prime number at least as large as n.
215 * @param n the starting number (must be positive).
216 * @return a prime number larger than or equal to n.
217 */
218 private static int nextPrime( int n )
219 {
220 if( n % 2 == 0 )
221 n++;
222
223 for( ; !isPrime( n ); n += 2 )
224 ;
225
226 return n;
227 }
228
229 /**
230 * Internal method to test if a number is prime.
231 * Not an efficient algorithm.
232 * @param n the number to test.
233 * @return the result of the test.
234 */
235 private static boolean isPrime( int n )
236 {
237 if( n == 2 || n == 3 )
238 return true;
239
240 if( n == 1 || n % 2 == 0 )
241 return false;
242
243 for( int i = 3; i * i <= n; i += 2 )
244 if( n % i == 0 )
245 return false;
246
247 return true;
248 }
249
250
251 // Simple main
252 public static void main( String [ ] args )
253 {
254 QuadraticProbingHashTable<String> H = new QuadraticProbingHashTable<>( );
255
256
257 long startTime = System.currentTimeMillis( );
258
259 final int NUMS = 2000000;
260 final int GAP = 37;
261
262 System.out.println( "Checking... (no more output means success)" );
263
264
265 for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
266 H.insert( ""+i );
267 for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
268 if( H.insert( ""+i ) )
269 System.out.println( "OOPS!!! " + i );
270 for( int i = 1; i < NUMS; i+= 2 )
271 H.remove( ""+i );
272
273 for( int i = 2; i < NUMS; i+=2 )
274 if( !H.contains( ""+i ) )
275 System.out.println( "Find fails " + i );
276
277 for( int i = 1; i < NUMS; i+=2 )
278 {
279 if( H.contains( ""+i ) )
280 System.out.println( "OOPS!!! " + i );
281 }
282
283 long endTime = System.currentTimeMillis( );
284
285 System.out.println( "Elapsed time: " + (endTime - startTime) );
286 }
287
288}