Hash indexes: equality still needs collision handling

Two keys can map to the same bucket while having different full hash values, and two distinct keys can also share a full finite-width hash. Neither condition implies the original values are equal. A generic chained hash table can store keys alongside entries and compare them while searching its bucket. A database index may instead retain only a hash fingerprint and a row reference, requiring the table value for exact rechecking. PostgreSQL 18's hash index stores a four-byte hash value rather than the original indexed datum.

The hash function must respect the database's equality semantics: values considered equal must be mapped consistently for the supported operation. Bytewise hashing without accounting for collation or a type's equality rules can violate that requirement. Conversely, a good hash is not a total order. The neighboring bucket of a key does not correspond to the next larger key, so a hash equality index does not directly provide the ordered range navigation of a B-tree. Evaluate the operator support of the actual index type rather than its name alone.

For N stored entries distributed uniformly over B buckets, the expected load per bucket is N/B. That average is not a bound on the largest bucket and does not describe a workload with many identical values. Chaining, open addressing, overflow pages, and resizing have different costs. A highly duplicated key can concentrate many required matches into one bucket even with an excellent hash function. Returning those matches necessarily costs work proportional to the output, so a constant-time headline cannot mean constant time for every full result.

Persistent database hash indexes also need crash recovery, concurrent bucket splits, and safe page reclamation. PostgreSQL's implementation can add overflow pages to a full bucket and split buckets as it expands. A lookup may inspect overflow pages, making a skewed bucket more expensive than a shallow B-tree path. Deleting tuples and recycling pages does not necessarily shrink the index file or bucket count. Rebuild behavior and maintenance policy are implementation details to measure; do not assume a standard in-memory hash-table resize routine describes an on-disk database.

Compare equality queries with realistic popular keys, absent keys, and a changing table size. Record candidate rechecks, bucket or overflow page visits, cache behavior, and insertion latency during growth. A small average load can coexist with one expensive hot bucket. If a query also requires sorting, range conditions, uniqueness enforcement, or multiple search columns, confirm the access method supports them; PostgreSQL 18's hash indexes have narrower capabilities than its B-tree indexes. Space saved by fingerprints must be weighed against exact recheck work.

The modular lab exposes one deliberately weak bucket map. Reset, set modulus m=16 and additive step a=4, predict the orbit 0,4,8,12 repeating with period four, then Play or Step. Separately Reset, set m=16 and a=5, predict all sixteen residues appear, then Play or Step. Interpret the sequence as stride-patterned integer keys under a direct modulo map only. It is not a production hash function, randomized collision experiment, or database bucket-split simulation. The contrast demonstrates why input structure and mixing assumptions matter.