7.1 Hash Indexes: Equality Lookups, Collisions, and Dynamic Resizing

Hash indexes use a hash function to map a search key to a bucket and are good at equality predicates. They do not preserve key order, so they are typically not suitable for direct range scans, ordered output, or prefix ordering. The "O(1)" refers to expected probe complexity under reasonable load and distribution, not a guarantee of a single I/O operation.

This lesson's objectives

• Distinguish hash table, persistent hash index, and hash join;
• Explain bucket, slot, collision, overflow, and load factor;
• Understand the growth mechanisms of extendible hashing and linear hashing;
• Analyze the semantics of equality, NULL, duplicates, and collation;
• Know when a B+ tree is actually more appropriate.

From hash value to bucket

hash(search_key) -> hash bits
directory/bucket mapping -> bucket page
scan matching fingerprints/keys in bucket
follow overflow or retry probes when necessary
verify actual key equality

The final step can't be skipped. A hash collision means different keys might end up in the same hash/bucket, so the index must store and compare the actual key or sufficient collision-resolution information.

Assumptions Behind Expected O(1)

An in-memory hash table can provide expected constant probes under the following conditions:

• The hash function distributes real keys uniformly enough;
• Load factor is controlled;
• resize/overflow keeps up with growth;
• Adversarial keys do not cause concentration conflicts;
• The key comparison cost is bounded.

A persistent hash index also needs to consider directory/cache misses, bucket page I/O, overflow chains, WAL, latches, and base-row lookup. A single equality query might return many duplicate keys, and the output cost is inherently O(result size).

Collision resolution

Separate chaining / overflow pages

When a bucket is full, it links to an overflow page. The implementation is simple, but skew or hot keys can result in long chains, random reads, and latch hotspots.

directory[17] -> bucket page -> overflow page -> overflow page

Open addressing

After a conflict, search for other slots using probe sequences such as linear/quadratic probing or double hashing. Good cache locality, but deletion, high load factor, and resizing are complex; on-disk page layout still needs to control probes across pages.

Cuckoo hashing

When there are multiple candidate positions for a key, a collision causes the existing key to be evicted and moved to another location. Lookup probes are few, but insertion may create relocation chains, requiring stash or rehashing. It is a viable choice, not the default structure in all database hash indexes.

A hash function is not a synonym for password hashing

Index hashing prioritizes speed, distribution, and stability in encoding; password hashing prioritizes being expensive, salted, and resistant to brute-force attacks. Never use fast, non-cryptographic hashes to store passwords, and don't default to expensive password KDFs for high-throughput index hashing.

For untrusted input, the engine must also consider hash-flooding DoS attacks; it may use keyed hashes, collision limits, or alternative data structures.

Static hashing

Fix B buckets:

bucket = h(key) mod B

After data growth, load factor/overflow increases; performing a single, full rehash of all entries results in high latency and I/O. Reserving too many buckets wastes directory/page space.

Extendible hashing

An extendible hash maintains directory depth d, using a fixed number of d bits of the hash to index 2^d directory entries. Each bucket has a local depth of l; multiple directory entries can point to the same bucket.

bucket full:

1. If l < d, split bucket, l += 1, redistribute its entries, and update the relevant directory pointers;
2. If l == d, directory double, d += 1, then split bucket;
3. retry insertion.

Example:

global depth = 2
00 -> A (local depth 1)
01 -> B (local depth 2)
10 -> A (local depth 1)
11 -> C (local depth 2)

This example uses the lowest bit: 00 and 10 both end in 0, so they share bucket A at local depth 1. A design using the highest bit is also possible, but then 00 and 01 would share A. Its directory pointers would differ from this diagram.

Directories can reside in memory, but large global depth, sparse distribution, and persistence/concurrency remain costly. Implementations may merge low-occupancy buckets or shrink the directory, using varied strategies.

Linear hashing

Linear hashing doesn't perform a single directory doubling, but instead uses level i and split pointer p to gradually split buckets:

h_i(key) = h(key) mod (2^i * initial_buckets)
if bucket < p:
    use h_{i+1}(key)

Every time a bucket is split using a split pointer, after p scans the entire round, the level increases. This smooths the cost of scaling, but lookup/metadata and overflow management still need to be implemented.

Equality semantics

A hash index must be consistent with the equality semantics of the query operator:

• data type canonicalization;
• collation/case sensitivity;
• numeric representations;
• NaN/-0 and other edge cases;
• composite key and NULL;
• database operator class.

If an equality comparator considers two values equal, the hash function must assign them compatible hashes; otherwise, the index will miss those results.

SQL = returns UNKNOWN for NULL. IS NOT DISTINCT FROM/MySQL <=> null-safe equality operations can use a hash index only if supported by the product/operator; it cannot be inferred from the hash structure itself.

Duplicate vs. Unique

A non-unique hash bucket can store multiple record locators for the same key. A unique hash index must atomically check for "no existing visible/conflicting key" before insertion under concurrency; simply looking up first and then inserting would lead to a race condition.

Uniqueness is a correctness constraint and cannot be removed just because the table is small; whether it's implemented with hash or B-tree is a physical design choice.

Hash index, hash join, hash aggregation

• hash index: persistent/memory access path, finds rows from a key;
• hash join: query operator that builds a hash table on one side and probes the other side;
• hash aggregation: build a hash table by group keys;
• application key-value hash map: an in-process data structure.

They share the hashing concept, but differ in lifecycle, spill, durability, concurrency, and semantics. Database hash joins do not require a hash index to exist on the schema.

Product Differences

PostgreSQL hash indexes support WAL recovery and equality lookups, but not unique or multicolumn indexes. Entries store a hash value and record locator, so a heap visit must recheck actual equality; they cannot provide index-only scans. Splits increase the number of buckets. B-trees support a wider range of access patterns. MySQL's MEMORY engine supports HASH and B-tree indexes, but table durability, locking, data types, and capacity limits are defined by the current version.

Don't say "Redis is just a replacement for production database hash indexes." Redis is a networked data structure server, with persistence, eviction, replication, and transaction models entirely different from relational indexes.

Official sources:

• PostgreSQL Hash Indexes
• MySQL MEMORY Storage Engine

When to choose an ordered index

The following requirements typically favor B+ trees:

• BETWEEN, <, >;
• ORDER BY / min/max;
• prefix/lexicographic scan;
• composite leading-key queries;
• range lock/predicate access;
• One index serves both equality and range queries.

A hash index is only worth the extra write and storage cost in scenarios with equality-heavy workloads, when the engine implementation is mature, and benchmarks prove a benefit.

Summary of This Lesson

Hash indexes trade unordered mapping for equality probing; the actual cost is determined by collision rate, load factor, bucket I/O, result cardinality, and equality semantics. The next lesson tackles the opposite goal: producing a globally ordered result even when memory is insufficient.