A hash table in Java with 64-bit hash codes (ctd)

Continuing our compact hash map implementation, we turn to the get() and set() methods.

get() method

We'll start by looking at how to implement the get() method, because this is more straightforward than the put() method and will help us envisage more clearly how the fields are used. The first stage is to take the relevant number of bottom bits of the hash code of the key. We do this by ANDing the 64-bit hash code with the "hash mask" that we set up in our initialiser, resulting in the "bucket" index (index into the table array). We then query this table for the pointer, k, to the start of the bucket: i.e. the index of hashValues/elements that represents the first entry in that bucket. If no item has yet been added to that bucket, this value will be -1 and we simply return null. Otherwise, we compare the hash value of the first element of the "bucket" (i.e. hashValues[k]); if it matches the hash of the key we are looking for, then we return the corresponding value, e.g. elements[k]. Otherwise, we query nextPtrs, which gives us the index of hashValues/elements representing the next item in the bucket:

public E get(CharSequence key) {
  long hash = DataHasher.hashCode(key);
  int hc = (int) hash & hashMask;
  int k = table[hc];
  if (k != -1)
    do {
      if (hashValues[k] == hash)
        return elements[k];
      k = nextPtrs[k];
    } while (k != -1);
  return null; // No value added at this bucket
}

put() method

At first glance, the put() method seems slightly more involved, but it is essentially setting up the structure expected by the get() method presented. We also return the previous value mapped to by the key in question, as this is sometimes useful and it is more efficient to retrive the old value as we are adding the new one.

public E put(CharSequence key, E val) {
  long hash = DataHasher.hashCode(key);
  int hc = (int) hash & hashMask;
  int k = table[hc];
  if (k == -1) {
    // Start a new bucket: none there before
    k = nextHashValuePos++;
    table[hc] = k;
  } else {
    // traverse the bucket, looking for a matching hash
    int lastk;
    do {
      if (hashValues[k] == hash) {
        E old = elements[k];
        elements[k] = val;
        return old;
      }
      lastk = k;
      k = nextPtrs[k];
    } while (k != -1);
    // ... if not there, append to end of bucket
    k = nextHashValuePos++;
    nextPtrs[lastk] = k;
  }
  // Append value, either to end of bucket or
  // to start of new bucket
  hashValues[k] = hash;
  nextPtrs[k] = -1;
  elements[k] = val;
  size++;
  return null;
}