PaperlayerView exact revision on arXiv

Source-linked AI summary

MultiTable: A Faster Hash Table at any Physical Load Factor up to and Including One

Maksym Petkus

arXiv:2609.39233v1cs.CRcs.DSmath.COmath.PR

TL;DR

Hashbrown’s slot-based load factor and capacity doubling can leave substantial memory unused, even though a table’s physical footprint determines where its data fits. Multitable uses a stable cascade of fixed-size buckets, with configurable load and failure probability. At equal physical memory, filtered multitable leads hashbrown across 84 configurations, averaging 2.1× its throughput on raw bytes and 1.9× when hashbrown uses native integers.

  • Problem

    Hashbrown’s slot load and power-of-two capacity growth can leave its physical load low, while a table’s true byte footprint determines whether data fits in cache, RAM, or a lower storage tier.

    Source: §1 · pp. 1–2

  • Method

    Multitable hashes keys into fixed-size buckets and rehashes overflow into successively smaller levels, sizing each level with binomial tail bounds for a chosen failure probability.

    Source: §1 · p. 2

  • Results

    Across 84 configurations, filtered multitable beats hashbrown at equal physical memory, averaging 2.1× hashbrown’s throughput on raw bytes and 1.9× when hashbrown uses native integers.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    Multitable makes load factor and failure budget configurable, reaches physical load one, and supports incremental resizing without rehashing.

    Source: §1 · p. 2, §8 · p. 19

    The analysis assumes independent random hash values at every level, while the implementation reuses a single hash per lookup; that reuse is empirically checked but not proved.

    Source: §8 · p. 20

Abstract

from arXiv · show

We present \emph{multitable} and its Rust reference implementation: a stable hash table both materially faster at equal physical memory and more flexible than the SwissTable in its Rust's hashbrown implementation. As an arithmetic mean over 84 configurations it delivers $\mathbf{2.1\times}$ hashbrown's throughput when both hash the same raw bytes and $\mathbf{1.9\times}$ when hashbrown is keyed on native integers, its best case; on negative lookups alone, $3.2\times$ and $2.9\times$. Multitable reaches \textbf{any physical load factor} up to and \textbf{including one} ($0.9999$ demonstrated), exactly for the requested capacity, compared to hashbrown which doubles at $0.777$ for 4-byte keys and values. At $75\%$ saturation of hashbrown (assumed average case of its rigid ladder) and multitable sized to $0.97$ physical load factor, hashbrown takes $66\%$ more space. The lookup probe count has no cliff as the load factor approaches one. Bucket size, physical load factor, and failure budget are parameters, and the multitable can be grown without rehashing. We implement two variants of multitable: plain and filtered. At equal physical memory on an Apple M2 Pro the filtered multitable leads hashbrown in all $84$ insert, hit, and miss configurations. Multitable is more \textbf{memory-efficient}, at equal mixed-lookup throughput on the map of $4$-byte keys and values the filtered multitable needs up to $12\%$ fewer bytes than hashbrown, and the plain multitable is $18\%$ smaller, holding $\mathbf{22\%}$ more keys in the same memory.

1 Introduction

Hashbrown’s advertised load factor obscures its lower physical utilization and abrupt capacity doubling, while table footprint can determine which storage tier holds the data. Multitable uses a cascade of fixed-size buckets to make physical load configurable and reports faster throughput than hashbrown at equal memory.

