• collisions occur when $h(k_1) = h(k_2)$
• in an ideal world we have some collision-free hash function
  • in practice, this is very difficult to design
  • thus, we assume collusions will occur, introducing the need for collision management strategies

Chaining — multiple items in one slot? store in a Doubly Linked List

Open Addressing — item already in slot? find the next available one

Load Factor $(\alpha)$ — $\frac{n}{m}$ where $n$ is the number of keys, and $m$ is the number of slots

Chaining

Open Addressing

Table Resizing