Chaining, Universal Hashing & Search Complexity Under Load

Under Simple Uniform Hashing, any key is equally likely to hash into any of the m slots, independently of other keys.

1. Unsuccessful Search:

The search traverses the entire linked list at slot h(k). The expected length of this list is the load factor alpha = n / m. Including the O(1) time to compute the hash function:

E[text{Cost}] = Theta(1 + alpha).

2. Successful Search:

The expected number of elements examined is 1 plus the expected number of elements inserted into the list after key x. On average, this is alpha / 2:

E[text{Cost}] = Theta(1 + alpha / 2).

In open addressing under the assumption of uniform hashing (each probe is equally likely to be any unoccupied slot):

- Unsuccessful Search: The probability that the first probe is occupied is alpha. The probability that the first two probes are occupied is alpha^2. Total expected probes:

E[P] = 1 + alpha + alpha^2 + alpha^3 + ... = frac{1}{1 - alpha}.

- Successful Search: Each key was inserted when the load factor was smaller. Integrating over the history yields:

E[P] = frac{1}{alpha} ln frac{1}{1 - alpha}.