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

1 /**
2 * Method that performs quadratic probing resolution.
3 * @param x the item to search for.
4 * @return the position where the search terminates.
5 */
6 private int findPos( Object x )
7 {
8 int offset = 1;
9 int currentPos = ( x == null ) ?
10 0 : Math.abs( x.hashCode( ) % array.length );
11
12 while( array[ currentPos ] != null )
13 {
14 if( x == null )
15 {
16 if( array[ currentPos ].element == null )
17 break;
18 }
19 else if( x.equals( array[ currentPos ].element ) )
20 break;
21
22 currentPos += offset; // Compute ith probe
23 offset += 2;
24 if( currentPos >= array.length ) // Implement the mod
25 currentPos -= array.length;
26 }
27
28 return currentPos;
29 }
figure 20.17
The routine that finally deals with quadratic probing
So far, nothing that we have done depends on quadratic probing.
Figure 20.17 implements findPos , which finally deals with the quadratic prob-
ing algorithm. We keep searching the table until we find an empty cell or a
match. Lines 22-25 directly implement the methodology described in Theo-
rem 20.5, using two additions. There are additional complications because
null is a valid item in the HashSet ; the code illustrates why it is preferable to
assume that null is invalid.
Figure 20.18 gives the implementation of the iterator inner class. It is rela-
tively standard fare, though quite tricky. visited represents the number of calls
to next , while currentPos represents the index of the last object returned by next .
Finally, Figure 20.19 implements HashMap . It is much like TreeMap , except
that Pair is a nested class rather than an inner class (it does not need access to
an outer object), and implements both equals and hashCode methods instead of
the Comparable interface.