1 Introduction

  • Hashbrown’s 7/8 slot load corresponds to physical load 7/9 ≈ 0.777 for maps with 4-byte keys and values, before padding and allocator rounding.Its power-of-two bucket count doubles when slot load reaches 7/8, rehashing every key.Source: §1 · p. 1
  • Multitable rehashes overflow keys into successively smaller levels of fixed-size buckets, with binomial tail bounds sizing levels to a chosen failure probability.The cascade ends in a single bucket; inserted keys remain stable and do not move.Source: §1 · p. 2
  • At equal physical memory, filtered multitable beats hashbrown in all 84 configurations, averaging 2.1× its throughput on raw bytes and 1.9× when hashbrown uses native integers.The configurations cover insertions, hits, and misses across maps and sets, 4- and 16-byte keys, and seven sizes.Source: §1 · pp. 2–3
  • At equal mixed-lookup throughput on 4-byte-key, 4-byte-value maps, filtered multitable needs up to 12% fewer bytes than hashbrown; plain multitable is 18% smaller in cache and holds 22% more keys.The averages of 2.1× and 1.9× throughput are over 84 configurations; negative lookups alone reach 3.2× and 2.9×, respectively.Source: §1 · p. 3
  • The paper also proposes incremental resizing and cache eviction, plus three strategies for deletion churn, two of which preserve stability.For continuous churn, the authors note that no scheme leaving stored keys in place sustains load factor one.Source: §1 · p. 3
  • Unlike funnel hashing, multitable treats bucket size, load factor, and failure budget as configurable, ends its cascade in one bucket, and is implemented and measured against hashbrown.For load 0.9, the cited example uses 5 levels, while funnel hashing’s formulas give 24 levels plus a special array.Source: §1 · p. 3

2 Intuition

Hashing keys into fixed-size buckets makes the number of keys per bucket concentrate around its mean, but sizing each bucket for rare overflow wastes space. Multitable recovers that slack by rehashing overflow into smaller levels, with bucket size chosen to suit the hardware.

2 Intuition

  • With n = 10 buckets and q = 100 keys, occupancy clusters around the mean λ = 10, so most buckets can hold fewer than the maximum without overflow.The expected number of buckets with exactly k keys is n P[Bin(q, 1/n) = k].Source: §2 · p. 3
  • A bucket should fit a hardware access unit and a SIMD register, making a bucket scan roughly one comparison’s time.The relevant units include cache lines, DRAM rows, SSD pages, and disk sectors.Source: §2 · pp. 3–4
  • Sizing every bucket for rare overflow wastes space: the example with s = 24 has load factor 100/240 ≈ 0.417.Larger buckets reduce relative variance, but wide reads are constrained by CPU-channel and SIMD width.Source: §2 · pp. 3–4
  • Rehashing overflow keys with a different seed creates a smaller instance of the same bucket problem, which cascades until the remainder fits in one final bucket.A single spare bucket can improve load, but growing overflow makes one oversized bucket or variable-size overflow slabs unattractive.Source: §2 · p. 4
  • At n = 10 and q = 100, over 99% of buckets are expected to hold at least 4 keys; concentration can fill every slot, but explicit tail bounds are needed for failure guarantees.The cascade trades deeper levels for higher load, with negative lookups probing one bucket per level.Source: Figure 1 · p. 4, §2 · p. 5, Figure 2 · p. 5

3 Construction and analysis

This section constructs and analyzes a multilevel bucket cascade to achieve high-probability slot occupancy and target loads below one while reducing lookup depth. It develops depth-reduction strategies and quantifies their per-level and tail failure guarantees, including the bucket cost of requiring no overflow at wrap-up.

3.1 Model

  • The analysis assumes independent uniform assignments across keys and levels, and reports an improvement over the classical s-subset multicollision bound as a side result.Bucket occupancies are multinomial, with each bucket’s marginal occupancy given by a binomial law.Source: §3.1 · pp. 5–6

3.2 A perfect table

  • The perfect construction allocates levels so expected underfull buckets stay within δ while preserving a final bucket; its total capacity is exactly the number of keys.Theorem 1 bounds the probability that all levels are saturated, which is the event on which every slot is occupied.Source: §3.2 · p. 7
  • With probability at least (1−δ)^(L−1) ≥ 1−(L−1)δ, the perfect construction stores every key and fills every slot, achieving slot load factor exactly 1.Conditioned on all levels being saturated, a miss probes all L levels; a uniformly chosen stored key has expected probe count determined by the levels’ stored-key counts.Source: §3.2 · pp. 7–8

3.3 An efficient table

  • The efficient construction sizes levels using the pointwise minimum of four overflow bounds, guaranteeing the target load α and storage of all q keys with probability at least (1−δ)^(L−1).The bound combines Markov’s inequality, bounded differences, and exponential tilting; capacity is fixed at construction, and the load guarantee holds on every non-failing run.Source: §3.3 · pp. 8–11
  • Conservative overflow quantiles can leave deep levels nearly empty, shortening positive lookups while negative lookups still traverse the tail.The tail truncation closes that gap early; the tilted bounds B3 and B4 also reduce depth through the pointwise minimum bound.Source: §3.3 · p. 11, §3.4 · p. 11

