How Collision Handling Changes Hash Costs

Two hash structures can use the same hash function. Their space, query time, and correctness still change with the fraction of keys that cannot be placed and with the handling of deleted slots.

When engineers compare hash structures, they usually look at the quality of the hash function and the probe count of the probe rule. Two papers from 2026 show where the cost changes a lot even when the hash function stays fixed. In static structures, it is the fraction of keys that cannot be placed and go to the next level. In concurrent structures, it is the handling of deleted slots.

The use of these two cases as one selection criterion is a judgment. The gap between theoretical probe bounds and practical implementations is in The Gap Between Data Structure Theory and Libraries. The basic structure of chaining and open addressing is in Core Data Structures.

Bumping Collects the Cost in Static Structures

A minimal perfect hash function (MPHF) maps a fixed set of n keys to the numbers 0 to n−1 with no collisions. The key set does not change, so all collisions are handled during construction.

The PHast family divides the keys into buckets. For each bucket, it selects an S-bit seed that puts each key in a free slot of the key's slice. The placement function p(s, h) uses the seed s and the key hash h to find the position in the slice.

Seed 0 is reserved. If none of the other $2^S - 1$ seeds places the keys of a bucket without overlap, the structure bumps the bucket. It marks the bucket with seed 0 and places its keys again at the next level. An Elias-Fano array connects the free slots of the first level to the results of the next levels.

flowchart TD
    K["Key"] --> H["64-bit hash"]
    H --> S["Read first-level seed"]
    S -->|"seed ≠ 0"| P["Compute slot in slice"]
    S -->|"seed = 0, bumped"| N["Read next-level seed"]
    N --> R["Read Elias-Fano remapping"]
    P --> OUT["Number from 0 to n-1"]
    R --> OUT

A query for a bumped key reads the seed of the next level and then the remapping structure. These reads are dependent cache misses. On 10⁹ keys, the PHastR paper reports that a bumped-key query takes about 220 to 260 ns more than a first-level query. At this scale, each percent of bumped keys adds more than 2 ns to the average query time.

Space depends on the same variable. The paper gives this approximation of the bits per key. Here, β is the fraction of bumped keys and λ is the expected number of keys per bucket.

$$\frac{S}{\lambda(1-\beta)} + \beta\left(2 + \log_2\frac{1}{\beta}\right)$$

When the seed width S and λ are fixed, β is the only remaining variable. The author also states that, under this condition, both the excess space and the slow queries come from bumping.

First-Level Queries Are Almost Equal

The PHastR paper measures the query time for first-level keys and for all keys separately. All three structures use the same hash function, GxHash, on 10⁹ 64-bit integer keys. PHast+ wrapping is a variant that adds the seed times a small integer δ and wraps keys around the end of the slice.

The first-level query times are within 0.6 ns of each other. The all-key query times follow the order of the bumping rates. The author attributes the difference between PHast+ wrapping and PHastR to bumped keys. For PHast, the author states that its slightly slower first-level queries are also part of the difference.

The test machine is an Amazon EC2 m8a.metal-24xl instance with one AMD EPYC 9R45. This table comes from a separate run. Thus, its all-key query time is slightly different from the 15.3 ns in the full comparison below.

Layouts Reduce Self-Collisions

PHast+ uses additive placement: a seed only adds a shift. When the seed changes, all keys of the bucket move by the same distance. Thus, bit operations can test many seeds at the same time. The PHast paper states that this method makes construction an order of magnitude faster.

The cost is self-collision. Two keys that overlap for one seed move together, so they overlap for almost all seeds. According to the PHastR paper, 35% of the buckets that PHast+ wrapping (δ=3, λ=5) bumped at the first level on 10⁷ keys contained a self-collision.

PHastR uses the lowest 2 bits of the seed to select one of 4 layouts. The remaining bits set a rotation. Each layout takes its offsets from different bits of a 64-bit value that is left over from the bucket computation. Thus, self-collisions occur independently in each layout.

Inside one layout, placement is still additive, so the search stays bit-parallel. The paper states that the three structures in the table differ mainly in the placement function p(s, h). Layouts change the placement function. The path that sends bumped keys to the next levels and to the Elias-Fano remapping has the same framework in all three structures.

A test that changes only the number of layouts isolates this effect. The conditions are 10⁹ keys, S=8, slice length L=1024, λ=4.25, and single-threaded construction.

The query times come from the same generic code for all numbers of layouts. But the construction time for 4 layouts also includes the effect of specialized code. According to the paper, only with 4 layouts do the ring bits of a key fill one word, and construction uses code for this configuration.

