PostgreSQL hash indexes narrow an equality search using a hash code, then verify the original value in the table. A hash match is a candidate, not proof of equality. Two different values can have the same code, and different codes can also map to the same bucket. Neither collisions nor shared buckets imply incorrect query results when the normal recheck is performed.

What lives in a bucket

An index tuple contains a four-byte hash value and a reference to the table tuple; it does not contain the full indexed value. The bucket mapping directs a lookup to relevant index pages. Buckets are shared storage, not one separately allocated bucket for every distinct key. An overflowing bucket can acquire additional pages that its scans must visit.

PostgreSQL can sort hash codes within an individual index page to accelerate local searching, but that does not provide ordering by the original column. A hash index cannot satisfy a key range or an ordered result. It supports single-column equality access, cannot enforce uniqueness, and does not support IS NULL. A B-tree is still a candidate for equality as well as the broader operations it supports.

The absence of original values makes hash scans lossy: matching index entries must be checked against table values. A collision can therefore appear as Rows Removed by Index Recheck in an execution plan. That is evidence that candidate verification worked, not an indication that the database returned both colliding values as equal.

When it breaks

Describing an indexed update as touching only one bucket hides important work. Changing the indexed key changes the tuple’s indexed value and may send its new entry to another bucket. PostgreSQL’s versioned rows and deferred index cleanup mean obsolete references do not necessarily disappear immediately. Growth can also split a bucket, and overflow pages add I/O.

Consequently, a workload with heavily repeated values or rapid growth can behave differently from a nearly unique, steady equality workload. Hash lookup is not an unconditional constant-time latency guarantee. Modern PostgreSQL hash indexes are crash recoverable, but durability does not eliminate storage maintenance or turn the structure into a uniqueness constraint.

Check it quickly

Run this with psql on a disposable PostgreSQL 18 database. It creates two hundred thousand temporary text keys using C collation, discovers a collision with the server’s own hashtext, and tests lookup and update behavior. It does not assume hash values are portable identifiers. Rollback removes the fixture.

\set ON_ERROR_STOP on
BEGIN;
CREATE TEMP TABLE hash_items (key text COLLATE "C");
INSERT INTO hash_items SELECT 'key-'||g FROM generate_series(1,200000) AS g;
CREATE TEMP TABLE collision_pair AS
SELECT min(key) AS a,max(key) AS b FROM hash_items
GROUP BY hashtext(key) HAVING count(*)>1 ORDER BY hashtext(key) LIMIT 1;
SELECT a AS collision_a,b AS collision_b FROM collision_pair \gset
SELECT a,b,hashtext(a),hashtext(b) FROM collision_pair;
CREATE INDEX hash_items_key ON hash_items USING hash(key);
ANALYZE hash_items;
EXPLAIN (ANALYZE, BUFFERS, TIMING OFF) SELECT key FROM hash_items WHERE key=:'collision_a';
UPDATE hash_items SET key='changed-'||key WHERE key=:'collision_a';
SELECT count(*) AS old_key_rows FROM hash_items WHERE key=:'collision_a';
SELECT count(*) AS new_key_rows FROM hash_items WHERE key='changed-'||:'collision_a';
DO $$ BEGIN
  IF (SELECT hashtext(a)=hashtext(b) AND a<>b FROM collision_pair) IS DISTINCT FROM true THEN
    RAISE EXCEPTION 'fixture did not establish a collision';
  END IF;
  IF (SELECT count(*) FROM hash_items h JOIN collision_pair p ON h.key=p.a) <> 0 OR
     (SELECT count(*) FROM hash_items h JOIN collision_pair p ON h.key='changed-'||p.a) <> 1 OR
     (SELECT count(*) FROM hash_items h JOIN collision_pair p ON h.key=p.b) <> 1 THEN
    RAISE EXCEPTION 'hash lookup or indexed update returned wrong keys';
  END IF;
END $$;
ROLLBACK;

On PostgreSQL 18.6, the discovered keys were key-129539 and key-7295, both with hash code -1960436116. The equality plan used hash_items_key, returned one row, and reported one row removed by index recheck. The two strings remained distinct despite their identical hash code. This is a concrete negative control against treating hashes as collision-free keys.

Updating the first key to its changed- form left zero rows under its old value and one under its new value. The other colliding key still had one row. The final assertions verify all three facts and verify that the original pair really collided. A successful update alone would not establish that unrelated colliding entries remained searchable.

The particular pair and plan are observations from this version. If a different environment does not discover a pair, the script must stop rather than claiming a collision was tested. Even when the pair changes, the required semantics stay the same: exact equality returns only matching original values, and updating one value does not change another merely because their hashes coincide.

Evaluate maintenance with lookup performance

Measure page accesses, equality latency, update behavior, and index size using representative distributions. VACUUM can remove dead references and recycle overflow pages, but it does not shrink the hash index’s bucket count or return its allocation to the operating system. Rebuilding is a separate maintenance operation with its own cost. A smaller hash entry can be useful, yet only a full workload comparison establishes whether that benefit exceeds recheck, overflow, and write overhead.

Sources