3.4 Depth reduction

  • Progressive overfill of top levels and a two-level tail truncation reduce cascade depth while retaining the per-level failure budget δ.The overfill factor r is tuned to minimize workload-weighted lookup cost; the implementation permits up to 0.5% budget overrun, with capacity cost bounded by the same amount.Source: §3.4 · pp. 11–12
  • With probability at least 1 − iδ, level i overflows by at most s and all q keys are stored, with capacity bounded by (23) truncated at level i.The construction allocates level i with n_i buckets and a final level with one bucket.Source: §3.4 · p. 12
  • The actual failure probability is L*δ, where L* counts levels whose chosen bound lies below the deterministic cap; for q = 10^5, s = 8, α = 0.9, δ = 2^-10, truncation closes at L = 13.The example cascade has 14 levels at load 0.900 and spends exactly the bucket budget ⌈q/(αs)⌉.Source: §3.4 · p. 12
  • At truncation i = 4, requiring no overflow at wrap-up needs 1128 buckets, whereas tolerating overflow of at most s and adding one bucket is cheaper.This comparison motivates keeping the final single-bucket level.Source: §3.4 · p. 12
  • At r = 1.025, progressive overfill and truncation close the cascade at L = 7 instead of 13 at load 0.900, reducing proven-bound sizing from 14 levels to 7.The remaining gap to the 5 levels of near-exact sizing is the cost of keeping a theorem behind every level.Source: §3.4 · p. 12

Asymptotics.

For each fixed configuration with α < 1, the cascade has logarithmic depth and constant expected positive-lookup probes. A computed overflow-quantile recipe closely tracks simulated quantiles and mainly reduces depth, while lookup cost has no cliff near full load.

Asymptotics.

  • For every fixed configuration (s, α, δ) with α < 1, the cascade has O(log q) levels and successful builds give O(1) expected probes for positive lookups.The constants depend only on (s, α, δ).Source: Asymptotics · p. 13

3.5 Near-exact overflow approximation

  • The approximation uses 1–3 fewer levels than bound-based sizing, including 5 versus 7 at α=0.9, while expected positive-lookup cost differs by at most about 1% of a probe.The comparison is under the overfill policy; at α=0.96 it flips in the bound’s favor.Source: §3.5 · p. 13
  • The approximate overflow quantile stays within 2 keys of the simulated quantile, but its configuration is checked by computation and simulation rather than a theorem.A four-way dispatch selects among exact enumeration, a deterministic bound, a Cornish–Fisher quantile, and a compound-Poisson tail.Source: §3.5 · p. 13
  • Unlike linear probing, multitable has no lookup cliff near full load; its level count rises from 3 at α=0.5 to 6 at α=0.96.The stated level-count growth is an observed rate, not a proven one.Source: §3.5 · p. 13

4 Resizing and cache eviction

Multitable can grow by prepending levels without moving or rehashing stored keys, and its levels can be removed as load falls. Its level structure also supports bulk eviction of the oldest entries.

4.1 Resizing

  • At n = 256 and s = 8, the approximation b Q stays within 2 keys of the exact and simulated quantiles where tractable, while the proven envelope is over twice b Q at λ = 1.75.The envelope runs 12–32% above b Q for 3 ≤ λ ≤ 8 and agrees within 0.2% from λ = 16.Source: Figure 4 · p. 14
  • Figure 5 compares expected positive-lookup probes and negative-lookup levels across target load factors when sizing uses either the full bound or the approximation b Q.Both sizing approaches use the overfill policy with r = 1.025.Source: Figure 5 · p. 14
  • Prepending a new level lets the table grow without moving or rehashing existing keys; later growth can add another level or remap only the newest one.Growth can be triggered as the tail fills, and level sizes can be chosen so capacity increases in increments rather than doubling.Source: §4.1 · pp. 13–14
  • Growth adds levels in chosen increments, and when deletions lower the load, the table can shed its smallest levels while reinserting their few keys.This avoids capacity changes being restricted to factors of two.Source: §4.1 · p. 14

