Collisions and Open Addressing

Load Factor

If a hash table has m slots and contains n elements, $\alpha = n / m$ is its load factor.

When too many elements are stored and the load factor $\alpha$ grows too large, lookup efficiency decreases. For open addressing, a practical maximum load factor is generally chosen within $0.5 \le \alpha \le 0.85$. When the load becomes too high, one solution is to double the table size. This process is called rehashing.

Rehashing traverses the original table and hashes every key into a new array. Why must the keys be hashed again? Increasing the length changes the hashing rule. After expansion, a crowded table becomes sparse again, and the existing keys are redistributed as uniformly as possible.

Load factor is also one of the factors influencing collisions. When different keys map to the same hash address, a collision occurs: $h(key_i) = h(key_j),\ key_i \ne key_j$. A collision-resolution strategy is therefore needed.

For example, consider the 12 objects {18, 23, 11, 20, 2, 7, 27, 30, 42, 15, 34, 35}. The table size is 17, and the hash function is h(key) = key % size.

No collisions occur before the final key, 35, is inserted. But h(35) = 1, and that position is already occupied, causing a collision.

Two common approaches resolve collisions:

1. Open addressing: after a collision, follow a rule to find another empty address. Common methods include linear probing, quadratic probing, and double hashing.

2. Separate chaining: store all keys that collide at the same position in a singly linked list.

Linear Probing

After a collision, probe cyclically with offsets 1, 2, 3, ..., N - 1, where N is the table length.

For the sequence {47, 7, 29, 11, 9, 84, 54, 20, 30}, use a table of length 13, h(key) = key % 11, and linear probing to resolve collisions.

Linear probing

Linear probing has the drawback of forming clusters.

Quadratic Probing

Quadratic probing uses the alternating offsets $1^2, -1^2, 2^2, -2^2, \dots, q^2, -q^2\ (q \le \lfloor N/2 \rfloor)$ to probe cyclically for another address.

For the sequence {47, 7, 29, 11, 9, 84, 54, 20, 30}, use a table of length 11, h(key) = key % 11, and quadratic probing to resolve collisions.

Quadratic probing

Does quadratic probing always find an empty position whenever space remains?

For the following table, insert key 11 with h(key) = key % 5 and quadratic probing.

Quadratic probing for key 11 keeps oscillating among indices 0 and 2 and never reaches the other empty positions.

A theorem shows that if the table length is a prime of the form $4k + 3\ (k \in Z^+)$, this quadratic-probing sequence can visit the entire table.

Double Hashing

Define another hash function $h_2(key)$ and use the probe offsets $h_2(key),\ 2h_2(key),\ 3h_2(key), \dots$.

The probe sequence should be able to visit every storage slot. The following form works well: