Skip to main content

Hashing as a Randomized Model: Expected O(1) and When It Fails

What This Concept Is​

A hash table maps keys to m buckets or starting positions. Collisions are possible whenever distinct keys share a destination; equality must still decide whether the requested key is present. With chaining and n stored keys, define load alpha=n/m. For a fixed absent key x, let I_y indicate that stored key y collides with x. If each collision probability is at most 1/m, then E[sum I_y] <= n/m by linearity of expectation. Search cost is O(1+alpha), assuming constant-cost hashing and equality.

The expectation must name its random experiment: for example, choosing a hash function independently of a fixed set of input keys. The table is not guaranteed to distribute every possible key set evenly.

Why It Matters Here​

This is the link from probability to an engineering promise. Removing its assumptions changes the promise. A low average load does not exclude one long chain, and randomized hashing does not give a per-request worst-case latency bound by itself.

Concrete Examples​

With h(x)=x mod 8, keys 0,8,16,24 collide despite load 1/2. In chaining, an absent lookup for 32 can inspect four stored keys. In linear probing, the same input forms a contiguous cluster and may inspect another empty slot before reporting absence. The lab deliberately uses this deterministic hash so the failure of an unconditional constant-time claim is visible.

For a fixed absent x in a randomized chaining model with n=100 and m=200, expected colliding stored keys are at most 0.5. This is neither a guarantee that every bucket holds at most one key nor a proof of the same probe bound for linear probing. Independence requirements and clustering behavior differ.

Common Confusion / Misconceptions​

A cryptographic digest, random-looking output, a prime capacity, and a universal hash family are different concepts. Variable-length keys can take time proportional to key length to hash or compare. Expected O(1) table navigation does not remove that cost. Equal keys must have equal hashes while resident; changing key identity or hashing fields breaks reachability.

How To Use It​

Separate the dictionary contract from the hashing mechanism. State key encoding, equality, hash computation cost, source of randomness, load policy, and adversary model. For performance evidence, include both representative and deliberately colliding inputs. For bounded latency, consider a structure or fallback with a documented worst-case guarantee.

Check Yourself​

  1. Where is linearity of expectation used?
  2. Does the collision-indicator argument require indicators to be independent?
  3. Why does a prime table size not prevent chosen collisions?
  4. Which work remains for a very long string key?

Mini Drill or Application​

For the lab map, insert multiples of the current capacity and measure examined slots before a resize. Compare a spread-out key set at the same occupancy. Explain what the measurements demonstrate and why neither proves an expected bound. Then derive the chaining bound for a randomly chosen hash family. See P9.

Read This Only If Stuck​

Use CLRS, Skiena, or Sedgewick and Wayne for hashing models, collision indicators, and key equality. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.