Topic 7 – Hash Table


Hash Table

Hash Table
Linear Probing

Hash Function¶

Separate Chaining¶

Use an array of $M$ < $N$ linked lists. [H. P. Luhn, IBM 1953]

• Hash: map key to integer $i$ between 0 and $M$ - 1.
• Insert: put at front of $i$th chain (if not already there).
• Search: need to search only $i$th chain.

Linear Probing¶