opthash 0.10.2

Rust implementations of Elastic Hashing and Funnel Hashing with Python bindings

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 std::collections::HashMap's API and support the same operations. Each map starts with zero allocation (new()) and grows dynamically 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)

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

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

  Each descriptor stores cached `ctrl_ptr`, `data_ptr`, capacity, plus
  per-shape metadata (salt, mask, etc). All slot/ctrl/SIMD ops live on
  the `ArenaSlots` trait (`src/common/arena.rs`).


ElasticHashMap
==============

  levels: Box<[Level]> (descriptors only)

    Level 0    ctrl_ptr, data_ptr, capacity (~half of total slots)
    Level 1    geometrically halved
    Level 2    ...

    per-level  group_count, group_count_mask, salt, len, tombstones,
               half_reserve_slot_threshold, budget_cap

  arena:       Arena (the single allocation backing every level above)

  map-wide     len, total_slots, max_insertions, reserve_fraction,
               batch_plan, current_batch_index, batch_remaining,
               max_populated_level, hash_builder, alloc


FunnelHashMap
=============

  levels: Box<[BucketLevel]> (descriptors)

    Level 0
      ctrl region   fp xx fp __ ... fp fp xx __ ... fp ...
      slot region   kv kv kv __ ... kv kv kv __ ... kv ...
                    └── bucket 0 ──┘└── bucket 1 ──┘
      (xx in ctrl marks a removed slot; the slot bytes may still hold
       the stale kv physically, but are logically uninit — never read.)

    Level 1    (same layout, smaller buckets)

    per-level  bucket_count_mask, bucket_size_log2, salt, len, tombstones

  special: SpecialArray

    primary    group-probed (paper B)
               group_count_mask, len, tombstones

    fallback   two-choice bucketed (paper C)
               bucket_count, bucket_size_log2, len, tombstones

  arena:       Arena (covers every level + both special regions)

  map-wide     len, total_slots, max_insertions, reserve_fraction,
               primary_probe_limit, max_populated_level, hash_builder, alloc

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.