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.
Table 1: Core Concepts
| 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. |