Resolving Collisions

Open Addressing (rehashing): each position of the array is either EMPTY, DELETED, or OCCUPIED.

To insert V:

1. compute position P = H(key(V)).
2. if P is not OCCUPIED, store V there.
3. else, compute another position P and repeat steps 2-3.

How to compute another position?

Linear Probing:

P = (1 + P) mod TABLE_SIZE