Hash Table
A hash table (or hash map) is a data structure that maps keys to values using a hash function to compute an index into an array of buckets, giving average O(1) lookup, insertion, and deletion.
Definition
A hash table (or hash map) is a data structure that maps keys to values using a hash function to compute an index into an array of buckets, giving average O(1) lookup, insertion, and deletion.
Overview
Hash tables are among the most widely used data structures in software engineering, backing everything from language-level dictionaries (Python's `dict`, JavaScript's `Map`/object, Java's `HashMap`) to database indexes and caching layers. The core idea is simple: a hash function converts a key into a numeric index, and the value is stored at that index in an underlying array. A well-distributed hash function spreads keys evenly across buckets so that most lookups touch only one or two entries. Because different keys can hash to the same index — a collision — hash tables need a collision-resolution strategy. The two dominant approaches are chaining, where each bucket holds a small list of entries that share an index, and open addressing, where a colliding entry is placed in the next available slot according to a probing sequence. As more entries are added, the table's load factor rises, and beyond a threshold the table is resized ('rehashed') into a larger array to keep operations fast — this occasional resize is why hash table operations are O(1) on average but not guaranteed O(1) in the worst case. Hash tables trade the ordering guarantees of a binary search tree for speed: unlike a BST, a standard hash table gives no guarantee about the order in which keys are stored or iterated. This makes them ideal when you need fast key-based lookup and don't care about order, but a poor fit when you need sorted traversal, range queries, or predictable iteration order. Understanding hash tables is essential for reasoning about algorithmic complexity — many optimizations that turn an O(n²) brute-force algorithm into an O(n) one (like the classic two-sum problem) work by trading extra memory for a hash table lookup instead of a nested loop. It is often mentioned alongside Big O Notation in this space.
Key Concepts
- Average O(1) time complexity for insert, lookup, and delete
- Hash function maps keys to array indices (buckets)
- Collision resolution via chaining or open addressing
- Automatic resizing (rehashing) as load factor grows
- No inherent ordering of keys or predictable iteration order
- Backs native dictionary/map types in most programming languages
- Worst-case degrades to O(n) with many collisions or a poor hash function