4.2 Cache tables

  • A ring of equal-sized levels supports bulk eviction: the oldest level is cleared and recycled at the back, with no scans, rehashing, or timestamps.Long-lived entries tend to sit in higher levels, while recent entries tend to land deeper; entries can be kept alive by reinsertion.Source: §4.2 · p. 15

5 Implementation

The Rust implementation offers plain and filtered variants with configurable bucket size, key and value sizes, and load factor. In equal-memory benchmarks on an Apple M2 Pro, the filtered variant beats hashbrown across the reported configurations, while memory use and lookup trade-offs vary by variant and workload.

5 Implementation

  • The filtered variant adds a one-byte-per-slot filter that rejects most mismatching keys before comparison; the plain variant instead uses almost no metadata and scans keys with SIMD equality checks.The filter replaces the plain variant’s per-bucket length byte and uses all 8 bits as a hash fragment, reducing useless key comparisons.Source: §5 · p. 15
  • Sizing uses a per-level failure budget δ, with a worked example yielding a terminal-overflow bound of about 0.004 and no terminal overflow in 10^7 simulated builds.The authors describe the bounds as conservative and select δ so the bound is reasonable, relying on compounding slack for reliability.Source: §5 · p. 15

5.1 Performance

  • The equal-memory benchmark uses FxHasher on an Apple M2 Pro, with multitable and hashbrown footprints matched within 0.5% at nearly every size anchor.It tests insert, positive and negative lookups, and a half-hit, half-miss stream across four shapes and seven sizes per shape.Source: §5.1 · p. 16, Figure 6 · p. 16
  • For the 4+4-byte shape, the filtered multitable’s 56 per-operation speedup ratios all exceed parity, ranging from 1.27× to 4.33× against byte-keyed hashbrown and 1.20× to 3.95× against integer-keyed hashbrown.The Figure 7 panels plot speedup against stored key-value pairs, with separate panels for hashbrown’s byte and integer keyings.Source: §5.1 · p. 17, Figure 7 · p. 17
  • Across 84 equal-memory configurations—four shapes, seven sizes, and insert, hit, and miss operations—the filtered multitable led hashbrown in every cell, by 1.23–4.47× for byte keys and 1.08–3.95× for integer keys.Source: §5.1 · p. 17, Table 1 · p. 17
  • The filtered multitable’s geometric-mean speedups over the 84 ratios are 1.96× against byte-keyed and 1.75× against integer-keyed hashbrown; its miss advantage is largest at smaller sizes and narrows at the largest sizes without closing.The filter is most effective where it rejects misses before a key comparison.Source: §5.1 · p. 17
  • At shared bucket size s = 8, the plain multitable’s per-operation time is 1.13× the filtered variant’s on the 4-byte set and 2.35× on the 16+16-byte map; positive lookups are its weak operation for 16-byte keys.The filtered variant uses s = 16 as a hit-miss trade-off: positive-lookup time is 0.88× that at s = 8, while negative-lookup time increases by 5%.Source: §5.1 · pp. 17–18
  • At equal mixed-lookup throughput, the filtered multitable uses up to 12% fewer bytes than hashbrown, while the plain multitable uses 18% fewer bytes in cache and holds 22% more keys in the same memory.The campaign covers one machine and one baseline.Source: §5.1 · p. 18

6 Variations

The paper describes variations for storing large keys and for constraining lookup locality. Framing partitions the table into regions, with each frame built as a standalone multitable under a composed failure guarantee.

6 Variations

  • For large keys that need not be iterated over, the table can store a fixed-size hash instead of each key, with the usual false-positive trade-off.A framed table is also proposed when lookup should stay within one region, such as an SSD page, DRAM row, disk sector, or server.Source: §6 · p. 18
  • A framed table chooses bucket size, frame capacity, and failure budget, then builds each frame as a standalone multitable sized to fit its region.If the target load cannot be met, the frame is enlarged; the stated guarantee composes the per-frame bounds with a union bound.Source: §6 · p. 18
  • A lookup maps a key’s hash to one frame and performs an ordinary multitable lookup there, so each lookup touches a single region and frames can be parallelized.The same arithmetic with single-bucket frames yields a one-level table; up to s overflowing keys can be caught in one spare bucket.Source: §6 · p. 18
  • The spare bucket raises the maximum load factor at every bucket size shown, reaching 0.98 at s = 2048 for q ≈ 10^5.The reported load factor climbs steeply with s, which the passage identifies as the reason framed configurations favor large buckets.Source: §6 · p. 18

