Hash Functions

By the end, you can

• Explain the role of a hash function in a hash table and why it must be deterministic, uniform, and fast.
• Apply the division method (h(k) = k mod m) to compute a slot index, and choose a prime table size to avoid low-bit clustering.
• Apply the multiplication method (h(k) = floor(m × frac(k × A))) and explain why it tolerates a power-of-two table size.
• Trace the polynomial rolling hash through a short string, step by step, and explain why the per-step modulo prevents overflow.
• Explain the pigeonhole principle argument for why collisions cannot be eliminated entirely.
• Describe universal hashing and explain how randomizing hash parameters defeats adversarial collision attacks.
• Distinguish non-cryptographic hashes from cryptographic hashes, naming the three extra properties that cryptographic hashes provide.
• Define the avalanche effect and identify which class of hash functions exhibits it.