Skip to content

Hash Tables

A hash table maps keys to array positions. Since distinct keys may map to the same position, every implementation needs a collision strategy.

Contract

For Java hash-based collections, equal objects must have equal hash codes:

a.equals(b)  implies  a.hashCode() == b.hashCode()

The converse is not required. Collisions are valid and must be resolved. Mutable keys are dangerous: changing equality-relevant state after insertion can make an entry unreachable through ordinary lookup.

Collision strategies

  • Separate chaining: each bucket stores multiple entries.
  • Open addressing: colliding entries probe other slots; deletion requires a careful marker or rearrangement policy.

The load factor relates stored entries to available buckets. Resizing keeps the expected chain or probe length controlled, at the cost of occasional Θ(n) rehashing.

Complexity

Lookup, insertion, and removal are expected O(1) under an effective hash distribution and controlled load factor. A worst case can be linear. Java implementations may use additional collision defenses, but client code should still implement correct and well-distributed hashing.

A value key

record Coordinate(int row, int column) {}

Map<Coordinate, String> labels = new HashMap<>();
labels.put(new Coordinate(2, 3), "target");

Records derive value-based equality and hashing from their components, making this immutable record suitable as a key.

Exercises

  1. Explain why a constant hash code is correct but inefficient.
  2. Compare separate chaining with linear probing under high load.
  3. Design equality for a case-insensitive identifier.