[PYTHON] 딕셔너리 성능을 결정짓는 2가지 핵심 : Hash Table 구현 방식과 Python 3.7 이후 순서 보장 원리 해결

Hash Table

 

파이썬 개발자라면 가장 빈번하게 사용하는 자료구조 중 하나가 바로 딕셔너리(Dictionary)입니다. 하지만 단순히 key-value 쌍을 저장하는 도구로만 알고 있다면, 대규모 데이터 처리나 고성능 애플리케이션 개발 시 예상치 못한 병목 현상에 직면할 수 있습니다. 본 글에서는 파이썬 딕셔너리의 근간이 되는 해시 테이블(Hash Table)의 내부 동작 방식과, 파이썬 3.7 버전부터 공식적으로 도입된 데이터 순서 보장(Insertion Order)의 기술적 배경을 심도 있게 분석합니다.

---

1. 파이썬 해시 테이블의 구조와 충돌 해결 방법

파이썬의 딕셔너리는 해시 테이블을 기반으로 구현되어 있어 데이터 탐색, 삽입, 삭제에 대해 평균적으로 $O(1)$의 시간 복잡도를 보장합니다. 이는 내부적으로 해시 함수(Hash Function)를 통해 키를 특정 인덱스로 변환하기 때문입니다.

해시 충돌(Hash Collision)과 Open Addressing

서로 다른 두 개의 키가 동일한 해시 값을 생성할 때 이를 '충돌'이라고 합니다. 파이썬은 이를 해결하기 위해 Open Addressing(개방 주소법) 방식을 채택합니다. 충돌이 발생하면 비어 있는 다른 버킷(Bucket)을 찾아 순차적으로 탐색(Probing)하는 방식이며, 특히 파이썬은 단순 선형 탐색이 아닌 특정 수식을 이용한 Quadratic Probing 변형 모델을 사용하여 클러스터링 현상을 방지합니다.

---

2. Python 3.6 이전 vs 3.7 이후: 메모리 구조의 혁신적 차이

과거 파이썬의 딕셔너리는 메모리 효율이 낮고 데이터 입력 순서를 유지하지 못했습니다. 하지만 3.6 버전에서 실험적으로 도입되고 3.7에서 표준이 된 새로운 구조는 메모리 사용량을 약 20%~25% 절감하면서 동시에 입력 순서를 보장하게 되었습니다.

구조적 변화 비교

저장 방식	단일 대형 배열에 Hash, Key, Value 모두 저장	Sparse Indices 배열 + Dense Entries 배열 분리
메모리 효율	빈 버킷(Dummy) 공간이 많아 낭비 심함	실제 데이터만 밀집 저장하여 효율 극대화
순서 보장	해시 값 순서대로 저장되어 순서 무작위	입력 순서(Insertion Order) 완벽 보장
인덱싱	Hash Table 직접 참조	Indices 배열을 거쳐 Entries 배열 참조

---

3. 순서 보장의 원리: Compact Dictionary

새로운 방식의 핵심은 Indices 배열과 Entries 배열의 분리입니다. 기존에는 커다란 테이블 중간중간에 데이터가 띄엄띄엄 들어있었다면, 현재는 다음과 같은 메커니즘을 따릅니다.

1. Entries 배열: 데이터가 들어오는 순서대로 [hash, key, value]를 차곡차곡 쌓습니다. 이 배열은 빈틈이 없으므로 인덱스 자체가 순서를 의미합니다.
2. Indices 배열: 해시 값을 인덱스로 사용하는 작은 정수 배열입니다. 이 배열에는 실제 데이터가 위치한 Entries 배열의 인덱스 번호가 저장됩니다.

이 구조 덕분에 for key in dict:와 같은 순회 시 Entries 배열을 앞에서부터 읽기만 하면 자연스럽게 입력한 순서대로 출력이 가능해진 것입니다.

---

4. Sample Example: 내부 동작 시뮬레이션

실제 코드를 통해 딕셔너리가 어떻게 데이터를 처리하고 순서를 유지하는지 확인해보겠습니다.

# Python 3.7+ 환경에서의 순서 보장 예시
inventory = {}
inventory['apple'] = 1500
inventory['banana'] = 2000
inventory['cherry'] = 3000

# 1. 입력 순서대로 출력됨을 확인
print("--- Dictionary Items ---")
for fruit, price in inventory.items():
    print(f"{fruit}: {price}")

# 2. 내부 indices와 entries의 개념적 시각화
# Indices: [None, 0, None, 2, 1, None, ...] (해시 값에 따른 위치)
# Entries: 
# 0: [hash_apple, 'apple', 1500]
# 1: [hash_banana, 'banana', 2000]
# 2: [hash_cherry, 'cherry', 3000]

---

5. 개발자가 반드시 알아야 할 주의사항과 성능 해결 방법

순서 보장이 된다고 해서 collections.OrderedDict가 완전히 무의미해진 것은 아닙니다. 일반 딕셔너리는 순서 기반의 비교(Equality check)에서 순서를 무시하지만, OrderedDict는 순서까지 같아야 동일한 객체로 취급합니다. 또한, 빈번한 삭제 연산이 일어날 경우 Entries 배열에 '구멍'이 생길 수 있으며, 파이썬은 특정 임계치에 도달하면 테이블을 재구성(Re-sizing)하여 성능 저하를 방지합니다.

최적화 팁 3가지

• 키의 개수를 미리 알고 있다면 대량 데이터 삽입 전 딕셔너리 크기를 고려하십시오.
• 불변(Immutable) 객체를 키로 사용하여 해시 계산 비용을 최소화하십시오.
• 순서 자체가 중요한 알고리즘(예: LRU 캐시)에서는 여전히 OrderedDict의 특수 메서드(move_to_end 등)가 유용할 수 있습니다.

---

6. 결론

파이썬 3.7 이후의 딕셔너리는 더 이상 단순한 해시 맵이 아닙니다. 인덱스와 엔트리를 분리한 Compact Hash Table 구조를 통해 메모리 효율성과 순서 유지라는 두 마리 토끼를 모두 잡았습니다. 이러한 내부 메커니즘을 이해하는 것은 고성능 파이썬 코드를 작성하는 전문가로 거듭나는 필수 단계입니다.

---

출처 및 참고 문헌

• Python Software Foundation: "What's New In Python 3.7" (Official Documentation)
• Raymond Hettinger: "Modern Python Dictionaries A confluence of a dozen great ideas" (PyCon Presentation)
• CPython Source Code: Objects/dictobject.c
• PEP 468 – Preserving the order of **kwargs in a function