The hash function, seed width, and bucket size stay fixed, and only the number of layouts increases. Bumping, space, and query time all decrease. On 10⁷ keys with one layout, the buckets with a self-collision held only 1.28% of the keys but 71% of the bumped keys.

The full comparison points in the same direction. On 10⁹ keys, PHastR (λ=4.25) uses 1.942 bits/key, almost the same as 1.939 for PHast+ wrapping δ=7 (λ=5). Their first-level bumping rates are 0.5% and 3.9%. Queries take 15.3 against 23.2 ns, which is 34% faster.

Single-threaded construction takes 44 against 113 ns/key. The author gives this as 38% of the time, and the calculated value is 38.9%. With 8 threads, construction takes 6.3 against 17.9 ns/key. The construction time of PHastR also includes the effect of the specialized 4-layout code.

This comparison is between structures with different implementations (the sux crate against the ph crate) and different λ values. The author attributes the query difference to the bumping difference. The layout test above changes only the number of layouts in one implementation, so it supports this explanation.

Bumping Has a Floor

Bumping cannot go to zero. In the PHast family, a key can go only into the W slots that start at its slice start. This range is the reach of the key. In PHastR, W is equal to the slice length L.

Propositions 1 to 3 of the paper assume that the number of keys equals the number of slots. They also assume that slice starts are independent and uniform. Under these assumptions, every placement must bump a constant fraction of the keys on large key sets. The paper derives an asymptotic lower bound of about 0.1/W on the expected bumped fraction.

The paper also proves that, in a Poisson model, the best placement bumps about 1/(2W) of the keys. With W=1024 in PHastR, this floor is 0.049%. On 10⁹ keys, the minimum that a greedy placement computes is 0.050%.

The floor itself costs about 0.006 bits/key. The 0.51% bumping of PHastR is about ten times the floor. With (1+ε)n slots, this loss decreases exponentially with εW.

The author attributes the remaining gap mostly to the seed constraint rather than to the reach. One bucket has only $2^S - 1$ possible placements. The author calculates that a search that reaches the floor would reduce the space from 1.94 to about 1.89 bits/key. The author sees this difference of about 0.05 bits/key as room that better searches can reduce.

The paper leaves other open problems too. One is to replace the small final levels with a more compact structure. Another is to find bump-free placements efficiently in subsets of exactly known size.

Deleted Slots Collect the Cost in Dynamic Structures

Linear probing scans forward from the hash location h(v) of a key v until it finds v or an empty slot. If a deletion turns a slot back into an empty slot, the search path for keys stored after it breaks. Thus, implementations either shift later keys back or leave a tombstone that searches skip over.

Meta's F14 article describes how tombstones accumulate in workloads that mix inserts and erases. Then search performance degrades as in a table with a high load factor. At the same time, memory efficiency drops as in a table with a low load factor. Thus, the deletion policy alone causes both costs, with no change to the hash function or the probe rule.

F14 keeps a 1-byte counter for each chunk of 14 slots. The counter records the number of keys that wanted to go into the chunk but are stored in a different chunk. When a key is erased, F14 decrements the counters of all chunks on the probe sequence of that key. If the counter of a chunk is 0, no key overflowed past that chunk, so a search can stop there.

When many threads change the table at the same time, the options become narrower. The paper by Attiya, Oshman, and Schiller compares earlier concurrent linear-probing designs by deletion method. Here, U is the size of the key domain and n is the number of processes.

The cell sizes are the values in Table 1 of the paper. They do not include auxiliary space for resizing. The last two rows are the design of this paper.

Tombstone Reuse Creates Duplicates

This paper lets new inserts reuse tombstones. Then concurrent inserts of the same key can find different tombstones. Each insert can write a tentative copy of the same key in a different cell. Slot reuse solves a space problem, but it creates a correctness problem.

The paper uses the probe order to set priority. The copy nearer to h(v) wins, and surviving copies move only toward h(v). A competing insert writes COLLIDED into a later tentative copy, and a delete writes DELETED. The insert that created the copy then converts the cell to a tombstone.

Lookups also take part in this cleanup. When a lookup returns true because of a copy that is not final, it writes revalidate into that cell. This tells the original insert to check for duplicates again. Copies can move toward h(v), so if the forward scan gives no result, a backward scan goes from the end of the run to h(v).

The per-cell metadata stays small. The LL/SC version uses 2 tag bits and one reserved value in addition to the key. The CAS version adds min(⌈log n⌉, ⌈log m⌉) bits for a cell index or a process identifier, where m is the number of cells.

The correctness guarantee is broad, but the cost analysis is narrow. The algorithm is linearizable even with concurrent inserts of the same key. Lookups are wait-free, and inserts and deletes are lock-free. But Theorem 21, which gives the expected amortized step complexity O(x²+c), requires all of these conditions.

