Module python 

Available on crate feature python only.

Python Bindings

Exposes the frozndict library to Python via pyo3.

Storage Layout (FrozenDictInner)

entries: Box<[(hash, key, value)]>    ← insertion-ordered
lookup:  Box<[(hash, u32)]>           ← hash-sorted for O(log n) lookup
hash:    isize                         ← O(1) pre-computed aggregate
cached_keys/values/items: OnceLock    ← built lazily on first access

O(1) FrozenDict→FrozenDict clone: frozendict(fd) with no kwargs short-circuits to Arc::clone(&fd.inner) - no rehashing or allocation.

O(n log n) deduplication: pairs are sorted by hash, then a linear scan resolves duplicates within same-hash runs. For the common case (dict/int/str keys with distinct hashes) the inner equality loop never runs, reducing the cost from O(n²) equality checks to zero.

No eager list construction: cached_keys, cached_values, and cached_items are built lazily via [OnceLock] on first call to keys(), values(), or items(). Construction no longer allocates three PyList objects and N PyTuple objects.

Inline hash mixing: hash((k, v)) tuple allocation is replaced with k_hash * M1 ^ v_hash * M2 using two multiplicative constants, eliminating N temporary Python tuple objects per construction.

O(1) self-equality: __eq__ checks Arc::ptr_eq first; o == o returns true in a single pointer comparison.

Complexity Summary

Operation	Time	Notes
frozendict(fd) (FrozenDict src)	O(1)	Arc clone
frozendict(dict) (n entries)	O(n log n)	Sort + O(n) dedup scan
frozendict(**kwargs)	O(n log n)
__getitem__ / get	O(log n)	Binary search via lookup
__contains__	O(log n)
__hash__	O(1)	Pre-computed
__eq__ (same object)	O(1)	Arc pointer equality
__eq__ (hash mismatch)	O(1)	Cached hash short-circuit
__eq__ (full compare)	O(n)
keys() / values() / items()	O(1)	View wrapping Arc
First iteration (lazy init)	O(n)	Builds PyList once
Subsequent iterations	O(n)	Traverse pre-built PyList
copy()	O(1)	Arc clone

Structs

FrozenDict

A fully immutable, hashable Python dictionary with insertion-order semantics.

FrozenItemsView

Set-like view over the (key, value) items of a :class:FrozenDict.

FrozenKeysView

Set-like view over the keys of a :class:FrozenDict (insertion order).

FrozenValuesView

Sequence-like view over the values of a :class:FrozenDict (insertion order).

Functions

register_python_module

Register all Python-exposed types into the _frozndict extension module.