Expected Hash Table Lookup Complexity

Assume a good hash function spreads keys evenly and the load factor is kept bounded.

Think about the expected size of a single bucket's chain under these assumptions.

1. 1. State the standard assumptions

   Assuming simple uniform hashing and a load factor (elements per bucket) bounded by a constant, each bucket holds $O(1)$ elements on average.

2. 2. Conclude the expected complexity

   A lookup examines only the elements in its bucket's chain, which has constant expected size, giving expected $O(1)$ lookup time.

Answer: O(1)