Hash Indexes · bigonotes

A hash index runs each key through a hash function to get a bucket number, and stores the key's location in that bucket. Looking a key up is one calculation and one jump, with no tree to walk. That makes hash indexes the fastest option for exact matches. The same trick also makes them useless for ranges, sorting and prefix searches, which is why most SQL databases default to B-trees instead.

How it works#

A hash function turns any key into a fixed-size number. Take that number modulo the number of buckets, and you know exactly which bucket to look in.

Say three emails hash like this. Each bucket then points at its row:

Bucket	Key	Points to
17	`john@example.com`	Row 3
42	`alex@example.com`	Row 1
85	`sarah@example.com`	Row 2

Looking up alex@example.com:

hash("alex@example.com") gives 42.
Go to bucket 42, which points to Row 1.

Done: $O(1)$ on average, with no tree traversal.

Hash vs B-tree#

Exact lookup: the hash index computes one bucket and jumps there, while the B-tree walks from root to leaf. Range lookup: the B-tree scans adjacent sorted leaves, while hashed values land in scattered buckets

Compare the two lookups for alex@example.com:

Index	Path to Row 1	Cost
B-tree	Root → internal node → leaf	A few page reads, $O(\log n)$
Hash	Hash → bucket 42	One lookup, $O(1)$

For pure exact-match lookups, hashing wins.

Why ranges don't work#

SELECT * FROM users WHERE age BETWEEN 25 AND 35;

A B-tree on age keeps sorted leaves: 22, 23, 25, 27, 30, 33, 35, 38, 42. Find 25, then walk right until 35. The values are adjacent.

A hash on age scatters neighbouring values:

Value	Bucket
25	71
26	14
27	93
…	…

The buckets are scattered at random. You'd have to hash every possible value in the range and check each bucket, which is no better than a scan (and impossible for non-integer keys like prices or timestamps).

A good hash function deliberately destroys ordering to spread keys evenly. That even spread is what makes lookups fast, and it is exactly why ranges, prefixes and ORDER BY get no help.

Collisions#

Two different keys can hash to the same bucket:

Key	Bucket
`alex@example.com`	42
`alice@example.com`	42 ← collision

There are two standard fixes.

Chaining#

Each bucket holds a small list. Bucket 42 holds alex@example.com, then alice@example.com, then the end of the list.

To look up alice:

Hash it to bucket 42.
Check alex: no match.
Check alice: found.

Open addressing#

If the bucket is taken, try the next one:

Key	Hashes to	Stored at
`alex`	42	42
`alice`	42 (taken), so try 43	43

To look up alice:

Hash it to bucket 42: holds alex, no match.
Try bucket 43: holds alice, found.

Keeping collisions rare#

With a good hash function and enough buckets (the table resizes as it fills), collisions stay rare and lookups stay $O(1)$ on average.

Where hash indexes are used#

Hashing shows up wherever exact-match speed matters more than order.

Where	How
Redis	The main keyspace is a hash table: `GET user:123` hashes the key and jumps to its value. There are no range queries over keys by design.
Memcached	Pure key-value cache built on hashing.
Hash joins in SQL	To join two tables, the database builds a temporary hash table from the smaller one, then probes it for each row of the larger one.
PostgreSQL hash indexes	`CREATE INDEX ... USING hash (email);` exists, but is rarely used, because a B-tree handles exact matches nearly as well and also supports ranges.
DynamoDB partition keys	The partition key is hashed to choose which partition stores an item, which is why you can't range-query on the partition key alone. Within a partition, items are kept sorted by the sort key, so `BETWEEN` and `>` work on the sort key.

The DynamoDB design is a nice example of using both ideas: hashing to spread data evenly and find the right partition fast, plus sorted order inside each partition for range queries.

Choosing hash or B-tree#

Pick by the queries you need to serve:

Query	Hash	B-tree
Exact match (`=`), e.g. find user by email	$O(1)$ , ideal	$O(\log n)$ , also fine
Range (`>`, `<`, `BETWEEN`), e.g. ages 25–35	Not supported efficiently	Excellent
Prefix (`LIKE 'ale%'`)	Not supported	Works
`ORDER BY`	No help	Already sorted
Cache lookup by session ID	Ideal	Works, but sorting is wasted
Typical home	Key-value stores and caches	General-purpose databases

Key takeaways#

A hash index maps a key straight to a bucket, giving $O(1)$ average exact-match lookups.
Hashing scatters keys on purpose, so it can't help with ranges, prefixes or sorting.
Collisions are handled by chaining or open addressing, and stay rare with good sizing.
Hash structures power key-value stores (Redis, Memcached), hash joins and DynamoDB partitioning.
Most SQL databases default to B-trees because they handle both exact and range queries.