Hash tables - Data Structures and Problem Solving Using Java - page 792

1 /**
2 * Tests if item in pos is active.
3 * @param pos a position in the hash table.
4 * @param arr the HashEntry array (can be oldArray during rehash).
5 * @return true if this position is active.
6 */
7 private static boolean isActive( HashEntry [ ] arr, int pos )
8 {
9 return arr[ pos ] != null && arr[ pos ].isActive;
10 }

figure 20.13
The isActive method for a quadratic probing hash table

1 /**
2 * Removes an item from this collection.
3 * @param x any object.
4 * @return true if this item was removed from the collection.
5 */
6 public boolean remove( Object x )
7 {
8 int currentPos = findPos( x );
9 if( !isActive( array, currentPos ) )
10 return false;
11
12 array[ currentPos ].isActive = false;
13 currentSize--;
14 modCount++;
15
16 if( currentSize < array.length / 8 )
17 rehash( );
18
19 return true;
20 }
21
22 /**
23 * Change the size of this collection to zero.
24 */
25 public void clear( )
26 {
27 currentSize = occupied = 0;
28 modCount++;
29 for( int i = 0; i < array.length; i++ )
30 array[ i ] = null;
31 }

figure 20.14
The remove and clear
routines for a
quadratic probing
hash table

We adjust currentSize , occupied , and modCount at lines 13-15 and return unless
a rehash is in order; otherwise, we call the private method rehash .
The code that implements rehashing is shown in Figure 20.16. Line 7
saves a reference to the original table. We create a new, empty hash table at
lines 10-12 that will have a 0.25 load factor when rehash terminates. Then we