CSC 16 Lab 12: Polymorphic Closed Hashing


The implementation of hash tables I showed you in class is called an "open"
hash table, because the size of the table is unlimited. Each array element
points to the start of a linked list which can be arbitarily large.

An alternative form for hash tables does not used linked lists. It is called
a closed hash table because the maximum size is limited by the size of the 
array.  The central problem we need to deal with in such a table is: if
a location is already occupied, how do we find a new place to put our data?

Thus in addition to the concept of a hash function, we also have a "rehash" 
function.  Usually, this function just adds one to the previous hash value.
That is, if array location h is occupied, try h+1.

public int rehash(int oldhash)  { return oldhash+1; }

To insert an element, compute

   int h = hash(key);  // as before
   while (Table[h] != null) h = rehash(h);  // find empty slot
   Table[h] = element to insert;

Deleting an element and looking up an element, however, involves an extra
problem.  If an element is deleted from the hash table, we naturally set
the table location to null.  However, say now we want to look something up.
The rehash function could bring us to a cell that was just deleted.  What
can we conclude?  Either the element doesn't exist, or it exists but
is further down the array.  That is, say elements A, B and C all have the
same hash value, and are stored in consective locations in the array:

0  1  2
A  B  C

Assume now that B is deleted.  We set location 1 to null.
Now say we lookup C.  The first hash value is 0, and so we rehash to
try 1.  But location 1 is null.  Do we look further?  How can we conclude that
an element doesn't exist without exhaustively looking up the entire table?

The solution is to use a parallel array to distinguish a location that has 
never been used, and one that was used but the element was deleted.

When we lookup, we can conclude that the element we're looking for doesn't
exist as soon as we reach a cell that was never used at all.  However, if
we reach a cell that's null but was used before, then the element may still
be in the table and we must keep rehashing to look for the element.

Here's some code to get you started:

class closedhash
{
    private int max; // max size of array
    private int occupied = 0; // number of cells actually occupied
    private student[] Ht;     // the table 
    private boolean[] Deleted;   // parallel deleted array
    public closedhash(int m)
    {
	max = m;
	Ht = new student[m]; // initially all null
	Deleted = new boolean[m];
	for(int i=0;i<m;i++) { Deleted[i]=false; } //false=never used.
    } // constructor

    // A hash function on strings, computes sum of ascii values * 4.
    // That is, we leave 4 slots between consecutive hash values to
    // save space for rehashing.
    public int hash(String s)
    {
	// add up ascii values, then mod max:
	int ax = 0;
	int n = s.length() - 1;
	while (n >= 0)
	    {
		ax += (int)s.charAt(n--);
	    }
	return (ax * 4) % max;
    } // hash function
    
    // The rehash function takes the previous hash value as arg
    public int rehash(int h) 
    {
        return (h+1) % max;
    }

/*

  You have to implement insert, lookup, and delete.

  Also write a main to test the operations.  Make sure you have
an example where two data elements have the same hash key.

...
*/
} // closedhash


///////////////// Part II /////////////////

Now make your closed hash table polymorphic, as I have done for open hash
tables.

Make at least two concrete subclasses, one a hash table of students and for
form some other datatype, such as string, bankaccount, etc ...