So there I was, staring at Python's frozenset, feeling that specific special rage that only a data structure enthusiast at 1AM can feel, while dict sat there, utterly mutable, fully hashable, completely disobedient.
Dictionary keys can change. You can pop from it. You can clear it. You can update it mid-computation and break 30 tests simultaneously.
I looked at this situation calmly. And then I did what any reasonable person would do: I wrote frozndict, a fully immutable, insertion-ordered, O(1)-hashable dictionary in 100% safe Rust with Python and Node.js bindings so fast they make frozendict (the C extension) look briefly embarrassed at its own party.
The result? frozndict: the state of the art immutable hashmap. Frozen at construction. Hashable by design. Faster than guilt.
Python's dict is a magnificent beast. It's ordered, fast, flexible. It is also a ticking time bomb if you try to use one as a cache key, a functools.lrucache argument, or anywhere that requires hashability.
The stdlib's frozenset solved this for sets. Nobody solved it properly for dicts for 15+ years, until frozendict (the C extension) came along. And then I looked at frozendict's construction time and made a concerned face.
frozndict solves all of this: Truly immutable: mutation attempts at the Rust level raise TypeError. Not AttributeError. No monkey-patching. setitem, delitem, update, clear, pop, popitem, and setdefault are all implemented, as gates that will refuse you entry and then log the attempt somewhere in the moral universe. O(1) hash: computed once at construction. Subsequent calls return a cached isize. No recomputation. Ever. O(1) copy(): returns the same Arc. One pointer copy. 63 ns. Done. Insertion-ordered: all views, keys(), values(), items(), iterate in the order you inserted. fromkeys support: FrozenDict.fromkeys(["a", "b"], 0) works exactly as you'd expect, including on subclasses. Set algebra on views: fd.keys() & otherkeys, fd.items() - otheritems, ^, |, isdisjoint, all there.
The key insight: entries stay in insertion order. The lookup table is a separate, sorted slice used only for binary search. This gives us: O(n) insertion-ordered iteration (just walk entries) O(log n + k) lookup (binary search to the hash bucket, then linear scan for collision k) O(n log n) construction (one sort of the lookup table, then done) O(1) copy() and clone() (pointer copy of the Arc)
The hash is computed by XOR-mixing each keyhash MIXKEY ^ valuehash MIXVAL. Order-independent. Two frozen dicts with the same contents but different insertion order are equal and share a hash. As nature intended.
These are real numbers. Benchmarked with timeit on Python 3.12.3, x86-64 Linux, min of 7 runs × 2,000 iterations, N=1000 entries.
| Operation | Python dict | frozendict (C) | immutables.Map | frozndict 🧊 | | ------------ | ------------ | -------------- | -------------- | ------------- | | Construction | 6.45 µs | 7.70 µs | 241.67 µs | 90.70 µs | | Clone O(1) | 6.45 µs | 70.48 ns | 404.62 ns | 138.68 ns | | Equality | 19.37 µs | 19.44 µs | 24.39 ns | 32.42 ns | | Iteration | 7.39 µs | 7.42 µs | 14.97 µs | 4.14 µs | | copy() | 6.53 µs | 323.83 ns | 317.07 µs | 63.29 ns | | hash() | N/A | 168.19 ns | 45.07 ns | 45.52 ns | | Lookup | 32.52 ns | 48.31 ns | 48.11 ns | 82.62 ns |
frozndict wins iteration, copy(), equality, clone, and very nearly ties immutables.Map on hash(). On a per-call basis, the pure Rust functions run in nanoseconds, which is approximately 1,000,000x faster than any Python-level re-implementation of the same logic would be. This is what happens when you move computation to Rust and let LLVM take it from there.
| Workload | Time | | ---------------------------- | -------- | | Construction, n=100 | \~2.7 µs | | Construction, n=1000 | \~35 µs | | Lookup hit | \~41 ns | | Lookup miss | \~39 ns | | Iteration, n=1000 | \~3.1 µs | | hash() | \~4.8 µs | | with() (functional update) | \~31 µs | | merge() | \~35 µs |
The lookup path is 40 nanoseconds. For comparison, a Python function call overhead alone is about 60-100 ns. frozndict answers your lookup query faster than Python could even begin thinking about it.
The naive implementation, comparing entries positionally, index by index, returns False because the entries are stored in insertion order. Early frozndict versions had exactly this bug. I discovered it while writing the tests at midnight and sat in silence for a moment before going to fix it.
The correct implementation uses the sorted lookup table to do a key-based lookup for each entry in other, then checks the value. Order-independent. Hash-consistent. Correct.
That last line, being usable in a set, is the whole point. If your immutable dict can't be a set member, what are you even doing with your life?
Every Python object wrapping frozndict shares one Arc. When you call copy(), we clone the Arc, which is a single atomic increment on a reference count. No allocation. No copying of entries. No touching the lookup table.