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

1 private static class HashEntry implements java.io.Serializable
2 {
3 public Object element; // the element
4 public boolean isActive; // false if marked deleted
5
6 public HashEntry( Object e )
7 {
8 this( e, true );
9 }
10
11 public HashEntry( Object e, boolean i )
12 {
13 element = e;
14 isActive = i;
15 }
16 }

figure 20.10
The HashEntry nested
class

types are illegal, HashEntry is not generic. The HashEntry nested class is shown
in Figure 20.10. The array is declared at line 49. We need to keep track of
both the logical size of the HashSet and the number of items in the hash table
(including elements marked as deleted); these values are stored in currentSize
and occupied , respectively, which are declared at lines 46 and 47.

The rest of the class contains declarations for the hash table routines and
iterator. The general layout is similar to that for TreeSet .
Three private methods are declared; we describe them when they are used
in the class implementation. We can now discuss the implementation of the
HashSet class.

The general layout
is similar to that for
TreeSet .

The hash table constructors are shown in Figure 20.11; nothing special is
going on here. The searching routine, contains , and the nonstandard getMatch
are shown in Figure 20.12. contains uses the private method isActive , shown
in Figure 20.13. Both contains and getMatch also call findPos , shown later, to
implement quadratic probing. The findPos method is the only place in the
entire code that depends on quadratic probing. Then contains and getMatch are
easy to implement: An element is found if the result of findPos is an active cell
(if findPos stops on an active cell, there must be a match). Similarly, the remove
routine shown in Figure 20.14 is short. We check whether findPos takes us to
an active cell; if so, the cell is marked deleted. Otherwise, false is returned
immediately. Note that this lowers currentSize , but not occupied . Also, if there
are many deleted items, the hash table is resized, at lines 16-17. The mainte-
nance of modCount is identical to the other Collections API components previ-
ously implemented. clear removes all items from the HashSet .
The add routine is shown in Figure 20.15. At line 8 we call findPos . If x is
found, we return false at line 10 because duplicates are not allowed. Other-
wise, findPos gives the place to insert x . The insertion is performed at line 12.

Most routines are
just a few lines of
code because they
call findPos to per-
form quadratic
probing.