We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
System Design and AI Engineering, by Roni Das. 984 interactive lessons.
Start LearningFoundation · Database Fundamentals
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.
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.
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.
Learn it in the course
This page is the free part.
₹1,111 in India$25 everywhere elseonce, for the whole course
The System Design course covers Hash Index across a run of lessons, not one page. These 4 alone are about 89 minutes of step-by-step reading, every one with a quiz.
Partitioning by contiguous value ranges, the go-to strategy for time-series data, logs, and anything with a natural ordering.
The identical function body took 143.874 ms declared VOLATILE and 0.078 ms declared STABLE, which is 1,845 times. The default is VOLATILE, and nothing validates any of these claims.
Using hash functions to distribute rows evenly across partitions, the antidote to hotspots and skewed data.
When your database indexes rot and queries slow to a crawl, how to fix it without taking the system down.
all part of
System Design Masterclass
770 lessons · about 287 hours · 18 free to read
₹1,111in India, by UPI
$25everywhere else, by PayPal
It is really nice and good Please join the course
You own this course
Continue with Range Partitioningpay once,
yours for life
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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 search tree in which each node is a page holding many sorted keys, so it stays wide and shallow. Most database indexes use it: finding one key among millions takes only a few page reads.
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.
This page explains the idea. The course covers it step by step, with diagrams. It is part of the System Design Masterclass course, which has 770 lessons. 18 of them are free to read. You pay once and keep it for life, with no subscription.
See the System Design Masterclass coursecourse 1
From absolute beginner to principal engineer, drawn step by step.
Asked about Hash Index in an interview?
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.
