Hash Index
An index that uses a hash function to map keys directly to storage locations. O(1) lookups for exact matches but useless for range queries. Memcached and Redis use hash indexes.
What is Hash Index?
In short
A hash index is a database index that runs each key through a hash function and stores the key's location in a bucket at the resulting hash value, giving average O(1) lookups for exact-match queries. It cannot answer range queries or sorted scans because hashing scatters keys with no ordering, so it is used where you only ever look up a single key by its exact value.
What a hash index actually is
A hash index is a lookup structure built on top of a hash table. You give it a key, it computes hash(key), and that number tells it which bucket holds the pointer to your row or value. Finding a record by exact key takes the same small, constant amount of work whether the table has a thousand rows or a billion.
Compare that to the default index in most relational databases, the B-tree. A B-tree keeps keys in sorted order, so a lookup walks down a tree of depth roughly log(n). For a billion rows that is about 30 comparisons. A hash index skips the tree entirely: compute one hash, jump to one bucket, done.
The price for that speed is that the order of keys is destroyed. After hashing, key 1, key 2, and key 1000000 land in unrelated buckets. So a hash index can answer 'give me the row where id = 42' but it cannot answer 'give me all rows where id is between 40 and 50' or 'give me rows sorted by id'. For those you need a B-tree.
How it works under the hood
The index is an array of buckets. A hash function maps each key to a bucket number, usually with something like hash(key) modulo bucket_count. Inside each bucket sits a pointer to the actual data, or in an in-memory store like Redis, the value itself.
Two different keys can hash to the same bucket. That is a collision, and it is unavoidable once you have more keys than buckets. The common fix is chaining: each bucket holds a small linked list of entries, and a lookup walks that short list comparing full keys until it finds the match. As long as the table stays well below full, these chains stay length one or two, so lookups stay effectively constant time.
When the table fills up past a load factor (often around 0.7 to 0.75), chains grow long and lookups slow down. The structure then rehashes: it allocates a larger bucket array, often double the size, and re-inserts every key. This is an expensive one-time cost amortized across many fast inserts. PostgreSQL hash indexes, Java's HashMap, and Python's dict all do versions of this.
On-disk hash indexes add a wrinkle: a naive rehash would rewrite the whole file. Linear hashing and extendible hashing solve this by splitting buckets incrementally instead of rebuilding everything at once, which is why production database hash indexes use those schemes rather than a plain in-memory table.
When to use one and the trade-offs
Reach for a hash index when your access pattern is purely point lookups by an exact key and you never need ranges, sorting, or prefix matches. Session stores, caches keyed by ID, user-by-email lookups, and key-value workloads are the natural fit.
The downsides are real. No range queries, no ORDER BY support, no LIKE 'prefix%' acceleration, and no help for queries on a prefix of a multi-column key. Hash indexes are also typically not great for equality on partial keys. Because of these limits most relational engines default to B-trees, which handle both exact and range queries at a small extra constant cost.
There is also a durability and crash story. Older PostgreSQL hash indexes were not written to the write-ahead log and could be corrupted by a crash, so they were discouraged until version 10 made them WAL-logged and crash-safe. Always check whether your engine's hash index is crash-safe before relying on it for persistent data.
A practical rule: if you are not sure, use a B-tree. A B-tree gives you exact-match lookups that are nearly as fast plus range support you might want later. Choose a hash index only when you have measured that point lookups dominate and the constant-factor win matters.
A concrete example
Imagine a login service storing 50 million users, looking each up by email on every sign-in. With a B-tree on email, each lookup costs roughly log(50M), about 25 comparisons through tree nodes. With a hash index, each lookup is one hash computation plus one bucket access, regardless of table size.
Now imagine you also need a page that lists users who signed up between two dates, sorted by date. The hash index is useless here because it has no ordering. You would keep a B-tree on the signup timestamp for that query and use the hash index only for the email point lookup. This is the typical pattern: pick the index type per query shape, not per table.
In-memory key-value stores take this further. Redis and Memcached are built around a hash table as the primary data structure, so GET key is a single hash lookup. That is how they sustain hundreds of thousands of operations per second on a single core.
Where it is used in production
Redis
Its core keyspace is a hash table, so GET and SET resolve a key to its value in a single hash lookup; it incrementally rehashes to avoid stalls.
Memcached
Stores all cached items in a hash table keyed by the item key, giving constant-time GET and SET for its caching workload.
PostgreSQL
Offers USING hash indexes for equality-only columns; made them crash-safe and WAL-logged in version 10.
Amazon DynamoDB
Uses the partition key's hash to route each item to a physical storage node, which is why queries must supply the exact partition key.
Frequently asked questions
- Why can't a hash index do range queries?
- A good hash function deliberately scatters keys so that similar keys land far apart in different buckets. After hashing there is no relationship between a key's value and its bucket, so the index has no way to find all keys between two bounds or return them in order. You need a B-tree, which keeps keys sorted, for ranges and ORDER BY.
- Is a hash index always faster than a B-tree for exact lookups?
- On paper yes, because it is O(1) versus O(log n). In practice the gap is small for typical table sizes, and B-trees benefit from heavy database optimization and good cache behavior. The hash index wins most clearly on very large tables with high point-lookup volume, and only when range support is genuinely never needed.
- What happens when two keys hash to the same bucket?
- That is a collision, and it is normal. The usual handling is chaining, where each bucket holds a short list of entries and lookups compare full keys within that list. As long as the load factor stays low the chains are tiny, so collisions barely affect speed. When chains get long the structure rehashes into a bigger bucket array.
- Should I use a hash index in PostgreSQL?
- Only for columns you query exclusively with equality and never with ranges, sorting, or pattern matching. Since version 10 hash indexes are crash-safe and replicated, so they are safe to use, but B-trees remain the safer default because they handle both exact and range queries well.
- Do in-memory caches like Redis use hash indexes?
- Yes. Redis and Memcached are built around a hash table as their primary structure, so a key lookup is essentially a single hash index access. This is what lets them serve hundreds of thousands of operations per second per core for exact-key reads and writes.
Learn Hash Index hands-on
This page explains the idea. The full lesson lets you step through the ring as servers join and leave, read the implementation, and check yourself with a quiz. It is one of 760+ lessons in the System Design Masterclass, from your first API call to distributed consensus. Eleven Foundation lessons are free, no signup. Lifetime access is ₹499 in India or $7.99 worldwide, one payment, no subscription.
Related lessons
Lessons that touch on Hash Index as part of a larger topic.
See also
Related glossary terms you might want to look up next.
Index
A data structure that speeds up database lookups. Like the index at the back of a book that lets you jump to the right page instead of reading every page.
B-Tree
A self-balancing tree data structure used by most relational databases for indexes. Keeps data sorted and allows searches, insertions, and deletions in O(log n).
Consistent Hashing
A hashing technique where adding or removing servers only moves a small fraction of keys. Used by Amazon DynamoDB and Cassandra for data distribution.
Database
An organized collection of data that can be easily accessed, managed, and updated. The backbone of almost every application.
SQL
Structured Query Language for managing relational databases. Tables, rows, columns, and powerful joins to query related data.
NoSQL
Databases that don't use traditional table-based relational models. Includes document stores, key-value, graph, and column-family databases.