Addressing

Overview

Direct

Given a universe of keys $U=\{0,1,\dots ,m-1\}$, a direct-address table has $m$ slots. Each slot corresponds to a key in universe $U$.

Closed

In closed addressing, a key is always stored in the bucket it’s hashed to. Collisions are dealt with using separate data structures on a per-bucket basis.

Ideal Hashing

An independent uniform hash function is the ideal theoretical abstraction. For each possible input $k$ in universe $U$, an output $h(k)$ is produced randomly and independently chosen from range $\{0,1,\dots ,m-1\}$. Once a value $h(k)$ is chosen, each subsequent call to $h$ with the same input $k$ yields the same output $h(k)$.

Chaining

The most common form of closed addressing is chaining. In this scheme, each slot $j$ is a (nullable) pointer to the head of a linked list containing all the elements with hash value $j$.

Open

In open addressing, keys always reside in the hash table. Collisions are dealt with by searching for other empty buckets within the hash table.

Sequential examination of slots during dictionary operations is called probing. Given hash function $h$, the probe sequence refers to the sequence $⟨h(k,0),h(k,1),\dots ,h(k,m-1)⟩$ visited when probing. Every probe sequence is expected to be a permutation of $⟨0,1,\dots ,m-1⟩$.

Ideal Hashing

An independent uniform permutation hash function is the ideal theoretical abstraction in open addressing. The probe sequence of each key is equally likely to be any of the $m!$ permutations of $⟨0,1,\dots ,m-1⟩$.

Bibliography

• “Hash Tables: Open vs Closed Addressing | Programming.Guide,” accessed June 12, 2024, https://programming.guide/hash-tables-open-vs-closed-addressing.html.
• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).