Hashing: chaining, open addressing and rehashing

Hashing is the way to answer “is this key present?” in constant time on average. A BST does this in $O(\log n)$, a hash table in $O(1)$. Java’s HashMap and HashSet classes are built on it. A compiler’s symbol table, caches and database indexes all use hashing.

The question that comes up most often from this week in the exam: “Insert these keys into this table with this method, write the final table.” Whoever applies the method correctly gets full marks. Golden rules:

1. The home cell is $h(k) = k \bmod M$. Compute it for every key first and write it aside.
2. If there is a collision, look at the next cell according to the method’s formula. In the formula you always start from the home cell, not from the last cell tried.
3. Everything is mod M. You wrap around from the end of the table to the beginning.
4. In open addressing, deletion is lazy.
5. When the λ threshold is passed, rehash: a new size, new home cells.

Basic concepts

Hash function: converts a key to an index between 0 and M-1. A good hash function is fast to compute and spreads the keys evenly over the table. For integer keys the standard choice is $k \bmod M$ with M prime.

Why prime? If you choose M = 10, only the last digit matters; if most keys end in 0, they all fall into the same cell. A prime M mixes all the digits of the key.

For Strings Java uses this formula (computed with Horner’s method):

$h(s) = s_0 \cdot 31^{n-1} + s_1 \cdot 31^{n-2} + \dots + s_{n-1}$

System.out.println("ab".hashCode());   // 97*31 + 98
System.out.println("cat".hashCode());
System.out.println("act".hashCode());

3105
98262
96402

If you only added the character codes, “cat” and “act” would both give 312. Multiplying by 31 takes the order of the letters into account.

PITFALL · negative hashCode. For long Strings the sum does not fit in an int and overflows, so hashCode() can be negative. h % M is then negative too and the array index blows up. Even Math.abs(h) % M is not safe: Math.abs(Integer.MIN_VALUE) is still negative. The correct way is Math.floorMod(h, M).

Collision: two different keys fall into the same cell. Since M is smaller than the number of possible keys, collisions are unavoidable. The question is how you resolve them.

Load factor: $\lambda = n / M$. This is the single number that determines performance.

We will use the same keys in all examples on this page:

M = 11
key      27  18  29  28  39  13  16
k mod 11  5   7   7   6   6   2   5

Separate chaining

Each cell holds a linked list. Keys that fall into the same cell are added to that list. We add the new key to the front of the list ($O(1)$).

0: -
1: -
2: 13
3: -
4: -
5: 16 -> 27
6: 39 -> 28
7: 29 -> 18
8: -
9: -
10: -

Search: go to the home cell and scan that list. Since the average list length is λ, an unsuccessful search examines λ elements on average, and a successful search about $1 + \lambda/2$. In chaining, λ around 1 is reasonable; λ > 1 also works but gets slower. Deletion is easy: remove it from the list.

Open addressing

There are no lists; the keys sit directly in the array. On a collision, an empty cell is searched with a probe sequence: $h_0, h_1, h_2, \dots$ Here $\lambda \le 1$ is required, and in practice $\lambda \le 0.5$ is the target.

Linear probing

$h_i(k) = (h(k) + i) \bmod M$

If it is full, look one to the right. The trace of the example table (in parentheses: the number of cells examined):

27 -> 5                    (1)
18 -> 7                    (1)
29 -> 7x 8                 (2)
28 -> 6                    (1)
39 -> 6x 7x 8x 9           (4)
13 -> 2                    (1)
16 -> 5x 6x 7x 8x 9x 10    (6)

idx: 0  1  2  3  4  5  6  7  8  9  10
key: -  -  13 -  -  27 28 18 29 39 16

A single full block formed from 5 to 10. Every new key that falls into the block is added at its end and the block grows further. This is called primary clustering. It is the biggest weakness of linear probing: the home cell of 16 was 5 but it visited 6 cells.

Expected probe counts:

When λ rises to 0.9, an unsuccessful search visits 50 cells on average. That is why the rehash threshold exists.

Quadratic probing

$h_i(k) = (h(k) + i^2) \bmod M$

In order: home + 0, +1, +4, +9, +16, … It moves away from the cluster quickly.

27 -> 5
18 -> 7
29 -> 7x 8          (7+1)
28 -> 6
39 -> 6x 7x 10      (6+1, 6+4)
13 -> 2
16 -> 5x 6x 9       (5+1, 5+4)

idx: 0  1  2  3  4  5  6  7  8  9  10
key: -  -  13 -  -  27 28 18 29 16 39

This time 16 was placed in 3 probes. Primary clustering goes away, but keys that fall into the same home cell still follow the same path: secondary clustering.

PITFALL · in quadratic probing, i² is added to the home cell. For 39, the second attempt is 7, and the third attempt is not 7 + 4 = 11 but 6 + 4 = 10. Each attempt is $h(k) + i^2$; it is not added to the previous attempt.

Why M prime and λ ≤ 0.5? If M is not prime, $i^2 \bmod M$ takes few different values. For M = 16, the cells reachable from home cell 0 are only {0, 1, 4, 9}. Even when the table is half empty, a place may not be found. If M is prime, the first $\lceil M/2 \rceil$ attempts always fall in different cells; if the table is at least half empty, an empty cell is certainly reached.

Double hashing

$h_i(k) = (h(k) + i \cdot h_2(k)) \bmod M, \qquad h_2(k) = R - (k \bmod R)$

R is a prime smaller than M. Since the step size depends on the key, two keys that fall into the same home cell follow different paths; secondary clustering goes away too. $h_2$ must never be 0 (otherwise it stays in place); $R - (k \bmod R)$ is between 1 and R, so it is safe.

With R = 7:

key  h  h2  path
27   5  1   5
18   7  3   7
29   7  6   7x 2      (7+6=13, mod 11 = 2)
28   6  7   6
39   6  3   6x 9
13   2  1   2x 3      (29 is at 2)
16   5  5   5x 10

idx: 0  1  2  3  4  5  6  7  8  9  10
key: -  -  29 13 -  27 28 18 -  39 16

Note: 29 being placed at 2 pushed 13, whose home cell is 2, aside later. Do not mix up the order; insert the keys in the given order.

Deletion: lazy deletion

In the linear table we want to delete 29 (index 8). If we empty the cell, searching for 39 breaks: the path of 39 is 6 → 7 → 8 → 9. The search sees an empty cell at 8, says “39 is absent” and stops. Yet 39 is at index 9.

The solution: put a DELETED mark on the cell.

idx: 0  1  2  3  4  5  6  7  8  9  10
key: -  -  13 -  -  27 28 18 D  39 16

• Search passes over DELETED as if it were full: for 39, 6, 7, 8, 9 → 4 cells, found.
• Insertion can use DELETED as if it were empty: for 50 (h = 6), 6 and 7 are full, 8 is DELETED → 50 is written there.

If there are many deletions, DELETED cells pile up and searches get longer; rehashing cleans these up too. This problem does not exist in chaining; the node is just removed from the list.

Rehashing

When the λ threshold is passed, a larger table is opened (usually the first prime above 2M) and every key is hashed again with the new M. Copying to the old indexes is wrong, because $k \bmod M$ has changed.

M = 7, linear probing, rehash if λ > 0.5 after an insertion:

insert 10  λ=0.143  3:10
insert 3   λ=0.286  3:10 4:3
insert 17  λ=0.429  3:10 4:3 5:17
insert 24  λ=0.571  3:10 4:3 5:17 6:24  -> rehash
new M = first prime >= 14 = 17
10 -> 10   3 -> 3   17 -> 0   24 -> 7
0:17 3:3 7:24 10:10

In the old table the four keys had formed a cluster between 3 and 6; in the new table there is no collision at all. Rehashing takes $O(n)$ but happens rarely. Since the size doubles each time, the amortized cost per insertion stays $O(1)$. Java’s HashMap doubles its capacity by default when λ > 0.75.

Which method when?

A hash table does not know order. For jobs like “print the keys in sorted order”, “the smallest key”, “the keys between 10 and 20”, choose a BST or AVL.

Common mistakes

System.out.println("ab".hashCode());
System.out.println("cat".hashCode() == "act".hashCode());

static int insert(int[] table, int key) {
    int M = table.length;
    int h = key % M;
    for (int i = 0; i < M; i++) {
        int p = (h + i) % M;
        if (table[p] == -1) {
            table[p] = key;
            return p;
        }
    }
    return -1; // table is full
}