1

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?

  • Does the homework assignment explicitly require the deletion operation? If it does not, then I wouldn't implement it. My experience with homework assignments is that you should implement a solution that fulfills the stated requirements and nothing more. – CodesInChaos Jun 28 '15 at 21:06
  • @CodesInChaos Nope, the only capability it requires is additions. I was going to go full keener, but I guess this may be the reason they don't require deletions. – Carcigenicate Jun 28 '15 at 21:08
2

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;
    }
  }
}
  • Thanks. The second part won't work because (as I just edited into the question; sorry), I'm required to use linear probing. I like your Bucket class solution with the occupied flag though. I'm trying to get away from using null though, so I think I'll represent the 3 states as Optional.empty() for an unoccupied cell, and a deleted flag field inside of the cell to represent a cell that's been previously deleted. One last concern, with this method, should I worry about the possibility of an inconstant state (as I just edited into the bottom of the question)? Thanks. – Carcigenicate Jun 28 '15 at 20:20
  • Oh, and what do you mean by my "Ternary approach"? – Carcigenicate Jun 28 '15 at 20:27
  • @Carcigenicate Is there a specific reason why you're "required" to use linear probing? – Ixrec Jun 28 '15 at 20:32
  • @lxrec As noted in the question, it's a homework requirement. – Carcigenicate Jun 28 '15 at 20:34
  • @Carcigenicate Using Optionals gives no advantage for such a low-level problem. Invalid states can only occur of you make a mistake in implementation, but you can facilitate correctness by encapsulating the Bucket structure and only manipulating its state through methods – which doesn't make it foolproof, but makes it harder to do stupid things. You could lift the state into the type system, but that would seem to be unneeded complication. I called your approach ternary since it involved three states. “Ternary” means “composed of three items”, see also “binary”, “unary”, “n-ary”. – amon Jun 28 '15 at 21:31
1

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.

  • Unless I'm mis-interpreting your answer, I can't use this. I am required to use linear probing. – Carcigenicate Jun 28 '15 at 20:45
  • @Carcigenicate This optimization can be used even with linear scanning. It corresponds to your second approach, but uses the same field to represent special values and something that's useful (the cached hash) if the slot contains an element. It's not a bad idea, but IMO an unnecessary complication for a homework problem. – CodesInChaos Jun 28 '15 at 20:47
  • Given the homework doesn't require the ability to delete, I'm think of just saying screw it. I was going to go full "keener" and make a decent full Hash Table, but simply allowing for deletions seems to complicate the code beyond what I want to devote to the question :/ – Carcigenicate Jun 28 '15 at 20:52
1
  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.

  • Thanks, as I mentioned in the comments though, wouldn't 1. break the Hash Table? If they're placed based on their hash, and I start moving things around, they'll no longer map to the correct value. And 2.a seems to be generally the agreed upon way of doing it. One problem I see though, doesn't that allow for an inconsistent state? With the "Haskell approach", that's impossible since an UnOcc can't even hold values. With this approach though, theoretically, the stored state could incorrectly report whether or not a value is available. Do I need to just minimize the risk via get/setters? – Carcigenicate Jun 28 '15 at 20:50
  • 1
    @Carcigenicate Only the Occupied class would contains those fields, so you can't get an invalid state. If the base class were public, somebody might be able to create a contract violating derived class, but there are workarounds for that (like internal constructors, which would prevent instantiation of other derived classes). You can make these classes immutable if you want, only accepting values via the constructor and not having setters. – CodesInChaos Jun 28 '15 at 20:54
  • Whoops, I misunderstood. Ya, that would work then. So basically, I'd just be matching against the returned State instead of the class itself using instanceOf. – Carcigenicate Jun 28 '15 at 20:57
  • Yes. AFAIK that's also the way F# implements discriminated unions, since it has to compile to the .NET type system, which is similar to java. – CodesInChaos Jun 28 '15 at 21:00
  • @Carcigenicate 1) Concerning the moving you must use the proper condition to figure out how many elements to use. All elements in the same buckets and elements of subsequent buckets displaced by it. 2) I suspect your non moving approach doesn't actually work. Since if you place a new value in that slot, with the new element coming from a higher bucket, this new element would disrupt the linear scan of the lower bucket extending beyond it. So implementing move-on-delete seems to be necessary with linear scan. – CodesInChaos Jun 28 '15 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.