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