Implementing a Hash table in Java

Intro...
- This webpage will discuss the implementation of a Hash Table with Linear Addressing in Goodrich's book
- There may be some Java constructs that you may not have seen...
  Please ask questions when you encounter some language issues that are unclear....

Hash entry type

The hash entry consists of a key and a value

To provide a common interface, Goodrich first define an Entry interface:

public interface Entry<K,V> { /** Returns the key stored in this entry. */ public K getKey(); /** Returns the value stored in this entry. */ public V getValue(); }

The actual type (class) definition of the hash table entry is as follows:

public class HashEntry<K,V> implements Entry<K,V> { protected K key; protected V value; public HashEntry(K k, V v) { key = k; value = v; } public V getValue() { return value; } public K getKey() { return key; } public V setValue(V val) { V oldValue = value; value = val; return oldValue; } public boolean equals(Object o) { HashEntry ent; try { ent = (HashEntry) o; // Test if o is a HashEntry... } catch (ClassCastException ex) { return false; } return (ent.getKey() == key) && (ent.getValue() == value); } public String toString() { return "(" + key + "," + value + ")"; } }

Location of the Hash entry type (class):

A note on static nested classes

Static nested class:

public class A // Outer class { public static class B // Inner (nested) class { public void methodB1() { .... } } .... }

Meaning of a static nested class:

A static nested class interacts other classes (including its outer class) as a top-level class.
In fact:

Example working with static nested classes:

public class MyProg { public static void main(String[] args) { A.B x = new A.B(); // defining variable x.methodB1(); // Invoking method ... } }

Example Program: (Demo above code)
- Prog file: click here

A note on instance nested classes

Instance nested class:

public class A // Outer class { public class B // Inner class { public void methodB1() { .... } } .... }

Meaning of an instance nested class:

An instance nested (inner) class is an instance member (like an instance variable or an instance method) of the outer class
Important note:

You cannot create an object of an inner class:

An instance (object) of an inner class can only exist within an instance (object) of its outer class
Forbidden:

Note:

When you create an object of the outer class, you will need create an object of its inner instance class(es) at that time !

Implication:

The constructors of the outer class must take care of instantiating the object variables of the inner instance class !!!

Example:

public class A { public class B // Inner instance class { public void methodB1() { .... } } .... public B x; // 1: You need a reference variable to a B-type object in class A public A() // Constructor for A { ... x = new B(); // 2; You need to instantiate an inner class (B) object ! ... } }

Example working with static nested classes:

public class MyProg { public static void main(String[] args) { A x = new A(); // defining variable x.x.methodB1(); // Invoking method ... } }

Example Program: (Demo above code)
- Prog file: click here

Packaging the HashEntry class

As a static inner class:

public class HashTableMap<K,V> implements Map<K,V> { /** Static nested class for an entry in a hash table. */ public static class HashEntry<K,V> implements Entry<K,V> { .... (see above for the definition) } (Variables and methods of the Map implementation) }

The Map interface

To allow different implementations of the Map ADT functionality, Goodrich defines the Map interface (similar to Java's approach in doing stuff - the long and winding road...)

Map ADT interface:

public interface Map<K,V> { /** Returns the number of items in the map. */ public int size(); /** Returns whether the map is empty. */ public boolean isEmpty(); /** Puts a given key-value pair in the map, replacing a previous * one, if any, and returns the old value. */ public V put(K key, V value) throws InvalidKeyException; /** Returns the value associated with a key. */ public V get(K key) throws InvalidKeyException; /** Removes the key-value pair with a given key. */ public V remove(K key) throws InvalidKeyException; /** Returns an iterable object containing all the keys in the map. */ public Iterable<K> keySet(); /** Returns an iterable object containing all the values in the map. */ public Iterable<V> values(); /** Returns an iterable object containing all the entries in the map. */ public Iterable<Entry<K,V>> entrySet(); }

Implementating the Map interface:

Data structure (array and other stuff) used by HashTableMap

Member variables in the HashTableMap class:

public class HashTableMap<K,V> implements Map<K,V> { protected Entry<K,V> AVAILABLE = new HashEntry<K,V>(null, null); // Dummy entry to occupy the DELETED slots protected int n = 0; // Actual number of entries in the Map protected int prime; // Prime number used in the hash function protected int capacity; // = N (capacity of bucket array) public Entry<K,V>[] bucket; // bucket array // I made it public to print :-) protected long scale; // Scaling factor (a) of the MAD compression protected long shift; // Shift factor (b) of the MAD compression .... }

Constructor for the Map class:

public class HashTableMap<K,V> implements Map<K,V> { ... public HashTableMap() // Default constructor... { this(109345121,1000); // Calls the actual constructor below // 109345121 is the default prime number :-) } public HashTableMap(int cap) { this(109345121, cap); // Calls the actual constructor below } public HashTableMap(int p, int cap) { prime = p; capacity = cap; bucket = (Entry<K,V>[]) new HashEntry[capacity]; // Create an array of HashEntries // It's a safe cast /* --------------------------------------------------- Select a and b for MAD compression: Hash index = ( (a × hashCode + b) % p ) % N ---------------------------------------------------- */ java.util.Random rand = new java.util.Random(); scale = rand.nextInt(prime-1) + 1; // integer from range [1..(p-1)] shift = rand.nextInt(prime); // integer from range [0..(p-1)] } ... }

Lookup the array index that stores a key

The main routine of the HashTableMap implementation (used by lookup, insert and delete) is how to look up the array element that store an entry containing a specific key value

FindEntry(K key):

/** --------------------------------------------------------------- Helper search method: - if the key is found, it returns index >= 0 - if the key is not found, it returns -a - 1 (a neg value), where a is the index of the first empty/available slot ------------------------------------------------------------------ */ protected int findEntry(K key) throws InvalidKeyException { int avail = -1; // Flag indicating an initial search int i; int j; checkKey(key); // Make sure "key" is correct type of object i = hashValue(key); // Hash index j = i; // Stop criteria... stop when i == j // See: click here do { Entry<K,V> e; e = bucket[i]; // (Initial) Hash location if ( e == null ) { /* Reach an EMPTY slot */ if ( avail < 0 ) { avail = i; // Remember the first EMPTY slot } break; } if ( key.equals(e.getKey()) ) // we have found our key { return i; // key found, return index of array that stores the key } if ( e == AVAILABLE ) { // This slot is open (was "previousle delete") if ( avail < 0 ) avail = i; // First time -> remember that FIRST available (EMPTY) slot } i = (i + 1) % capacity; // Linear probe, look at the next location } while (i != j); /* -------------------------------------------- At this point: 1. k is NOT found 1. avail = index of the FIRST empty slot -------------------------------------------- */ return -avail - 1; // Return indication of not found and the index // of the first empty/available slot // Note: the actual index is "avail", and avail canbe 0 // We subtract 1 to make sure that the return value is < 0 // To get "avail" back: -value - 1 }

Note:

The findEntry() method is used by get(), insert() and remove() !!!
findEntry() returns a value ≥ 0 when key k is found in the map

findEntry() returns a value < 0 when key k is not found in the map

The negative return value also convey the location (index) of the first empty slot in the array

Example:

findEntry(22): (to prepare for insert(22,W))

Search process:

findEntry(22) starts the search at array element bucket[4]
The search process stops when it find an empty slot: this happens at index 8
findEntry(22) will return:
- (−5 − 1) = −6
The negative value indicates not found

To convert the negative return value to an array index, use:
Example:

The get(key) (lookup) method for a map

get(K key):

get(K key) method:

/** Returns the value associated with a key. */ public V get (K key) throws InvalidKeyException { int i; i = findEntry(key); // Call helper method to finding a key if ( i < 0 ) return null; // there is no value for this key, so return null return bucket[i].getValue(); // return the found value in this case }

Inserting into the Map

put(K key, V value):

Insert (key, value) in map if key "key" is not found
Return null
Otherwise, update the value of key "key" to the value value
Return the old value

put(K key, V value) method:

Deleting (removing) an entry from the Map

remove(K key):

remove(Key k) method:

/** -------------------------------------------------- Removes the key-value pair with a specified key. -------------------------------------------------- */ public V remove (K key) throws InvalidKeyException { int i; i = findEntry(key); // find this key first // i >= 0, then i = index of item with key k // i < 0, then (-i)-1 = index of first empty slot if ( i < 0 ) { // Item to delete is not in the map.... return null; // nothing to remove } V toReturn; toReturn = bucket[i].getValue(); // Save the old value to return bucket[i] = AVAILABLE; // mark this slot as deactivated n--; return toReturn; }

When the array become "too full": Increase array size

Fact:
Maintaining a low level of occupancy:

Caveat: hash function no longer works !

Note:

Changing the array size will change the compression function used !
And this in turn will change the hash function
The old hash function cannot be used to find the stored entries in a larger array !!!

Example:

Solution:
This operation is called re-hashing....

rehash() method:

protected void rehash() { Entry<K,V> e; int i, j, k; capacity = 2*capacity; // Double the array size Entry<K,V>[] old = bucket; // The old Map bucket = (Entry<K,V>[]) new Entry[capacity]; // the new map java.util.Random rand = new java.util.Random(); scale = rand.nextInt(prime-1) + 1; // new hash scaling factor shift = rand.nextInt(prime); // new hash shifting factor /* ---------------------------------------------- Re-hash every entry (loop through the array) ----------------------------------------------- */ for ( i = 0; i < old.length; i++) { e = old[i]; // Process new array element if ( (e != null) && (e != AVAILABLE) ) { // e is a valid entry (don't hash AVAILABLE :-)) k = findEntry(e.getKey()); // k = index of e.key in new array j = (-k) - 1; // k must be negative because key is new bucket[j] = e; // Put entry e at position j of new Map } } }

When to run a Rehash execution

The rehash operation is invoked when the insert (put) map operation detects that the map is "filling up"

Improved put(K key, V value):

public V put (K key, V value) throws InvalidKeyException { int i; HashEntry<K,V> oldValue; i = findEntry(key); //find the appropriate spot for this entry if ( i >= 0 ) // this key has an existing value { /* Replace existing value */ oldValue = (HashEntry<K,V>) bucket[i]).setValue(value); return (oldValue); // Return old value } /* ------------------------------------------------------- ******* Check for the need to RE-HASH ------------------------------------------------------- */ if ( n >= capacity/2 ) { rehash(); // rehash to keep the load factor <= 0.5 i = findEntry(key); // find again the appropriate spot for this entry } /* --------------------------------------------------------- **END** Check for the need to RE-HASH --------------------------------------------------------- */ /* --------------------------------------- Insert (new) entry in empty position --------------------------------------- */ bucket[(-i)-1)] = new HashEntry<K,V>(key, value); // (-i)+1 convert i to a proper index n++; // One more entry in Map return null; // there was no previous value, return null... }

Goodrich's implementation
- The Map implementation is here:
  - click here
- I have an edited version of his code here (I do not like his indentation):
  - click here
- The Map implementation needs a lot of other support classes
  Here is the directory where I have Goodrich code compiled (and ready to run):
- To use the Map.java implementation, you need to write these programs:
- Example Program: (Demo above code)
  - My Key class (String) Prog file: click here
  - My Value class (Integer) Prog file: click here
  - My Test Prog file: click here

Example using a Map: word frequency

Input:

WE hold these Truths to be self-evident, that all Men are created equal, that they are endowed by their Creator with certain unalienable Rights, that among these are Life, Liberty and the Pursuit of Happiness -- That to secure these Rights, Governments are instituted among Men, deriving their just Powers from the Consent of the Governed, that whenever any Form of Government becomes destructive of these Ends, it is the Right of the People to alter or to abolish it, and to institute new Government, laying its Foundation on such Principles, and organizing its Powers in such Form, as to them shall seem most likely to effect their Safety and Happiness. Prudence, indeed, will dictate that Governments long established should not be changed for light and transient Causes; and accordingly all Experience hath shewn, that Mankind are more disposed to suffer, while Evils are sufferable, than to right themselves by abolishing the Forms to which they are accustomed. But when a long Train of Abuses and Usurpations, pursuing invariably the same Object, evinces a Design to reduce them under absolute Despotism, it is their Right, it is their Duty, to throw off such Government, and to provide new Guards for their future Security. Such has been the patient Sufferance of these Colonies; and such is now the Necessity which constrains them to alter their former Systems of Government. The History of the present King of Great-Britain is a History of repeated Injuries and Usurpations, all having in direct Object the Establishment of an absolute Tyranny over these States. To prove this, let Facts be submitted to a candid World.

Output:

The most frequent word is "to," with word-count = 16.

Program:

public class WordCount { public static void main(String[] args) throws IOException { Scanner cin = new Scanner(System.in); cin.useDelimiter("[^a-zA-Z]"); // ignore non-letters HashTableMap<String,Integer> h = new HashTableMap<String,Integer>(); String word; Integer count; while ( cin.hasNext() ) { word = cin.next(); if (word.equals("")) continue; // ignore null strings between delimiters word = word.toLowerCase(); // ignore case count = h.get(word); // get the previous count for this word /* ************************************** Update count of word in Map ************************************** */ if ( count == null ) h.put(word, 1); // First occurence else h.put(word, ++count); // Increase count and update Map entry } /* ================================ Find most frequent word in input ================================ */ int maxCount = 0; String maxWord = "no word"; for ( Entry<String,Integer> ent : h.entrySet() ) { // find max-count word if ( ent.getValue() > maxCount ) { maxWord = ent.getKey(); // More frequent word found maxCount = ent.getValue(); } } System.out.print("The most frequent word is \"" + maxWord); System.out.println(",\" with word-count = " + maxCount + "."); } }

Example Program: (Demo above code)
- WordCount.java Prog file: click here
Program location: