Hash tables (also called hash maps or associative arrays) are data structures that implement an associative array abstract data type, mapping keys to values for rapid lookup. At their core, they use a hash function to compute an index into an array of buckets from which the desired value can be retrieved. Hash tables are ubiquitous in computer science β powering dictionaries in Python, maps in Go, HashMaps in Java, unordered_map in C++, and countless database indexes and caches. The magic lies in achieving O(1) average-case time complexity for insertions, deletions, and lookups, though the worst case remains O(n) when collisions overwhelm the structure. Understanding how hash tables manage collisions, resize dynamically, and balance speed with memory efficiency is essential for writing high-performance code β a key insight is that performance is determined as much by the hash function and collision strategy as by the underlying array.
What This Cheat Sheet Covers
This topic spans 20 focused tables and 119 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
Table 1: Core Concepts
The vocabulary every hash table discussion is built on β the hash function that turns a key into a number, the array of buckets it indexes into, and the collisions that inevitably arise when two keys land in the same slot. Load factor and rehashing describe how the structure stays fast as it fills, while the birthday problem explains why collisions show up far earlier than most people expect. Get comfortable with these eight terms first; everything later is a variation on them.
| Concept | Example | Description |
|---|---|---|
hash("John") β 42table[42] = "John's data" | β’ Maps keys of arbitrary size to fixed-size integer indices (hash codes) β’ must be deterministic β same input always yields same output. | |
table = [None] * 16table[hash(key) % 16] = value | β’ Array of buckets/slots indexed by hash codes β’ uses modulo operation to wrap hash values into valid array indices. | |
bucket_3 = [(k1,v1), (k2,v2)] | β’ A slot in the hash table array β’ may hold one entry (open addressing) or multiple entries (chaining) when collisions occur. | |
hash("cat") == hash("dog")β both map to index 5 | β’ Occurs when two different keys produce the same hash index β’ requires collision resolution to store both entries. | |
Ξ» = n / mΞ» = 10 / 16 = 0.625 | β’ Ratio of number of entries (n) to table capacity (m) β’ typical resize threshold is 0.7β0.75. |