7 Deletion churn

Deletion churn makes a one-shot placement less reliable, so the paper presents three ways to restore or preserve capacity without routinely rebuilding the whole table. Each option addresses a different use case.

7 Deletion churn

  • Figure 8 compares the maximum load factor for zero overflow with sizing that tolerates up to s overflowed keys caught in one spare bucket.The overflow quantiles are computed using the dispatch described in Section 3.5.Source: Figure 8 · p. 19
  • A hoist pass restores a one-shot placement by reinserting keys from levels 2 through L into level 1, touching only those keys and requiring no additional memory.In the cited 10^5-key example, those keys are 43% of the table; unlike hashbrown’s rebuild, the pass is usable at any load without forcing a doubling above 0.5.Source: §7 · pp. 18–19
  • Under continuous churn, holes accumulate in top levels, and no scheme that leaves stored keys in place sustains load factor one.The model uses uniformly random deletion and fresh insertion at each step, with turnover defined as m steps for m live keys.Source: §7 · p. 19
  • The three options are hoisting on first overflow, growing by prepending a level as the tail fills, or sizing for q(1 + x) keys at a raised target load factor.The raised-load option holds up to q entries and, at its minimum target, a shape scored safe survives continuous churn.Source: §7 · p. 19

8 Conclusion

Multitable turns multicollision distributions into a configurable, high-load table and reports roughly twice hashbrown’s throughput at equal memory. Its analysis assumes independent per-level hash values, while the implementation reuses one hash per lookup; that shortcut is empirically checked but not proved.

8 Conclusion

  • At equal memory, filtered multitable averages 2.1× and 1.9× hashbrown’s throughput across 84 configurations, depending on whether hashbrown hashes raw bytes or native integers.Negative lookups reach 3.2× and 2.9×; inserts and positive lookups reach 1.3–1.6×.Source: §8 · p. 19
  • Multitable uses binomial-tail sizing to make slot load a parameter up to one, with a capacity chosen freely and local resizing and eviction.Its multicollision bound remains informative where the classical subset bound is vacuous.Source: §8 · p. 19
  • The analysis assumes independent hash values at every level, but the implementation derives all levels from one hash per lookup, a reuse shortcut verified empirically rather than proved.The authors identify formal treatment of this reuse as a natural next step.Source: §8 · p. 20

A Benchmark charts

The appendix reports benchmark charts spanning key and value sizes, load factors, and sizing variants. The results show where filtered and plain multitables compare with hashbrown and how throughput changes as physical load rises.

16+16-byte map

  • 1.87× and 1.73× are the filtered multitable’s average speedups on the 16+16-byte map, while plain wins only 4 of 28 cells against either hashbrown arm.With 16 bytes to compare per slot, the plain variant performs worst on this shape.Source: Figure 9 · p. 22, A Benchmark charts · p. 22

Set workload, 4-byte keys

  • 2.18× and 1.91× are the filtered multitable’s average speedups over byte-keyed and integer-keyed hashbrown on the 4-byte set; plain wins 25 and 23 of 28 cells, respectively.On negative lookups, plain averages 3.46× and 3.00×; it trails integer-keyed hashbrown on positive lookups.Source: Figure 10 · p. 23, A Benchmark charts · p. 23

Set workload, 16-byte keys

  • 1.85× and 1.71× are the filtered multitable’s average speedups on the 16-byte set; plain wins 9 and 6 of 28 cells against byte-keyed and integer-keyed hashbrown.A seventh insert cell against the integer-keyed arm is tied within 0.1%.Source: A Benchmark charts · p. 23, Figure 11 · p. 24

Load-factor sweep

  • At realized physical load 0.97, throughput gives up 6.1–25.2% from load 0.86 to 0.977, with no cliff as load approaches one.Only plain s = 8 in cache holds hashbrown’s reference throughput through realized load 0.937, using 18% fewer bytes.Source: A Benchmark charts · p. 23, Figure 12 · p. 24

