🧊 FrozenDict

frozendict is a state of the art world's most memory-efficient immutable hashmap written in 100% safe Rust, with native Python and Node.js bindings 🗿.

🚀 Installation

🤔 What does this crate provide?

frozendict provides a fully immutable, hashable dictionary for Python and Node.js backed by a high-performance Rust core. It:

• Stores entries in a single contiguous sorted heap allocation, zero per-entry heap overhead.
• Looks up keys in O(log n) via binary search, no hashing, no pointer-chasing, excellent cache behaviour.
• Caches its hash at construction, repeated hash() calls are O(1).
• Integrates with Python's dict protocol (keys(), values(), items(), pickle, copy, | merge operator).
• Exposes a native Node.js FrozenDict class with TypeScript declarations via napi-rs.
• Provides functional update primitives: merge, with, without, intersection, union, difference.

💡 Why sorted slice + binary search?

Binary search beats hash-map lookup for maps with fewer than ~64 entries because it avoids hashing and pointer-chasing. For larger maps the memory savings (up to 2×) and cache locality more than compensate. See Cache-oblivious binary search and the AHash paper for background.

🦀 Rust

[dependencies]
frozendict = "2.1.1"

use frozendict::frozen_map::FrozenMap;

let map: FrozenMap<&str, i32> = FrozenMap::new([("b", 2), ("a", 1)]);
assert_eq!(map["a"], 1);
assert_eq!(map.len(), 2);

let updated = map.with("c", 3);
assert_eq!(updated.len(), 3);

let merged = updated.merge(&FrozenMap::new([("a", 99)]));
assert_eq!(merged["a"], 99);

For the full API reference see RUST.md.

🐍 Python

pip install frozndict

from frozndict import FrozenDict

d = FrozenDict({"a": 1, "b": 2})
print(d["a"])          # 1
print(hash(d))         # stable integer (pre-computed at construction)

d2 = d | {"c": 3}      # returns a new FrozenDict
print(d2.keys())

For full docs see PYTHON.md.

🟩 Node.js

npm install frozendict

const { frozenDict, FrozenDict } = require("frozendict");

const d = frozenDict({ a: 1, b: "hello", c: [1, 2, 3] });
console.log(d.get("a")); // 1
console.log(d.size); // 3
console.log(d.has("z")); // false

const d2 = d.merge({ d: true });
console.log(d2.size); // 4
console.log(d2.toJSON()); // '{"a":1,"b":"hello","c":[1,2,3],"d":true}'

For full docs see NODE.md.

🔭 Features

📊 Benchmarks

🚀 Performance Highlights

frozndict operates natively at the mathematical speed limits of the hardware, heavily outperforming its C counterparts and standard dictionary data structures on several fronts.

The following is a 1000-element dictionary micro-benchmark comparison in seconds per operation (smaller is better), measured on x86-64 Linux with LTO=fat, opt-level=3, codegen-units=1, panic=abort, target-cpu=native.

Benchmarked with timeit (min of 7 runs × 2 000 iterations). Python 3.12.

🏆 Fastest Iteration in Class

Keys are stored in a single contiguous sorted Box<[K]>, sequential iteration has perfect prefetch behaviour. At 1000 elements, frozndict iterates 1.9× faster than frozendict (C) and 3.5× faster than immutables.Map.

🏆 Smallest copy() Overhead

copy() and __deepcopy__() share the backing Arc<FrozenDictInner>, O(1), just an atomic reference count increment. At 64 ns, frozndict is 5× faster than frozendict (C) on copy.

Deterministic O(1) Pre-Computed Hashing

The dict-level hash is XOR-combined over all (k, v) pairs exactly once at construction via inline multiplicative mixing (0x9e3779b97f4a7c15, 0x517cc1b727220a95). Subsequent hash() calls are a single field read, O(1), allocating nothing.

O(1) Clone & Identity Equality

A shared Arc<FrozenDictInner> is re-used across the original, all copies, and frozendict(existing_fd) constructors. No data is ever duplicated. __eq__ short-circuits in O(1) via Arc::ptr_eq before comparing pre-computed hashes.

Smallest Memory Footprint

Entries sit in a SoA layout: a Box<[K]> for keys and a Box<[V]> for values, two contiguous allocations. Binary search only touches the key array: 2× smaller cache footprint compared to AoS layouts on large value types.

Infallible Rust-Level Immutability

Mutation is blocked at the Rust binary level. There are no &mut self methods, not just descriptor tricks.

Rust micro-benchmarks (cargo bench)

Run benchmarks yourself:

cargo bench                              # Rust
pip install frozndict frozendict immutables
python benchmarks/bench_compare.py      # Python comparison

🔒 Safety

This crate uses #![forbid(unsafe_code)] in all Rust modules except the Node.js FFI layer, which requires unsafe for napi-rs interop. Every other byte of implementation is safe Rust.

📚 Further Reading

• RUST.md: Rust API guide
• PYTHON.md: Python bindings guide
• NODE.md: Node.js bindings guide
• PACKAGING.md: Debian/RPM packaging
• Cache-oblivious binary search
• AHash: the underlying hasher
• napi-rs: Node.js native bindings framework
• PyO3: Rust-Python interop library
• Criterion.rs: benchmarking framework

📄 License

Licensed under the MIT License.