opthash

Rust implementations of Elastic Hashing and Funnel Hashing from Optimal Bounds for Open Addressing Without Reordering (Farach-Colton, Krapivin, Kuszmaul, 2025).

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

Data Structures

• ElasticHashMap<K, V> — Multi-level table with geometrically halving levels. Keys are placed via batch-based insertion across levels using stride-based probing.
• FunnelHashMap<K, V> — Multi-level bucketed table with a 3/4-ratio geometric progression and a special overflow array (primary + fallback) for keys that don't fit in any level.

Both support insert, get, get_mut, contains_key, remove, and clear. Maps start with zero allocation (new()) and grow dynamically on demand.

Benchmarks

10,000 inserts and 20,000-entry maps for lookups, measured on Apple M1 (aarch64, NEON SIMD):

cargo bench --bench throughput

Usage

use opthash::{ElasticHashMap, FunnelHashMap};

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