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

1 /**
2 * Adds an item to this collection.
3 * @param x any object.
4 * @return true if this item was added to the collection.
5 */
6 public boolean add( AnyType x )
7 {
8 int currentPos = findPos( x );
9 if( isActive( array, currentPos ) )
10 return false;
11
12 if( array[ currentPos ] == null )
13 occupied++;
14 array[ currentPos ] = new HashEntry( x, true );
15 currentSize++;
16 modCount++;
17
18 if( occupied > array.length / 2 )
19 rehash( );
20
21 return true;
22 }

figure 20.15
The add routine for a
quadratic probing
hash table

1 /**
2 * Private routine to perform rehashing.
3 * Can be called by both add and remove.
4 */
5 private void rehash( )
6 {
7 HashEntry [ ] oldArray = array;
8
9 // Create a new, empty table
10 allocateArray( nextPrime( 4 * size( ) ) );
11 currentSize = 0;
12 occupied = 0;
13
14 // Copy table over
15 for( int i = 0; i < oldArray.length; i++ )
16 if( isActive( oldArray, i ) )
17 add( (AnyType) oldArray[ i ].element );
18 }

figure 20.16
The rehash method
for a quadratic
probing hash table

scan through the original array and add any active elements in the new table.
The add routine uses the new hash function (as it is logically based on the size
of array , which has changed) and automatically resolves all collisions. We can
be sure that the recursive call to add (at line 17) does not force another rehash.
Alternatively, we could replace line 17 with two lines of code surrounded by
braces (see Exercise 20.13).

The add routine
performs rehash-
ing if the table is
(half) full.