Hash Tables

A hash table maps keys to values via a hash function $h(k) \to \text{index}$, giving $O(1)$ average-case lookup, insert, and delete.

How it works:

1. Compute $h(\text{key})$ to get an array index
2. Store the value at that index
3. Handle collisions (two keys mapping to the same index) via chaining (linked lists) or open addressing (probing)

Performance:

• Average: $O(1)$ for all operations
• Worst case: $O(n)$ if all keys collide (pathological hash function)
• Load factor $\alpha = n / m$ (items / buckets) — resize when $\alpha$ exceeds threshold (typically 0.7)

Where hash tables are critical in ML:

• Python dicts and sets — the backbone of all data processing code
• Deduplication — removing duplicate training examples (hash the content)
• Feature hashing (hashing trick) — map high-dimensional sparse features to fixed-size vector without a dictionary. Used in large-scale linear models and NLP
• Caching — memoizing expensive computations (e.g., tokenized sequences, preprocessed batches)
• Counting / frequency estimation — token frequencies, vocabulary building
• Locality-Sensitive Hashing (LSH) — approximate nearest neighbors by hashing similar items to the same bucket → Approximate Nearest Neighbor Search

Consistent hashing — used in distributed data sharding: when a node joins/leaves, only $O(n/k)$ keys need remapping. Relevant for distributed dataset storage.

See also: Approximate Nearest Neighbor Search, Big-O and Complexity Analysis