Sizing variants

  • On a favorable sizing ladder, rounding every level to a power of two changes median mixed-lookup throughput by +0.6%; on an adversarial ladder, it cedes 14.2% median.The first-level-only variant is no better: −1.3% on the favorable ladder and −15.2% on the adversarial one.Source: A Benchmark charts · pp. 23, 25, Figure 13 · p. 25

B Asymptotics

The asymptotic analysis bounds cascade depth and positive-lookup cost for fixed bucket size, load factor, and failure probability. Its constants worsen as the target load approaches one, and it does not cover the perfect table’s load-one regime.

Asymptotic bounds

  • For fixed configuration, cascade depth grows logarithmically in the number of keys, while a positive lookup takes a constant expected number of probes.The positive-lookup result is conditioned on Theorem 3’s event and applies when q ≥ T.Source: B Asymptotics · pp. 25–26

Logarithmic depth

  • For inputs o ≥ T, choosing n* = floor(βo/s) is feasible and forces overflow to contract by factor c; below T, each level loses at least s keys.The proof uses a fixed tilt θ = 2/s and an additive ln(1/δ) slack cost.Source: B Asymptotics · pp. 25–26

Bound limitation

  • The depth bound is asymptotic in q for fixed (s, α, δ), and its constants degrade as α approaches one.It says nothing about the perfect table’s α = 1 regime; at (8, 0.9, 2^-10), the bound gives L ≤ 626 for q = 10^5, while the constructed cascade has 14 levels.Source: B Asymptotics · p. 26

C An improved multicollision bound

The section improves a multicollision probability bound by using binomial bucket-load tails. The improvement matters in the loaded regime, where the classical subset bound can become vacuous.

Improved bound

  • The binomial-tail bound is never worse than the subset bound and strictly dominates it in the loaded regime.At n = 10 and q = 100, for s = 20 the subset bound gives 54 while the improved bound gives 0.020.Source: C An improved multicollision bound · p. 27
  • For all 1 ≤ s ≤ q and n ≥ 1, the probability of an s-collision is bounded using n P[Bin(q, 1/n) ≥ s].The bound follows by applying Markov’s inequality to the number of buckets holding at least s keys.Source: C An improved multicollision bound · p. 27

When the improvement matters

  • The subset bound and binomial-tail bound agree to leading order when q is small relative to n, and their gap opens as the table becomes loaded.The bounds also represent expected counts of overloaded buckets, so the comparison applies to uses of Lemma 1 in the paper.Source: C An improved multicollision bound · p. 27

D Deferred proofs

The deferred proofs bound bucket overflow and use those bounds to establish storage guarantees for the multilevel table. They also compare the multicollision bound with the s-subset bound.

D Deferred proofs

  • The expected overflow of n buckets is n times the expected excess of a Bin(q, 1/n) occupancy over s.The proof expresses the excess using the event that occupancy is at least s + 1, then conditions on one key landing in a given bucket.Source: D Deferred proofs · p. 27
  • For s = 20 and n = 10, the s-subset bound is vacuous by q = 85, while the paper’s bound remains informative through q = 147.The comparison is shown on log-log axes.Source: Figure 14 · p. 28
  • Negative association bounds the overflow tail by an exponential-moment argument, with an analogous bound for unfilled slots.Overflow is the sum of per-bucket excesses; applying Markov’s inequality to its exponential gives the tail bound.Source: D Deferred proofs · p. 28
  • The overflow-bound procedure takes the minimum of five candidates, including expectation, concentration, and deterministic-capacity bounds.For one bucket, the cap (q − s)+ is attained exactly and is the minimum candidate.Source: D Deferred proofs · p. 28
  • The level-by-level construction succeeds with probability at least (1 − δ)^(L−1), and its final bucket stores the remaining keys without further overflow.The proof conditions successively on prior levels staying within their overflow bounds, then uses the final level’s capacity of s slots.Source: D Deferred proofs · pp. 28–29

E Deletion churn: model and measurements

