opthash

Rust implementations of Elastic Hashing and Funnel Hashing from Optimal Bounds for Open Addressing Without Reordering (Farach-Colton, Krapivin, Kuszmaul, 2025) — see References [^fkk2025].

Both are open-addressing hash maps that achieve optimal expected probe complexity without reordering elements after insertion.

Data Structures

Both maps share a common core: a single-Arena allocation per map indexed by per-level descriptors, 7-bit fingerprint control bytes, SIMD control-byte scans for occupancy + lookup, and tombstone accounting [^swisstable] [^cppcon2017] [^hashbrown]. Per-level salt re-randomization [^cw1979] decorrelates probe paths across levels. The default BuildHasher is foldhash [^foldhash]. The two maps differ in how they probe within a level:

ElasticHashMap<K, V> — Levels with geometrically halving capacities, each probed by a SwissTable-style triangular sequence ((idx + delta) & mask); inserts follow a per-level probe budget.
FunnelHashMap<K, V> — Bucketed levels (paper §5): a key maps to one bucket per level; overflow spills to the next level, not other buckets. Plus a split special array: primary (odd-step group probe) and fallback (two-choice buckets).

Both maps mirror the std::collections::HashMap API. Each starts with zero allocation (new()) and grows on demand; the reserve_fraction headroom knob is exposed via dedicated constructors.

Usage

Rust

cargo add opthash

use opthash::{ElasticHashMap, FunnelHashMap};

let mut map = ElasticHashMap::new();
map.insert("key", 42);
assert_eq!(map.get("key"), Some(&42));

let mut map = ElasticHashMap::with_capacity_and_reserve_fraction(1024, 0.10);
map.insert("key", 42);
assert_eq!(map.get("key"), Some(&42));

let mut map = FunnelHashMap::with_capacity_and_reserve_fraction(1024, 0.10);
map.insert("key", 42);
assert_eq!(map.get("key"), Some(&42));

Python

pip install opthash

from opthash import ElasticHashMap, FunnelHashMap

m = ElasticHashMap()
m["key"] = 42
assert m["key"] == 42
assert "key" in m and len(m) == 1

m = ElasticHashMap.with_options(capacity=1024, reserve_fraction=0.10)

m = FunnelHashMap.with_options(capacity=1024, reserve_fraction=0.10)

Layout Sketch

Arena (one allocation per map)
==============================

  fp = fingerprint (7-bit control byte)   kv = key-value entry
  __ = empty (CTRL_EMPTY 0x00)            xx = tombstone (CTRL_TOMBSTONE 0x80)
  a tombstoned kv may still sit in its slot physically, but is logically uninit

  Control bytes pack first, then alignment padding so the slot region starts
  at align_of::<SlotEntry<K, V>>(), then the slots:

  arena::ptr ► [fp fp xx __ ... ][fp xx fp __ ...][fp fp ...][  pad  ][kv kv kv ...][kv ... ]
               └─── ctrl L0 ────┘└─── ctrl L1 ───┘└── ... ──┘         └─ slots L0 ─┘└─ ... ─┘
               ▲ each level descriptor caches ctrl_ptr + data_ptr into the arena.

  All slot/ctrl/SIMD ops live on the ArenaSlots trait (src/common/arena.rs).


ElasticHashMap — geometrically halving levels
=============================================

  Box<[Level]> over the arena; each level ~half the previous, probed by a
  SwissTable triangular sequence (idx → idx+1 → idx+3 ... & mask). A full
  level sends the key down to the next:

    L0  [################################]  ~half of all slots
    L1  [################]
    L2  [########]
    L3  [####]
    ...


FunnelHashMap — fixed-width buckets, overflow down the funnel
=============================================================

  Box<[BucketLevel]>; each level is a grid of β-wide buckets. A key hashes
  to one bucket per level (levels salt independently); a full bucket spills
  the key to the next level. β is fixed, so levels differ only in bucket count:

    key
     │  hashed independently to one β-wide bucket per level
     ▼
    L0  [b0][b1][b2][b3][b4][b5] ┐ bucket full?
    L1  [b0][b1][b2]             ▼ rehash to next level
    L2  [b0]
    special ─► primary (group-probed · paper B) → fallback (two-choice · paper C)

  within one level (buckets sit side by side in the ctrl/slot regions):

    ctrl  fp xx fp __ ... fp fp xx __ ...
    slot  kv kv kv __ ... kv kv kv __ ...
          └── bucket 0 ──┘└── bucket 1 ──┘

Benchmarks

See benches/README.md for comparison charts.

References

[^fkk2025]: Martín Farach-Colton, Andrew Krapivin, William Kuszmaul. Optimal Bounds for Open Addressing Without Reordering (2025). arXiv: https://arxiv.org/abs/2501.02305. Establishes the elastic and funnel hashing schemes implemented in src/elastic.rs and src/funnel.rs; the funnel "special array" split into primary (group-probed, paper B) and fallback (two-choice, paper C) follows the paper's construction directly.

[^cw1979]: J. Lawrence Carter, Mark N. Wegman. Universal Classes of Hash Functions (STOC 1977 / JCSS 1979). DOI: https://doi.org/10.1016/0022-0000(79)90044-8. Foundational hash-based probing model the FKK bounds rely on; the per-level salt re-randomization in Level/BucketLevel (see level_salt in src/common/math.rs) follows the universal-hashing assumption.

[^swisstable]: Abseil. SwissTable design notes. https://abseil.io/about/design/swisstables. Source of the 7-bit fingerprint control-byte layout + SIMD group scans used by the shared ArenaSlots trait (see src/common/arena.rs, src/common/control.rs, src/common/simd.rs) and the triangular (idx + delta) & mask probe sequence used in Level::triangular_group_start.

[^cppcon2017]: Matt Kulukundis. Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step (CppCon 2017). https://www.youtube.com/watch?v=ncHmEUmJZf4. Talk introducing the SwissTable design referenced above.

[^hashbrown]: hashbrown — Rust port of SwissTable. https://github.com/rust-lang/hashbrown. Used as the absolute throughput ceiling in the Criterion benches (see benches/README.md).

[^foldhash]: foldhash crate. https://crates.io/crates/foldhash. Default BuildHasher (foldhash::fast::RandomState) wired up in src/common/mod.rs.

opthash 0.10.3