• x > 1, and the load factor is 1 − 1/x.
• The batch of operations is fixed before the hash function is selected, and a worst-case scheduler sets the execution order in the batch.
• The batch has at most (1 − 1/x)m insert calls.
• At any time, at most one insert is active for each key.
• At most c operations on the same key overlap at the same time.

A lookup that writes to a shared cell has a cost like that of the LRU hit path in FIFO Cache Eviction Replacing LRU. But this lookup writes only when it finds a copy that is not final. Thus, the cost is probably small when contention is low, but this is an estimate.

Conditions That Weaken This Claim

On small key sets, bumping costs less. In the PHastR paper, the structure fits in the cache at 10⁷ keys. A query for a bumped key takes about 45 ns more, and each percent of bumped keys costs at most 0.5 ns on average.

At this scale, it can be better to look at construction time or bits/key before the bumping rate. This is a judgment.

If the hash function does not mix its bits well, the priority changes. The F14 article explains that std::hash for integers is often the identity function. If only the low 5 bits are used, keys that are multiples of 32 have many collisions.

The PHastR comparison uses GxHash for all structures and so keeps hash quality fixed. It gives no answer for low-quality hash functions.

Workloads without deletes create no tombstones. Thus, in these workloads, deleted-slot handling probably has a small effect on the cost. This is a judgment. A design that removes tombstones with rebuilds pays the rebuild cost instead of the tombstone cost.

The evidence also has a narrow scope. One author measured the PHastR numbers with 64-bit integer keys on one machine type, and measured construction on 10⁹ keys only once.

Version 2 of the paper reported construction in 37% of the time and 28% faster queries on an Intel Xeon Platinum 8488C. Version 3 reports 38% and 34% on an AMD EPYC 9R45 with a revised implementation.

The concurrency paper gives no implementation benchmarks. Its cost analysis ignores tombstone reuse on purpose and assumes that inserted keys keep their cells after deletion. Thus, the O(x²+c) bound applies only while the cumulative number of inserts, including deleted keys, is at most (1−1/x)m.

For the same reason, the paper does not show how much tombstone reuse shortens runs in practice. Resizing is also out of scope, and an insert that finds no free cell returns ABORT.

The sources also leave some questions open. They contain no design that combines F14-style counters with lock-free tombstone reuse. They also contain no comparison that measures the two methods on the same workload.

Criteria to Check Collision Handling

When you select or implement a hash structure, answer these questions in sequence.

• Is the key set fixed? If yes, an MPHF is a candidate. Together with bits/key, check the first-level bumping rate and the query path for bumped keys.
• Is the structure larger than the cache? If yes, each percent of bumping costs more per query. For this reason, the PHastR author recommends λ=4.25 as the default, which uses 0.04 more bits/key than λ=4.5. With λ=4.5, queries on 10⁹ keys were 10% slower.
• Do inserts and deletes mix? If yes, find out how tombstones are removed: by rebuilds, by F14-style counters, or by tombstone reuse. In long-running workloads, the cumulative inserts can go above the limit of the O(x²+c) analysis, so measure the cost in that range.
• Do many threads change the same table? If yes, check tombstone reuse, metadata bits per cell, whether lookups write to cells, and the behavior when the table is full.

The same questions apply to structures that move a colliding key to another candidate position. The cost of kick-out chains and rehashing in cuckoo hashing is in Cuckoo Hashing and Fingerprint Filters.

References

• PHastR: Faster Minimal Perfect Hashing with Rotated Layouts, arXiv:2610.17833 (2026-10, version 3)
• PHast – Perfect Hashing made fast, arXiv:2504.17918 (2025-04, ALENEX 2026)
• Space-Efficient Lock-Free Linear-Probing Hash Table, arXiv:2606.17315 (2026-06)
• Open-sourcing F14 for faster, more memory-efficient hash tables, Engineering at Meta (2019-04)

All numbers were checked against each original source as of 2026-10.

Summary

In the cases of this post, the cost changed with collision handling even when the hash function and the first-level query cost were the same. With the same hash function and seed width, PHastR added layouts and reduced bumping from 1.79% to 0.51%. As a result, space and query time on 10⁹ keys both decreased. The design of Attiya et al. uses duplicate cleanup, backward scans, and revalidation requests from lookups to reuse tombstones.

For static structures, this criterion fits best when the key set is large and the hash function mixes bits well. On small key sets, bumping costs less. For dynamic structures, the criterion fits when inserts and deletes mix, but the concurrency paper gives no measured performance. When you select a hash structure, check the bumping rate and the deleted-slot handling together with bits/key and the average probe count.