A hash table in Java with 64-bit hash codes

On the previous pages, we created a 64-bit hash function. We can now use this to create a hash map in which we will not store the key objects, but only the hash codes of the keys and the values the corresponding keys are mapped to.

In principle, the procedure is as follows— note the structural similarity with the standard Java HashMap implementation:

One way of implementing this would be to essentially follow the structure of the standard Java HashMap implementation, with each bucket consisting of a list of "entry" objects, à la HashMap.Entry, encapsulating each (hash code, value) pair. In the example implementation here, we will favour the approach used by the Numerical Recipes authors of essentially "rolling our own" object allocation. The approach is as follows:

In our example, we'll write a CompactHashMap class that maps CharSequences to objects of a given type. We'll also make our class generic:

public class CompactMap<E> {
  private int[] table;
  private int[] nextPtrs;
  private long[] hashValues;
  private E[] elements;
  private int nextHashValuePos;
  private int hashMask;

  public CompactMap(int maxElements) {
    int sz = 128;
    int desiredTableSize = maxElements * 4 / 3;
    while (sz < desiredTableSize) sz <<= 1;
    this.table = new int[sz];
    this.nextPtrs = new int[maxValues];
    this.hashValues = new long[maxValues];
    this.elements = (E[]) new Object[sz];
    Arrays.fill(table, -1);
    this.hashMask = sz-1;
  }

  public E get(CharSequence key) {
    ...
  }
  public E put(CharSequence key, E value) {
    ...
  }
}

The potential advantage of structuring the data in this way is that it is less "object heavy" than the standard Java implementation. This probably will put less strain on the garbage collector for relatively large maps that stay around in memory for most of the lifetime of the application (which is a typical use of hash maps). For small, temporary maps, Java's use of small objects may actually be beneficial, but we leave it as a future exercise to test this hypothesis.

On the next page we look at how to implement the get() and put() methods.