A hash index is a database index that stores entries in buckets selected by a hash function applied to the indexed key, so that an equality lookup can jump almost directly to the matching rows. In indexing, it is the main alternative to the B-tree index for workloads dominated by exact-match searches such as WHERE id = 42.
Because the hash function destroys key order, a hash index cannot answer range conditions, sorting or prefix searches. That single trade-off, constant-time equality versus no ordering, explains almost every decision about when to use it in database systems.
How a hash index locates a row
When a row is inserted, the database computes a hash value from the indexed column, reduces it to a bucket number, and stores the key with a pointer to the row in that bucket. A lookup repeats the same computation, reads one bucket and compares the stored keys to filter out hash collisions, where different keys share a bucket.
The expected cost of a lookup is O(1), independent of table size, as long as buckets stay short. As the table grows, the index must add buckets. Linear hashing and extendible hashing split one bucket at a time, which avoids rebuilding the whole structure and keeps the load factor within a target range.
| Component | Role | What can go wrong |
|---|---|---|
| Hash function | Maps a key to a fixed-size value | Poor distribution creates hot buckets |
| Bucket array | Groups entries by hash value | Too few buckets lengthen every search |
| Overflow pages | Hold entries when a bucket is full | Long chains turn lookups into scans |
| Load factor | Ratio of entries to bucket capacity | High values trigger splits and slowdowns |
| Stored key or hash | Confirms the real match after hashing | Storing only the hash requires a row recheck |
Hash index versus B-tree index
The B-tree index is the default in nearly every relational system because it keeps keys sorted and supports a broad set of operators. A hash index wins only in a narrow case: very frequent equality lookups on long or random keys, where a smaller index and fewer comparisons pay off.
| Operation | Hash index | B-tree index |
|---|---|---|
| Equality (=, IN) | Yes, about one bucket read | Yes, a few page reads by tree depth |
| Range (<, >, BETWEEN) | No | Yes |
| ORDER BY on the key | No | Yes, without a sort step |
| Prefix search (LIKE ‘abc%’) | No | Yes |
| Multi-column leading prefix | No, all columns required | Yes, leftmost columns usable |
| Unique constraint | Rarely supported | Yes |
| Covering index scans | Usually no | Yes |
The difference in lookup cost is smaller than the theory suggests. A B-tree over millions of rows typically has a depth of three or four levels, and the upper levels sit in memory, so a hash index often saves only one or two page reads. The query planner chooses between them using cost estimates, and it will ignore a hash index for any predicate it cannot serve.
Hash index support across database systems
Support for hash indexes varies widely between engines, and the same syntax may mean different things. Some systems build a persistent on-disk structure, while others keep an in-memory hash table that is rebuilt automatically or accept the keyword and silently create a B-tree.
| System | Behavior | Practical note |
|---|---|---|
| PostgreSQL | Persistent hash access method | Crash-safe and replicated since version 10 |
| MySQL MEMORY engine | Default index type for memory tables | Data is lost on restart |
| MySQL and MariaDB InnoDB | Adaptive hash index built automatically | Not user-defined, can be disabled |
| SQL Server | Hash indexes on memory-optimized tables | Bucket count fixed at creation |
| Redis and key-value stores | Hash table as the primary structure | The whole store behaves like a hash index |
Systems with a fixed bucket count require sizing in advance. A common guideline is to set the bucket count at one to two times the expected number of distinct keys; far fewer buckets create long chains, while far more waste memory.
When to choose a hash index
A hash index is a specialized tool, and the default answer remains a B-tree. The following decision table summarizes situations where the choice is clear.
| Situation | Recommended index | Reason |
|---|---|---|
| Lookups only by exact token, UUID or hash | Hash index | Smaller index, flat lookup cost |
| Key also used for sorting or pagination | B-tree index | Hash order is meaningless |
| Date or numeric range filters | B-tree index | Hash cannot serve ranges |
| Very long text keys compared by equality | Hash index | Index stores fixed-size hashes |
| Uniqueness must be enforced | B-tree index | Most engines lack unique hash indexes |
| Low-cardinality column with many duplicates | Neither alone | Long buckets or poor selectivity |
Pitfalls and misconceptions
- Skewed keys with many identical values put most entries in one bucket, so lookups degrade toward a scan.
- A hash index is not automatically faster than a B-tree; on cached data the difference is often negligible.
- Collation and type casts matter: a query that compares a cast or a different collation cannot use the index.
- Bulk inserts into a growing index cause repeated bucket splits; building the index after loading is usually quicker.
- Older engine versions may have non-logged hash indexes that must be rebuilt after a crash.
The simple explanation
Imagine a coat check that gives each coat a numbered hook based on a quick rule applied to the owner’s ticket. To return a coat, the attendant applies the same rule and walks straight to the right hook, without searching the whole room.
A hash index does the same for a database. It is excellent for finding one exact item, but useless for questions like “show every coat between hook 10 and 20 in order”, because the hooks are not arranged by any meaningful order. Fast exact matches, no ranges is the whole idea.
How it is used in practice
A web application stores login sessions in a PostgreSQL table with about 40 million rows, keyed by a 64-character random session token. Every request looks up one token by equality, and nothing ever sorts or filters tokens by range. The B-tree on the token column has grown large because each entry stores the full text key.
The team replaces it with a hash index on the token column, which stores fixed-size hash values instead of long strings. The index becomes noticeably smaller, more of it stays in memory, and session lookups remain a single fast probe. Expiry cleanup, which filters by a timestamp range, continues to use a separate B-tree on the expiry column.