[PYTHON] 딕셔너리 해시 충돌 해결 방법과 3.6 버전 이후 순서 보장의 2가지 핵심 원리

딕셔너리 해시

 

파이썬 개발자라면 가장 빈번하게 사용하는 자료구조 중 하나가 바로 딕셔너리(dict)입니다. 파이썬의 딕셔너리는 단순한 키-값(Key-Value) 쌍의 집합을 넘어, 언어 자체의 네임스페이스를 관리하는 핵심 엔진입니다. 하지만 파이썬 3.6 이전과 이후, 딕셔너리는 메모리 효율성과 데이터 유지 방식에서 혁명적인 변화를 겪었습니다. 오늘날 우리가 당연하게 여기는 '입력 순서 보장'이 어떻게 구현되었는지, 그리고 해시 충돌이라는 고전적인 알고리즘 문제를 파이썬이 어떻게 세련되게 해결했는지 심층적으로 파헤쳐 보겠습니다.

1. 파이썬 딕셔너리의 근간: 해시 테이블과 충돌 해결

딕셔너리는 내부적으로 해시 테이블(Hash Table)을 사용하여 데이터에 접근합니다. 키(Key)를 해시 함수에 통과시켜 얻은 인덱스에 값을 저장함으로써 $O(1)$의 경이로운 탐색 속도를 보장합니다. 그러나 서로 다른 두 키가 동일한 해시 값을 갖게 되는 해시 충돌(Hash Collision)은 피할 수 없는 숙제입니다.

오픈 어드레싱(Open Addressing) 방식

자바의 HashMap이 '체이닝(Chaining)' 방식을 사용하는 것과 달리, 파이썬은 오픈 어드레싱, 그중에서도 선형 탐사(Linear Probing)를 개량한 방식을 사용합니다. 충돌이 발생하면 미리 정해진 이차 함수를 이용해 비어 있는 다음 슬롯을 찾아가는 방식입니다. 이는 데이터들이 메모리상에 연속적으로 배치되게 하여 CPU 캐시 적중률을 높이는 효과를 줍니다.

---

2. 혁신의 시작: 파이썬 3.6+ 딕셔너리의 구조적 차이

파이썬 3.6 이전의 딕셔너리는 해시 테이블 자체가 키, 해시값, 값을 모두 담고 있었습니다. 이로 인해 빈 공간이 많아 메모리 낭비가 심했고, 순서 또한 무작위였습니다. 레이몬드 헤팅거(Raymond Hettinger)가 제안한 새로운 구조는 이를 '인덱스 배열'과 '엔트리 배열'로 분리했습니다.

표: 파이썬 3.6 이전 vs 3.6 이후 딕셔너리 메커니즘 비교

비교 항목	Legacy Dict (3.6 미만)	Modern Dict (3.6 이상)
메모리 구조	Sparse Hash Table (성긴 배열)	Dense Entries + Index Array (밀집 배열)
메모리 효율	낮음 (빈 슬롯도 큰 메모리 차지)	높음 (데이터를 밀집 저장하여 약 25% 절감)
순서 보장 여부	보장되지 않음 (Unordered)	입력 순서 유지 (Ordered)
충돌 해결 전략	Open Addressing (이차 탐사)	Open Addressing + Compact Storage

3. 순서 보장의 원리: 컴팩트 딕셔너리(Compact Dict)

어떻게 순서가 보장될까요? 비결은 데이터를 추가된 순서대로 엔트리 리스트에 쌓는 것에 있습니다. 인덱스 배열은 해시 값을 통해 엔트리 리스트의 '위치'만을 가리킵니다. 사용자가 딕셔너리를 순회할 때 파이썬은 인덱스 배열이 아닌, 데이터가 순차적으로 쌓인 엔트리 배열을 그대로 읽기 때문에 자연스럽게 입력 순서가 유지되는 것입니다.

이 방식은 3.6에서 최적화의 일환으로 도입되었으나, 그 유용성을 인정받아 3.7부터는 언어 사양으로 공식 확정되었습니다.

4. Sample Example: 해시 충돌과 순서 유지 확인

아래 코드를 통해 실제로 딕셔너리가 순서를 어떻게 기억하는지, 그리고 동일한 해시값을 가진 객체가 어떻게 처리되는지 유추해 볼 수 있습니다.

# 1. 입력 순서 보장 확인 (Python 3.7+ 기준)
user_data = {}
user_data['name'] = 'Chaewon'
user_data['job'] = 'Developer'
user_data['location'] = 'Seoul'

print("딕셔너리 순회 결과:")
for key, value in user_data.items():
    print(f"{key}: {value}")
# 입력한 순서(name -> job -> location)대로 출력됩니다.

# 2. 해시 충돌 모사 (동일한 __hash__ 값을 가진 클래스)
class ForceCollision:
    def __init__(self, val):
        self.val = val
    def __hash__(self):
        return 42  # 모든 객체가 동일한 해시값을 가짐
    def __eq__(self, other):
        return self.val == other.val

obj1 = ForceCollision("First")
obj2 = ForceCollision("Second")

collision_dict = {obj1: "Value 1", obj2: "Value 2"}
print(f"\n충돌 발생 시 딕셔너리 크기: {len(collision_dict)}")
# 해시값이 같아도 __eq__가 다르므로 별개의 엔트리로 저장됩니다.

5. 결론: 효율적인 딕셔너리 활용 방법

파이썬의 딕셔너리는 지속적으로 진화하고 있습니다. 대규모 데이터를 처리할 때는 keys()나 values() 뷰 객체를 활용하여 메모리 오버헤드를 줄이고, 순서가 중요한 로직에서는 굳이 collections.OrderedDict를 쓰지 않아도 기본 딕셔너리로 충분하다는 점을 명심하십시오. 파이썬의 내부 메커니즘을 이해하는 것은 더 견고하고 빠른 코드를 작성하는 밑거름이 됩니다.

콘텐츠 출처 및 기술 자료

• Python Enhancement Proposals
• Raymond Hettinger's Talk: "Modern Dictionaries by Great Algorithms" (PyCon)
• CPython Source Code