The churn analysis models insert flow through cascading buckets and evaluates overload sizing against terminal overflow. Tests support the model for selected overload shapes, while thin tails and fill transients remain important qualifications.

E Deletion churn: model and measurements

  • The churn model treats each bucket as a loss system: arrivals offered at load a encounter a Poisson occupancy truncated at s, and the blocked fraction is the bucket’s blocking probability.The appendix’s measurements use 20 turnovers and halt at the first terminal overflow; the default workload is a delete followed by an insert at constant table size.Source: E Deletion churn: model and measurements · p. 29
  • The mean-field model sets flow fluctuations to zero and estimates level-i offered load as y_i = mρ_i/n_i.The fraction of inserts reaching level i follows the preceding levels’ full-bucket fractions; the model then applies each bucket’s blocking probability.Source: E Deletion churn: model and measurements · p. 29
  • Overload sizing redistributes buckets toward deeper levels; at intended load 0.80, α′ = 0.934 gives a realized load of 0.791 and a predicted D of 3.3 × 10^-23.That shape uses about 1% more slots than the exact-load-0.80 target; with exactly q/α slots, α′ = 0.93 is unsafe, while α′ = 0.94 is the lowest target reported safe across the tested window.Source: E Deletion churn: model and measurements · p. 30
  • Table 3 reports the lowest churn-safe α′ for each intended load and bucket size at 220 keys, with safety defined as D < 10^-12 for shapes using q/α to 1.01q/α slots.The grid search varies α′ and overload x; the constructor converts physical load φ′ to slot-load target α′ according to whether the filtered or plain arm is used.Source: E Deletion churn: model and measurements · pp. 30–31, Table 3 · p. 31
  • The 17 tested overload shapes saw no failure across the reported 4,000-seed and 100-seed tests, with bounds of 1.87 × 10^-9 and 1.43 × 10^-9 per step.The measured mean levels were within 0.001 of the model; the single-bucket last level never held more than two keys.Source: E Deletion churn: model and measurements · p. 31
  • The fluctuation correction accounts for random offered load and bursty overflow; the reported mean field alone can underestimate thin-tail failure rates by up to thirteen orders of magnitude.The model tracks flow variance using a Gamma approximation, but its tail assumption remains a qualification when the final level is nearly empty.Source: E Deletion churn: model and measurements · pp. 31–32
  • Across the tested thin-tail shapes, predicted failure rates were 2.1–7.6 times measured rates, while all 17 overload shapes were predicted safe.The model does not include the fill transient, and the Gamma-tail assumption carries the failure-rate estimate when the last level is nearly empty.Source: E Deletion churn: model and measurements · p. 32

F Comparison with funnel hashing

Funnel hashing and multitable share a cascade of shrinking bucket levels, but differ in their tails, parameter choices, guarantees, and purposes. The paper contrasts funnel hashing’s theoretical probe-complexity result with multitable’s explicit sizing and measured implementation.

F Comparison with funnel hashing

  • Funnel hashing adds a special array after its geometric bucket levels, whereas multitable ends in a single bucket and supports deletions while retaining stability.Funnel hashing’s special array combines a uniform-probing portion with a two-choice bucket portion.Source: F Comparison with funnel hashing · p. 32
  • Funnel hashing fixes bucket size, level count, and shrink ratio through its proof, while multitable selects bucket size, load, and per-level failure budget for the application.Multitable sizes each level from an occupancy-tail bound rather than a fixed ratio between consecutive levels.Source: F Comparison with funnel hashing · p. 32
  • With the funnel’s bucket size, multitable uses 5 levels at 1 − α = 0.1 and 6 at 1 − α = 2^-5, versus 24 and 30 levels plus a special array for funnel hashing.These are practical-size comparisons, not asymptotic comparisons; multitable’s cascade has O(log q) levels for a fixed configuration.Source: F Comparison with funnel hashing · p. 32
  • Funnel hashing proves worst-case expected probe complexity Θ(log2(1/(1−α))) and reports no implementation or measurements; multitable is measured ahead of hashbrown in all 84 benchmark configurations at equal physical memory.Multitable’s comparison uses physical load, counting metadata in allocated bytes, rather than slot-load accounting alone.Source: F Comparison with funnel hashing · p. 33
Loading 2609.39233v1…