What is Hash Index?

A hash index is an index structure used in database systems and key-value stores to locate rows or documents by an exact match on the indexed column or key. It is built on top of a hash table, where a hash function computes a numeric bucket identifier from the key, and that bucket directly points to the storage page or memory location holding the record. Because lookup time depends on the hash computation and bucket traversal, it approximates O(1) average cost, independent of the total number of entries.

The hash function distributes keys uniformly across a fixed number of buckets. Collisions, unavoidable when distinct keys hash to the same bucket, are resolved either by chaining (maintaining a linked list of entries per bucket) or by open addressing (probing alternate slots within the table). Most implementations dynamically resize the bucket array when load factors exceed a threshold, rehashing all existing entries to maintain performance. Unlike B-tree indexes, hash indexes do not preserve any key ordering, so they cannot support range queries, prefix searches, or ORDER BY sorting on the indexed column. They also typically do not support partial matches or pattern matching.

In practice, hash indexes appear in database engines that prioritize point lookups over ordered scans. MySQL’s MEMORY storage engine offers hash indexes, and PostgreSQL has a built-in hash index type (though it has historically been less favored than B-trees for general workloads). Some NoSQL systems, such as Redis, build their entire core on hash tables for O(1) key lookups. Modern LSM-tree engines (e.g., LevelDB, RocksDB) sometimes incorporate append-only hash indexes in their in-memory memtable layers to accelerate point lookups before merging into sorted runs.