Frozendict 🧊: Python·Node.js를 위한 최신 불변 해시맵

AI 요약

frozndict는 Python의 일반 dict를 생성 시점에 고정해 변경할 수 없도록 만들고, 딕셔너리 자체를 해시 가능한 값으로 사용할 수 있게 하는 자료구조입니다. 글에서는 이를 100% safe Rust로 구현하고 Python과 Node.js용 네이티브 바인딩을 제공한다고 설명합니다. Python의 dict는 순서가 보장되고 빠르지만 mutable하기 때문에 cache key, functools.lru_cache 인자, set 원소처럼 hashability가 필요한 위치에는 직접 사용할 수 없습니다. 예를 들어 key = {"x": 1}을 다른 딕셔너리의 키로 사용하면 TypeError: unhashable type: 'dict'가 발생합니다.

■ Rust 기반 내부 구조와 복잡도

FrozenDict 객체는 Arc<FrozenDictInner>를 공유합니다. 내부에는 삽입 순서대로 저장되는 entries 배열, 키 해시를 기준으로 정렬된 lookup 배열, 생성 시 계산하는 hash 값, 그리고 keys·values·items를 위한 지연 초기화 캐시가 들어갑니다. entries에는 key_hash와 key, value가 함께 저장되며 lookup은 해시와 entries의 위치를 연결합니다. 이처럼 순서 보존용 저장소와 검색용 인덱스를 분리해, 순회에서는 entries를 그대로 읽고 검색에서는 lookup을 이진 탐색하도록 설계합니다.

글이 제시하는 복잡도는 삽입 순서 순회가 O(n), 조회가 해시 충돌 항목 수를 k라고 할 때 O(log n + k), 생성이 lookup 테이블 정렬을 포함해 O(n log n), copy()와 clone()이 Arc 포인터 복사만 수행하는 O(1)입니다. hash는 생성 시 한 번 계산하고 이후 캐시된 값을 반환하므로 반복 호출은 O(1)입니다. 두 FrozenDict의 해시는 삽입 순서에 영향을 받지 않도록 각 키 해시와 값 해시를 XOR 방식으로 섞어 계산합니다.

■ 불변성, 동등성, 복제

__setitem__, __delitem__, update, clear, pop, popitem, setdefault 같은 변경 메서드는 객체에 존재하지만 호출하면 TypeError를 발생시킵니다. 글에서는 메서드가 아예 없어 AttributeError가 발생하는 방식보다, Mapping 또는 MutableMapping 인터페이스가 기대하는 메서드를 제공한 뒤 변경을 명시적으로 거부하는 방식이 Python의 타입 검사와 duck typing에 더 적합하다고 설명합니다. del fd.x 같은 속성 변경도 TypeError로 차단합니다.

삽입 순서를 보존하더라도 동등성은 순서에 의존하지 않습니다. FrozenDict({"x": 1, "y": 2})와 FrozenDict({"y": 2, "x": 1})은 같은 키-값 쌍을 가지므로 True로 비교되며, hash 값도 같습니다. 초기 구현에서는 entries를 위치별로 비교해 순서가 다르면 False가 되는 문제가 있었지만, 현재 구현은 다른 객체의 각 항목을 정렬된 lookup 테이블로 키 검색한 뒤 값을 비교합니다. 따라서 두 객체를 set에 넣어도 같은 원소 하나로 합쳐집니다.

copy()는 1,000개 항목을 가진 객체에서도 entries나 lookup 테이블을 복사하지 않고 Arc의 참조 횟수만 증가시킵니다. 글의 예제에서는 frozndict.copy()가 약 63ns, 같은 크기의 Python dict에 copy.copy()를 적용한 경우가 약 6.5µs, C 확장 frozendict의 copy()가 약 324ns라고 제시합니다. 이 수치는 글 작성자가 Python 3.12.3, x86-64 Linux에서 timeit으로 측정한 결과이며, 7회 실행과 2,000회 반복의 최솟값을 사용하고 N=1000으로 설정했습니다.

■ 뷰 API와 Python 호환성

keys(), values(), items()는 dict의 뷰와 유사한 객체를 반환하며, keys 뷰와 items 뷰에는 집합 연산을 제공합니다. 예를 들어 keys()끼리 &, |, -, ^를 사용할 수 있고 isdisjoint도 지원합니다. items()의 연산은 키뿐 아니라 값까지 포함한 튜플을 기준으로 하므로, 한 딕셔너리에 ("c", 3)이 있고 다른 딕셔너리에 ("c", 99)가 있으면 두 items 뷰의 교집합에는 포함되지 않습니다. 뷰는 같은 Arc<FrozenDictInner>를 참조하고 연산 시점에 처리되므로 별도의 대규모 복사 없이 동작한다고 설명합니다.

fromkeys도 지원하며, FrozenDict.fromkeys(["a", "b"], 0)은 예상한 값의 FrozenDict를 만듭니다. 예제에서는 subclass에서 호출할 경우 결과도 해당 subclass의 인스턴스가 된다고 설명합니다. 제네릭 별칭인 FrozenDict[str, int], 역순 삽입 순회를 위한 __reversed__, pickle과 copy, | 병합 연산 등 Python dict 프로토콜과 관련된 기능도 제공 대상으로 제시합니다.

■ 벤치마크와 사용 예

작성자가 제시한 N=1000 벤치마크에서 생성 시간은 Python dict 6.45µs, C frozendict 7.70µs, immutables.Map 241.67µs, frozndict 90.70µs입니다. clone O(1)은 각각 6.45µs, 70.48ns, 404.62ns, 138.68ns이며, iteration은 7.39µs, 7.42µs, 14.97µs, 4.14µs입니다. copy()는 6.53µs, 323.83ns, 317.07µs, 63.29ns이고, hash()는 C frozendict 168.19ns, immutables.Map 45.07ns, frozndict 45.52ns입니다. 반면 lookup은 Python dict 32.52ns, C frozendict 48.31ns, immutables.Map 48.11ns, frozndict 82.62ns로 제시됩니다. 별도 측정에서는 n=1000 생성 약 35µs, 조회 적중 약 41ns, 조회 실패 약 39ns, 순회 약 3.1µs, hash() 약 4.8µs, with() 기반 함수형 갱신 약 31µs, merge() 약 35µs라고 설명합니다.

Python에서는 pip install frozndict 후 FrozenDict를 가져와 hash(fd)를 호출하거나, fd를 다른 딕셔너리의 키와 set의 원소로 사용할 수 있습니다. Rust에서는 cargo add frozendict로 추가하고 FrozenMap<&str, i32>를 생성한 뒤 get과 with를 사용할 수 있습니다. Node.js에서는 npm i frozendict로 설치하며 napi-rs 기반의 FrozenDict 클래스와 TypeScript 선언을 제공한다고 안내합니다. Debian/Ubuntu용 .deb와 RHEL/Fedora용 .rpm도 GitHub Releases에서 제공한다고 적혀 있습니다.

현재 버전은 frozndict 2.1.1이며, 로드맵에는 wasm32-unknown-unknown을 대상으로 한 WASM 빌드와 HashMap처럼 FrozenMap을 직렬화·역직렬화하기 위한 serde 지원이 포함되어 있습니다. 따라서 이 글의 핵심은 mutable dict를 단순히 감싼 객체가 아니라, Rust의 공유 소유권과 별도 검색 테이블을 사용해 불변성, 해시 가능성, 삽입 순서, O(1) 복제를 함께 제공하려는 구현을 소개하는 데 있습니다.

원문: dev.to / 번역·요약: Trawling