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

private static final int DEFAULT_TABLE_SIZE = 101;

1

figure 20.11
Hash table
initialization

2
3 /**
4 * Construct an empty HashSet.
5 */
6 public HashSet( )
7 {
8 allocateArray( DEFAULT_TABLE_SIZE );
9 clear( );
10 }
11
12 /**
13 * Construct a HashSet from any collection.
14 */
15 public HashSet( Collection<? extends AnyType> other )
16 {
17 allocateArray( nextPrime( other.size( ) * 2 ) );
18 clear( );
19
20 for( AnyType val : other )
21 add( val );
22 }

1 /**
2 * This method is not part of standard Java.
3 * Like contains, it checks if x is in the set.
4 * If it is, it returns the reference to the matching
5 * object; otherwise it returns null.
6 * @param x the object to search for.
7 * @return if contains(x) is false, the return value is null;
8 * otherwise, the return value is the object that causes
9 * contains(x) to return true.
10 */
11 public AnyType getMatch( AnyType x )
12 {
13 int currentPos = findPos( x );
14
15 if( isActive( array, currentPos ) )
16 return (AnyType) array[ currentPos ].element;
17 return null;
18 }
19
20 /**
21 * Tests if some item is in this collection.
22 * @param x any object.
23 * @return true if this collection contains an item equal to x.
24 */
25 public boolean contains( Object x )
26 {
27 return isActive( array, findPos( x ) );
28 }

figure 20.12
The searching
routines for a
quadratic probing
hash table