Hashing basics

An array finds a value in O(1) when you know its index. A hash table gives *any* key an index: a **hash function** turns the key into a number, and the number modulo the table size is the **bucket** where the key's entry lives. Looking up a key repeats the same computation and goes straight to that bucket instead of scanning.

A map stores key-value pairs; a set stores keys only. Both use the same machinery. In the animation, add keys to a table of 5 buckets with key % 5 and watch where each one lands, then search with ?22 and remove with -7.

1class ChainedHashSet {
2    private final int m, variant, a;                                // m buckets
3    private final LinkedList<Integer>[] table;                      // one chain per bucket
4    int hash(int key) {                                             // the option picks one variant
5        switch (variant) {
6            case 0: return Math.floorMod(key, m);
7            case 1: return (int) (m * ((key * 0.6180339887) % 1.0));
8            case 2: return 0;                                       // worst case: every key collides
9            default: return ((a * key + 7) % 101) % m;              // universal-style family
10        }
11    }
12    boolean add(int key) {
13        LinkedList<Integer> chain = table[hash(key)];
14        if (chain.contains(key)) return false;                      // walk the chain: duplicate
15        chain.add(key); return true;                                // append to the chain
16    }
17    boolean contains(int key) { return table[hash(key)].contains(key); }
18    boolean remove(int key) { return table[hash(key)].remove((Integer) key); }
19}

A good hash function is **deterministic** (the same key always gives the same number), **fast**, and **uniform** (keys spread evenly over the buckets). The simplest function for integers is key % m. For strings Java uses a polynomial: s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1], computed in int arithmetic that silently overflows and wraps.

Other ideas: the multiplicative method floor(m * frac(k * A)) with A ≈ 0.618 (the golden ratio) scrambles patterns in the keys, and universal hashing picks the function at random from a family. The animation lets you choose between key % m, the multiplicative method, a constant function and a universal-style function.

1static int stringHash(String s) {
2    int h = 0;
3    for (int i = 0; i < s.length(); i++) h = 31 * h + s.charAt(i);   // overflow wraps; that is intended
4    return h;                                                         // same as s.hashCode()
5}

A bucket is one slot of the table's array. It may hold nothing, one entry, or several entries when keys collide. Java's HashMap uses an array whose length is always a power of two, so the bucket index is (n - 1) & hash instead of a slow division, and it first mixes the high bits into the low bits with h ^ (h >>> 16) so that keys differing only in their high bits do not all land in one bucket.

For "hello" the hash is 99162322; after the spread step it is 99163451, and in a 16-bucket table it lands in bucket 11.

1static int bucketIndex(Object key, int tableLength) {                // tableLength is a power of two
2    int h = key.hashCode();
3    int spread = h ^ (h >>> 16);                                     // mix high bits into low bits
4    return spread & (tableLength - 1);                               // same as floorMod(spread, tableLength)
5}

Every Java object has hashCode(). The contract has three rules: it returns the same value while the object's equality-relevant fields do not change; **if two objects are equal by equals, they must have the same hash code**; and unequal objects may share a hash code (it is only a hint). The second rule is the one that matters for hash tables, because a lookup goes to one bucket only.

If you override equals but not hashCode, two equal objects get different identity-based hashes and usually land in different buckets, so the table cannot find them. With a class BadPoint that overrides only equals, new BadPoint(1, 2).equals(new BadPoint(1, 2)) is true, yet after set.add(new BadPoint(1, 2)), set.contains(new BadPoint(1, 2)) is false. Adding hashCode fixes it.

1static final class Point {
2    final int x, y;
3    Point(int x, int y) { this.x = x; this.y = y; }
4    @Override public boolean equals(Object o) { return o instanceof Point p && p.x == x && p.y == y; }
5    @Override public int hashCode() { return Objects.hash(x, y); }          // must be consistent with equals
6}

equals must be an equivalence relation: **reflexive** (x.equals(x)), **symmetric** (x.equals(y) iff y.equals(x)), **transitive**, **consistent** (same answer while nothing changes) and x.equals(null) is false. A hash table relies on it to decide, inside a bucket, which entry is *the* key.

The signature matters: equals(Object), not equals(Point). A method boolean equals(Point p) overloads instead of overriding, so collections never call it. Annotate with @Override and the compiler catches this.

1static final class Pair {
2    final int a, b;
3    Pair(int a, int b) { this.a = a; this.b = b; }
4    @Override public boolean equals(Object o) {              // the parameter type must be Object
5        if (this == o) return true;
6        if (!(o instanceof Pair)) return false;               // also handles null
7        Pair p = (Pair) o;
8        return a == p.a && b == p.b;
9    }
10    @Override public int hashCode() { return 31 * a + b; }
11}

The speed of a hash table depends on how evenly keys fill the buckets. With m buckets and n keys spread perfectly, every bucket has n/m keys and a lookup scans about that many entries. A poor function piles keys into a few buckets and the table degrades toward a linked list.

Compare presets in the animation with the keys 10, 20, 30, 40, 50 and 5 buckets: with key % 5 every key lands in bucket 0 (all are multiples of 5), but the multiplicative function spreads them. The data matters as much as the function: keys that share a factor with the table size are the classic trap, and one reason to use prime sizes or to mix bits first.

1class ChainedHashSet {
2    private final int m, variant, a;                                // m buckets
3    private final LinkedList<Integer>[] table;                      // one chain per bucket
4    int hash(int key) {                                             // the option picks one variant
5        switch (variant) {
6            case 0: return Math.floorMod(key, m);
7            case 1: return (int) (m * ((key * 0.6180339887) % 1.0));
8            case 2: return 0;                                       // worst case: every key collides
9            default: return ((a * key + 7) % 101) % m;              // universal-style family
10        }
11    }
12    boolean add(int key) {
13        LinkedList<Integer> chain = table[hash(key)];
14        if (chain.contains(key)) return false;                      // walk the chain: duplicate
15        chain.add(key); return true;                                // append to the chain
16    }
17    boolean contains(int key) { return table[hash(key)].contains(key); }
18    boolean remove(int key) { return table[hash(key)].remove((Integer) key); }
19}

A **collision** is two different keys mapping to the same bucket. It cannot be avoided: with more possible keys than buckets, the pigeonhole principle forces it, and even with few keys collisions appear surprisingly early (the birthday paradox: 23 random keys in 365 buckets have a better than even chance of at least one collision).

So every hash table needs a **collision strategy**. The two families are separate chaining (each bucket holds a list of entries) and open addressing (a colliding key is stored in another slot of the array). The next lesson covers both.

1class ChainedHashSet {
2    private final int m, variant, a;                                // m buckets
3    private final LinkedList<Integer>[] table;                      // one chain per bucket
4    int hash(int key) {                                             // the option picks one variant
5        switch (variant) {
6            case 0: return Math.floorMod(key, m);
7            case 1: return (int) (m * ((key * 0.6180339887) % 1.0));
8            case 2: return 0;                                       // worst case: every key collides
9            default: return ((a * key + 7) % 101) % m;              // universal-style family
10        }
11    }
12    boolean add(int key) {
13        LinkedList<Integer> chain = table[hash(key)];
14        if (chain.contains(key)) return false;                      // walk the chain: duplicate
15        chain.add(key); return true;                                // append to the chain
16    }
17    boolean contains(int key) { return table[hash(key)].contains(key); }
18    boolean remove(int key) { return table[hash(key)].remove((Integer) key); }
19}