Expand description
§🧊 FrozenDict
frozendictis 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
| Platform | Command |
|---|---|
| Rust library | cargo add frozendict |
| Python | pip install frozndict |
| Node.js | npm i frozendict |
| Debian/Ubuntu | Download .deb from GitHub Releases |
| RHEL/Fedora | Download .rpm from GitHub Releases |
§🤔 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
FrozenDictclass with TypeScript declarations via napi-rs. - Provides functional update primitives:
merge,with,without,intersection,union,difference.
§💡 Why sorted slice + binary search?
| Property | FrozenMap (this crate) | HashMap / BTreeMap |
|---|---|---|
| Memory overhead | Zero: exactly n × entry_size | 1.5-2× allocator overhead |
| Allocation count | One at construction | One per entry (BTreeMap) |
| Lookup | O(log n) binary search | O(1) / O(log n) |
| Cache behaviour | Excellent: sequential prefetch | Pointer-chasing on tree nodes |
| Mutation | Impossible by design | &mut self methods exist |
| Hash stability | O(1): pre-computed at init | O(n) on every hash() call |
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 frozndictfrom 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 frozendictconst { 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
| Feature | Default | Description |
|---|---|---|
python | ❌ | Python extension module via PyO3/maturin |
node | ❌ | Node.js native add-on via napi-rs |
§📊 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.
| Operation (1000 items) | Python dict | frozendict (C) | immutables.Map | frozndict 🧊 |
|---|---|---|---|---|
| Construction | 6.41 µs 🏆 | 7.73 µs | 244.91 µs | 98.72 µs |
| Clone O(1) | 6.37 µs | 69.13 ns 🏆 | 411.89 ns | 117.24 ns |
| Equality | 19.18 µs | 19.61 µs | 24.39 ns 🏆 | 34.92 ns |
| Iteration | 7.10 µs | 7.19 µs | 14.89 µs | 4.13 µs 🏆 |
| copy() | 6.45 µs | 323.22 ns | 310.04 µs | 63.25 ns 🏆 |
| hash() | N/A | 168.11 ns | 45.38 ns | 45.25 ns 🏆 |
| Lookup | 33.33 ns 🏆 | 56.03 ns | 47.48 ns | 82.98 ns |
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)
| Benchmark | Time |
|---|---|
construction/4 | ~105 ns |
construction/64 | ~821 ns |
construction/1024 | ~16.1 µs |
construction/65536 | ~1.32 ms |
lookup/hit/4 | ~5.94 ns |
lookup/hit/64 | ~5.83 ns |
lookup/hit/1024 | ~5.87 ns |
lookup/hit/65536 | ~5.83 ns |
lookup/miss/64 | ~6.48 ns |
lookup/miss/65536 | ~6.51 ns |
iteration/keys/65536 | ~20.8 µs |
iteration/values/65536 | ~20.8 µs |
iteration/items/65536 | ~56.2 µs |
hash/precomputed/65536 | ~13.1 ns |
equality/equal/16384 | ~4.82 µs |
equality/unequal/16384 | ~969 ps |
functional/merge/256 | ~7.31 µs |
functional/with/4096 | ~64.6 µs |
functional/without/4096 | ~79.7 µs |
fromkeys/4096 | ~56.9 µs |
string_keys/lookup/hit_1024 | ~12.9 ns |
string_keys/lookup/miss_1024 | ~5.58 ns |
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.
§frozendict Rust Documentation 🦀
The frozendict Rust crate provides a fully immutable, hashable, sorted-slice
key-value store available as both a Rust library and the core backing all
language bindings.
§📦 Installation
[dependencies]
frozendict = "2.1.1"§🗂 Module Structure
The frozen_map public module is split into focused sub-modules:
| Sub-module | Contents |
|---|---|
frozen_map::slot | Slot, EMPTY, MIX_KEY/VAL, probe_capacity, table_insert |
frozen_map (map) | FrozenMap struct: construction, O(1) lookup, functional updates |
frozen_map (iter) | IntoIterator (owned + borrowed), FromIterator |
frozen_map (fmt) | Debug, Display, pretty_repr |
frozen_map (ops) | Default, Hash, PartialEq, Eq, Index |
§🛠 Core Data Structure: FrozenMap<K, V>
§Construction
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);§fromkeys (Python-compatible)
use frozendict::frozen_map::FrozenMap;
let map = FrozenMap::fromkeys(["x", "y", "z"], 0_i32);
assert_eq!(map["x"], 0);§Lookup
use frozendict::frozen_map::FrozenMap;
let map: FrozenMap<&str, i32> = FrozenMap::new([("a", 1)]);
assert_eq!(map.get("a"), Some(&1));
assert_eq!(map.get("b"), None);
let (key, val) = map.get_key_value("a").unwrap();
assert_eq!(key, &"a");§Iteration
use frozendict::frozen_map::FrozenMap;
let map: FrozenMap<&str, i32> = FrozenMap::new([("b", 2), ("a", 1)]);
let keys: Vec<_> = map.keys().collect(); // [&"a", &"b"]
let vals: Vec<_> = map.values().collect(); // [&1, &2]
let items: Vec<_> = map.items().collect(); // [(&"a", &1), (&"b", &2)]
for (k, v) in &map {
println!("{k}: {v}");
}§Hashing
use frozendict::frozen_map::FrozenMap;
use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;
let map: FrozenMap<&str, i32> = FrozenMap::new([("a", 1)]);
println!("{}", map.precomputed_hash()); // O(1): pre-computed at construction§Equality
use frozendict::frozen_map::FrozenMap;
let m1: FrozenMap<&str, i32> = FrozenMap::new([("a", 1), ("b", 2)]);
let m2: FrozenMap<&str, i32> = FrozenMap::new([("b", 2), ("a", 1)]);
assert_eq!(m1, m2); // order-independent; short-circuits on hash mismatch§Functional Updates
All these methods return a new FrozenMap; the original is never modified.
use frozendict::frozen_map::FrozenMap;
let a: FrozenMap<&str, i32> = FrozenMap::new([("a", 1), ("b", 2)]);
// merge: other's values win on key collision
let merged = a.merge(&FrozenMap::new([("b", 99), ("c", 3)]));
assert_eq!(merged["b"], 99);
assert_eq!(merged["c"], 3);
// with: add or overwrite a single key
let extended = a.with("c", 3);
assert_eq!(extended.len(), 3);
// without: remove a single key
let reduced = a.without("a");
assert!(!reduced.contains_key("a"));
// intersection: keep keys present in both, values from self
let b: FrozenMap<&str, i32> = FrozenMap::new([("b", 99)]);
let inter = a.intersection(&b);
assert_eq!(inter.len(), 1);
assert_eq!(inter["b"], 2);
// union: all keys, self has priority on collision
let u = a.union(&FrozenMap::new([("b", 99), ("c", 3)]));
assert_eq!(u["b"], 2); // self wins
assert_eq!(u["c"], 3);
// difference: remove all keys present in other
let b2: FrozenMap<&str, i32> = FrozenMap::new([("b", 0)]);
let diff = a.difference(&b2);
assert_eq!(diff.len(), 1);
assert_eq!(diff["a"], 1);§Index operator
use frozendict::frozen_map::FrozenMap;
let map: FrozenMap<&str, i32> = FrozenMap::new([("a", 1)]);
assert_eq!(map["a"], 1);
// map["z"] would panic§Display and Debug
use frozendict::frozen_map::FrozenMap;
let map: FrozenMap<&str, i32> = FrozenMap::new([("a", 1)]);
println!("{map:?}"); // frozendict({"a": 1})
println!("{map}"); // frozendict({a: 1})
println!("{}", map.pretty_repr(4));§FromIterator / IntoIterator
use frozendict::frozen_map::FrozenMap;
let map: FrozenMap<&str, i32> = [("a", 1), ("b", 2)].into_iter().collect();
// Consuming iteration
for (k, v) in map {
println!("{k}: {v}");
}§📖 API Complexity Table
| Method | Time | Notes |
|---|---|---|
new(entries) | O(n log n) | Sort + linear dedup, no BTreeMap |
fromkeys(keys, value) | O(n log n) | |
len() | O(1) | |
is_empty() | O(1) | |
get(key) | O(1) amortised | Open-addressing probe table |
get_key_value(key) | O(1) amortised | |
contains_key(key) | O(1) amortised | |
keys() / values()/items() | O(n) | Full iteration |
precomputed_hash() | O(1) | Cached at construction |
hash(state) (trait) | O(1) | |
eq() (PartialEq) | O(1) / O(n) | O(1) if hash differs, O(n) otherwise |
merge(other) | O((m+n) log(m+n)) | |
with(key, val) | O(n log n) | |
without(key) | O(n log n) | |
intersection(other) | O(n log m) | |
union(other) | O((m+n) log(m+n)) | |
difference(other) | O(n log m) | |
pretty_repr(n) | O(n chars) | |
clone() | O(n) | |
IntoIterator (owned) | O(n) | |
IntoIterator (ref) | O(n) |
§📊 Running Benchmarks
# All benchmark groups
cargo bench
# Targeted group
cargo bench -- construction
cargo bench -- lookup
cargo bench -- functionalResults written to target/criterion/ as interactive HTML reports.
§🔒 Safety
All Rust code outside the napi-rs FFI layer uses #![forbid(unsafe_code)].
§🔗 See Also
§🧊 FrozenDict
frozendictis 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
| Platform | Command |
|---|---|
| Rust library | cargo add frozendict |
| Python | pip install frozndict |
| Node.js | npm i frozendict |
| Debian/Ubuntu | Download .deb from GitHub Releases |
| RHEL/Fedora | Download .rpm from GitHub Releases |
§🤔 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
FrozenDictclass with TypeScript declarations via napi-rs. - Provides functional update primitives:
merge,with,without,intersection,union,difference.
§💡 Why sorted slice + binary search?
| Property | FrozenMap (this crate) | HashMap / BTreeMap |
|---|---|---|
| Memory overhead | Zero: exactly n × entry_size | 1.5-2× allocator overhead |
| Allocation count | One at construction | One per entry (BTreeMap) |
| Lookup | O(log n) binary search | O(1) / O(log n) |
| Cache behaviour | Excellent: sequential prefetch | Pointer-chasing on tree nodes |
| Mutation | Impossible by design | &mut self methods exist |
| Hash stability | O(1): pre-computed at init | O(n) on every hash() call |
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 frozndictfrom 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 frozendictconst { 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
| Feature | Default | Description |
|---|---|---|
python | ❌ | Python extension module via PyO3/maturin |
node | ❌ | Node.js native add-on via napi-rs |
§📊 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.
| Operation (1000 items) | Python dict | frozendict (C) | immutables.Map | frozndict 🧊 |
|---|---|---|---|---|
| Construction | 6.41 µs 🏆 | 7.73 µs | 244.91 µs | 98.72 µs |
| Clone O(1) | 6.37 µs | 69.13 ns 🏆 | 411.89 ns | 117.24 ns |
| Equality | 19.18 µs | 19.61 µs | 24.39 ns 🏆 | 34.92 ns |
| Iteration | 7.10 µs | 7.19 µs | 14.89 µs | 4.13 µs 🏆 |
| copy() | 6.45 µs | 323.22 ns | 310.04 µs | 63.25 ns 🏆 |
| hash() | N/A | 168.11 ns | 45.38 ns | 45.25 ns 🏆 |
| Lookup | 33.33 ns 🏆 | 56.03 ns | 47.48 ns | 82.98 ns |
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)
| Benchmark | Time |
|---|---|
construction/4 | ~105 ns |
construction/64 | ~821 ns |
construction/1024 | ~16.1 µs |
construction/65536 | ~1.32 ms |
lookup/hit/4 | ~5.94 ns |
lookup/hit/64 | ~5.83 ns |
lookup/hit/1024 | ~5.87 ns |
lookup/hit/65536 | ~5.83 ns |
lookup/miss/64 | ~6.48 ns |
lookup/miss/65536 | ~6.51 ns |
iteration/keys/65536 | ~20.8 µs |
iteration/values/65536 | ~20.8 µs |
iteration/items/65536 | ~56.2 µs |
hash/precomputed/65536 | ~13.1 ns |
equality/equal/16384 | ~4.82 µs |
equality/unequal/16384 | ~969 ps |
functional/merge/256 | ~7.31 µs |
functional/with/4096 | ~64.6 µs |
functional/without/4096 | ~79.7 µs |
fromkeys/4096 | ~56.9 µs |
string_keys/lookup/hit_1024 | ~12.9 ns |
string_keys/lookup/miss_1024 | ~5.58 ns |
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.
§frozendict Rust Documentation 🦀
The frozendict Rust crate provides a fully immutable, hashable, sorted-slice
key-value store available as both a Rust library and the core backing all
language bindings.
§📦 Installation
[dependencies]
frozendict = "2.1.1"§🗂 Module Structure
The frozen_map public module is split into focused sub-modules:
| Sub-module | Contents |
|---|---|
frozen_map::slot | Slot, EMPTY, MIX_KEY/VAL, probe_capacity, table_insert |
frozen_map (map) | FrozenMap struct: construction, O(1) lookup, functional updates |
frozen_map (iter) | IntoIterator (owned + borrowed), FromIterator |
frozen_map (fmt) | Debug, Display, pretty_repr |
frozen_map (ops) | Default, Hash, PartialEq, Eq, Index |
§🛠 Core Data Structure: FrozenMap<K, V>
§Construction
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);§fromkeys (Python-compatible)
use frozendict::frozen_map::FrozenMap;
let map = FrozenMap::fromkeys(["x", "y", "z"], 0_i32);
assert_eq!(map["x"], 0);§Lookup
use frozendict::frozen_map::FrozenMap;
let map: FrozenMap<&str, i32> = FrozenMap::new([("a", 1)]);
assert_eq!(map.get("a"), Some(&1));
assert_eq!(map.get("b"), None);
let (key, val) = map.get_key_value("a").unwrap();
assert_eq!(key, &"a");§Iteration
use frozendict::frozen_map::FrozenMap;
let map: FrozenMap<&str, i32> = FrozenMap::new([("b", 2), ("a", 1)]);
let keys: Vec<_> = map.keys().collect(); // [&"a", &"b"]
let vals: Vec<_> = map.values().collect(); // [&1, &2]
let items: Vec<_> = map.items().collect(); // [(&"a", &1), (&"b", &2)]
for (k, v) in &map {
println!("{k}: {v}");
}§Hashing
use frozendict::frozen_map::FrozenMap;
use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;
let map: FrozenMap<&str, i32> = FrozenMap::new([("a", 1)]);
println!("{}", map.precomputed_hash()); // O(1): pre-computed at construction§Equality
use frozendict::frozen_map::FrozenMap;
let m1: FrozenMap<&str, i32> = FrozenMap::new([("a", 1), ("b", 2)]);
let m2: FrozenMap<&str, i32> = FrozenMap::new([("b", 2), ("a", 1)]);
assert_eq!(m1, m2); // order-independent; short-circuits on hash mismatch§Functional Updates
All these methods return a new FrozenMap; the original is never modified.
use frozendict::frozen_map::FrozenMap;
let a: FrozenMap<&str, i32> = FrozenMap::new([("a", 1), ("b", 2)]);
// merge: other's values win on key collision
let merged = a.merge(&FrozenMap::new([("b", 99), ("c", 3)]));
assert_eq!(merged["b"], 99);
assert_eq!(merged["c"], 3);
// with: add or overwrite a single key
let extended = a.with("c", 3);
assert_eq!(extended.len(), 3);
// without: remove a single key
let reduced = a.without("a");
assert!(!reduced.contains_key("a"));
// intersection: keep keys present in both, values from self
let b: FrozenMap<&str, i32> = FrozenMap::new([("b", 99)]);
let inter = a.intersection(&b);
assert_eq!(inter.len(), 1);
assert_eq!(inter["b"], 2);
// union: all keys, self has priority on collision
let u = a.union(&FrozenMap::new([("b", 99), ("c", 3)]));
assert_eq!(u["b"], 2); // self wins
assert_eq!(u["c"], 3);
// difference: remove all keys present in other
let b2: FrozenMap<&str, i32> = FrozenMap::new([("b", 0)]);
let diff = a.difference(&b2);
assert_eq!(diff.len(), 1);
assert_eq!(diff["a"], 1);§Index operator
use frozendict::frozen_map::FrozenMap;
let map: FrozenMap<&str, i32> = FrozenMap::new([("a", 1)]);
assert_eq!(map["a"], 1);
// map["z"] would panic§Display and Debug
use frozendict::frozen_map::FrozenMap;
let map: FrozenMap<&str, i32> = FrozenMap::new([("a", 1)]);
println!("{map:?}"); // frozendict({"a": 1})
println!("{map}"); // frozendict({a: 1})
println!("{}", map.pretty_repr(4));§FromIterator / IntoIterator
use frozendict::frozen_map::FrozenMap;
let map: FrozenMap<&str, i32> = [("a", 1), ("b", 2)].into_iter().collect();
// Consuming iteration
for (k, v) in map {
println!("{k}: {v}");
}§📖 API Complexity Table
| Method | Time | Notes |
|---|---|---|
new(entries) | O(n log n) | Sort + linear dedup, no BTreeMap |
fromkeys(keys, value) | O(n log n) | |
len() | O(1) | |
is_empty() | O(1) | |
get(key) | O(1) amortised | Open-addressing probe table |
get_key_value(key) | O(1) amortised | |
contains_key(key) | O(1) amortised | |
keys() / values()/items() | O(n) | Full iteration |
precomputed_hash() | O(1) | Cached at construction |
hash(state) (trait) | O(1) | |
eq() (PartialEq) | O(1) / O(n) | O(1) if hash differs, O(n) otherwise |
merge(other) | O((m+n) log(m+n)) | |
with(key, val) | O(n log n) | |
without(key) | O(n log n) | |
intersection(other) | O(n log m) | |
union(other) | O((m+n) log(m+n)) | |
difference(other) | O(n log m) | |
pretty_repr(n) | O(n chars) | |
clone() | O(n) | |
IntoIterator (owned) | O(n) | |
IntoIterator (ref) | O(n) |
§📊 Running Benchmarks
# All benchmark groups
cargo bench
# Targeted group
cargo bench -- construction
cargo bench -- lookup
cargo bench -- functionalResults written to target/criterion/ as interactive HTML reports.
§🔒 Safety
All Rust code outside the napi-rs FFI layer uses #![forbid(unsafe_code)].
§🔗 See Also
Modules§
- frozen_
map - FrozenMap: State-of-the-art immutable key-value store
- node
nodeandstd - Node.js Bindings
- python
pythonandstd - Python Bindings