Real World: Hashing Algorithms

Math for CS · Axiom Academy

Hash functions, hash tables, and collision resolution Arrays let us access element i in O(1) time — but only if we know the index. What if we want to look up data by a key (a name, a string, an arbitrary object)? A hash function converts keys into array indices. A hash table uses this to achieve expected O(1) insert, delete, and lookup. Be deterministic — same key always produces same index Distribute uniformly — spread keys evenly across the table Be fast to compute — O(1) or O(|key|) Simple but sensitive to the choice of m . Avoid powers of 2 (only uses low-order bits). Primes work well. where A is a constant, 0 < A < 1 . Knuth suggests . Less sensitive to m . Choose h randomly from a family such that for any two distinct keys : This guarantees good average-case behavior regardless of the input. Collision Resolution: Chaining Since , collisions are inevitable (by the pigeonhole principle). Chaining stores all elements that hash to the same slot in a linked list. Under simple uniform hashing, the expected length of each chain is . So search takes expected time. If we keep (e.g., resize the table when ), all operations are expected O(1) . Collision Resolution: Open Addressing Instead of linked lists, store everything directly in the table. When a collision occurs, probe for the next open slot. Simple but causes primary clustering — long runs of occupied slots form, slowing searches. Reduces primary clustering but can cause secondary clustering .

This is the written version of the interactive lesson above. See the full Math for CS course.