Chaining: Basic Idea

Keep a linked list in each ``slot'' of the table.

If two keys hash to the same slot, stick them both on the list for that slot.

• Insert(k): $T[h(k)] \leftarrow T[h(k)] : k$
• Delete(k): $T[h(k)] \leftarrow \mbox{remove}(k, T[h(k)])$
• Find(k): $\mbox{assoc}(k,T[h(k)])$.

Note: ispell and perl use this scheme.