Cleanest way to represent three states, where one can hold a Key/Value pair, and the other two are empty markers

Question

I'm writing a Hash Table that uses linear probing to resolve collisions.

I looked over how linear probing works, and it seems like to allow for deletions, I can't simply remove an element, since that may prevent a previously-collided element from being found post-deletion (since searching ends on an unoccupied cell).

I thought of wrapping the Key,Value pair in a class that just represents a state. 2 of the 3 states (say, Deleted and UnOccupied) are just acting as "markers"; they don't hold anything. The third state however (Occupied) needs to hold the pair.

The goal of this is to differentiate between cells that have always been empty, and cells that have have data previously deleted from them.

To illustrate what I wanted to do, if I were writing this in Haskell, I'd set it up as:

data CellState k v = Occ k v | Deleted | UnOcc

Then I'd just need to pattern match against it to tell what the state of the cell is, and easily extract the pair if the cell is occupied.

I have to write this in Java though. I started writing up a set of classes for the 3 states that all inherit from a base class CellState, but then I thought it through, and I'm not sure how I would even use it since pattern-matching isn't supported in Java.

My second idea was to define 1 class that has key and value fields, and has a enumerated State field, with "getters" that can be used to check what the state of the cell is. If the user attempts to "get" from a CellState that isn't occupied, an exception would be thrown (similar to the behavior of Optional). The user could then use either an if-tree, or a switch to act on the cell based on its internal state.

The second idea seems more imperitive-styled, but still seems clumsy. This also allows for the possibility of an inconsistent state where a key and value are available, but it's marked as non-Occupied, or where it's marked as Occupied, but doesn't contain a pair. This isn't possible in the "Haskell solution".

By the way, this is for homework, so I can't simply not use linear probing, since that is an assignment requirement.

Is there a better way to go about doing this?

Answer 1

Linear Probing is inherently restricted and has sub-optimal performance, and there's no good way around those problems. The only good uses for linear probing hash tables is when you are in a memory-restricted environment and cannot perform any allocations, or when you have a perfect hash function and can therefore know that no collisions will arise.

If you really have to provide deletion, then your ternary approach makes sense. In Java, we would use null for a free bucket, and the state of the bucket to mark it as occupied or deleted. E.g.:

class Bucket<K, V> {
  K key;
  V value;
  boolean occupied;
  Bucket(K key, V value) {
    this.key = key;
    this.value = value;
    occupied = true;
  }
  void free() {
    key = value = null;
    occupied = false;
  }
}

Bucket<K, V> buckets[] = ...;

V get(K key) {
  int i = hash(key);
  for (; i < buckets.length; ++i) {
    Bucket b = buckets[i];
    if (b == null) break;
    if (b.occupied && b.key == key) return b.value;
  }
  throw ...;
}

void delete(K key) {
  int i = hash(key);
  for (; i < buckets.length; ++i) {
    Bucket b = buckets[i];
    if (b == null) break;
    if (b.occupied && b.key == key) b.free();
  }
}

An alternative would be to have each bucket link to the next bucket with the same hash, which is effectively a pre-allocated linked list. Note that each Bucket needs two pointers: one to the next bucket for the same hash as this entry, and one to the start of the list for the hash of this bucket – which is needed since when a bucket is filled, the entry may belong to a different list and not to this hash. Actually, this isn't using open addressing any more. It has the capacity restrictions of open addressing since each bucket can only hold one value, but all other properties are equivalent to the linked-list technique of collision resolution.

Example of structure:

hashTable.put("a", 1) // hash(a) = 1
hashTable.put("b", 1) // hash(b) = 1
hashTable.put("c", 2) // hash(c) = 2
hashTable.put("d", 1) // hash(d) = 1
hashTable.put("e", 3) // hash(e) = 3

// 0: start: / next: 3 key: "b" value: 1
// 1: start: 1 next: 0 key: "a" value: 1
// 2: start: 2 next: / key: "c" value: 2
// 3: start: 4 next: / key: "d" value: 1
// 4: start: / next: / key: "e" value: 3

Algorithms sketch:

class Bucket<K, V> {
  K key = null;
  V value = null;
  Bucket<K, V> next = null;
  Bucket<K, V> start = null;
}

Bucket<K, V> buckets[] = ...;
// initialize buckets[] with empty buckets

V get(K key) {
  Bucket<K, V> b = buckets[hash(key)].start;
  for (; b != null; b = b.next) {
    if (b.key == key) return b.value;
  }
  throw ...;
}

void put(K key, V value) {
  Bucket<K, V> b = buckets[hash(key)];

  // case: first item in bucket
  if (b.start == null) {
    b.key = key;
    b.value = value;
    b.start = b;
    return;
  }

  // find bucket with key
  Bucket<K, V> p = null;
  b = b.start;
  for (; b != null; p = b, b = b.next) {
    // overwrite entry
    if (b.key == key) {
      b.value = value;
      return;
    }
  }

  // enter a new bucket into this list:
  b = getNextFreeBucket();
  p.next = b;
  b.key = key;
  b.value = value;
}

void delete(K key) {
  Bucket<K, V> p = null;
  Bucket<K, V> b = buckets[hash(key)].start;
  for (; b != null; p = b, b = b.next) {
    if (b.key == key) {
      b.key = null;
      b.value = null;
      if (p != null) p.next = b.next;
      b.next = null;
      return;
    }
  }
}

Answer 2

Cocoa NSDictionary uses an array containing hash values (which is useful anyway, because that way looking up a key doesn't require calculation of any hash code except the one of the key that is looked up), with two special hash values reserved to indicate an unused and a previously used cell. These special values are not constants but stored in the hash table. If you try to add a key/value pair where the hash code matches one of these two special values (which would be very, very rare), the code picks two other special values randomly until it picks two that are not used in the hash table, then replaces all the special values.

I don't know how good this approach is, but it is used by any single application on about a billion devices, so it better be good.

Answer 3

1. I have my doubts about the occupied vs deleted tracking.

   Perhaps you should instead move elements coming after the deleted element one down, similar to what you do when deleting in the middle of an array like collection. To determine how many elements you need to delete you could use a similar condition as you use to determine when the linear scan in finished.

2. To implement your first approach (different classes), I see several possible ways to replace pattern matching:

   • Add a method abstract State getState() where state is an enum to the base class which you then override in the derived classes. Then you can switch on its result.
   • The instanceof operator
   • Since the special values are stateless, you could create canonical instances and compare with them (reference equality works).

   The first of these is the proper OOP approach, so it's probably the best choice for a homework assignment.

3. As a variant of your second approach, one could switch column-major-order. That way you don't need to allocate an object per slot, only a few per collection.

   Something like

   public class Dictionary<K, V>
   {
       K[] keys;
       V[] values;
       State[] states;
   }
   

   But I wouldn't use this approach in a homework assignment. The potential performance gain isn't worth the complexity.

Instead of scanning through the array, I'd rather keep a linked list (containing slot indices) for each bucket and a linked list for the free slots. Much simpler and better performance. But if the homework requires the dumb approach, it can't be helped.