2 / 4 Hash Functions, Universal Hashing & Hash Flooding

Four Live Buckets

A profiler stores object records keyed by their offset into a 4-byte-aligned arena, so every key is a multiple of 4. The table has m=16m = 16 buckets with h(k) = k mod 16 and separate chaining. You insert 200 records.

What is the expected chain length, and which fix restores an even spread?

A

All 200 in one bucket, since every multiple of 4 has the same residue modulo 16

B

About 50 in each of 4 live buckets; make mm a prime such as 17, so the modulus shares no factor with the key stride

C

About 12.5 in each of 16 buckets; the load factor is only 12.5, so nothing needs fixing

D

About 50 in each of 4 live buckets; doubling mm to 32 restores the spread