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
Use Cases
Frequently Asked Questions
From the Blog
Hash Tables Explained: The Data Structure You Use Daily
Hash tables store key-value pairs for near-instant lookups and power dictionaries and maps everywhere. Learn how hashing, collisions, and resizing work.
Read More ProgrammingData Structures Every Developer Should Know
Arrays, hash maps, stacks, queues, trees, and graphs are the data structures every developer needs. Learn what each one is best at and when to reach for it.
Read More Data ScienceHow to choose a statistical test from your question, not a lookup table
Three questions narrow the choice to one or two tests every time: what type is the outcome, how many groups are you comparing and are they paired, and what does the shape of the data allow. Answering them in order is more reliable than memorising a table, and it surfaces the assumption that actually matters — independence.
Read More ProgrammingHow Python dictionaries work: hashing, collisions and ordering
A dict is a hash table with a compact index layer, and every surprising behaviour follows from that structure — unhashable keys, equal-but-distinct keys colliding, preserved insertion order and resize pauses. The payoff is knowing what makes a good key and when a dict is the wrong container.
Read More