11장. 해시 테이블 (2) - 충돌 처리 방식 (개별 체이닝, 오픈 어드레싱)
파이썬 딕셔너리는 해시 테이블을 기반으로 한 자료형으로, 충돌 해결을 위해 오픈 어드레싱 방식을 사용합니다. 이를 통해 메모리 할당 오버헤드를 줄이고, 성능 저하를 막기 위해 로드 팩터를 낮게 설정하여 최적화를 이루고 있습니다.
충돌 (Collision)
해시 함수가 아무리 좋아도 충돌(Collision)은 피할 수 없습니다.
예를 들어, 그림 1에서 윤아와 서현의 해시 값이 모두 2로 같아 충돌이 발생했습니다.
이렇게 충돌이 발생했을 때는 어떤 방법으로 이를 처리할 수 있을까요?
우선 개별 체이닝(Separate Chaining) 방식을 살펴보겠습니다.
1. 개별 체이닝 (Separate Chaining)
우선, 입력 데이터는 아래의 표와 같이 구성되었습니다.
해시는 키를 해싱한 결과 값이며, 윤아와 서현의 경우 해시 값이 동일해 충돌이 발생한다고 가정했습니다.
| 키 | 값 | 해시 | 충돌 여부 |
| 윤아 | 15 | 2 | 충돌 |
| 유리 | 47 | 1 | |
| 서현 | 17 | 2 | 충돌 |
| 수영 | 7 | 4 |
위 데이터를 개별 체이닝 방식으로 구현하면 그림 1과 같은 형태가 됩니다.
개별 체이닝은 해시 테이블에서 가장 널리 사용되는 충돌 해결 방법으로, 그림 1처럼 충돌이 발생한 경우 연결 리스트로 해당 키들을 연결하는 방식입니다. 예를 들어, 윤아와 서현의 해시 값이 동일할 때, 윤아 다음에 서현이 연결 리스트 형태로 이어지게 됩니다.
개별 체이닝은 구현이 간단하고, 기본적인 자료구조와 간단한 알고리즘만 있으면 가능하여, 전통적인 해시 테이블에서 주로 사용됩니다.
이를 요약하면 다음과 같습니다.
- 키의 해시 값을 계산합니다.
- 해시 값을 배열의 인덱스로 변환하여 데이터를 저장할 위치를 결정합니다.
- 충돌이 발생하면 해당 인덱스의 연결 리스트에 키-값을 추가합니다.
개별 체이닝 방식을 잘 구현하면 대부분의 탐색이 상수 시간(O(1))에 완료됩니다.
다만, 모든 키가 같은 해시 값으로 충돌한다면 최악의 경우 시간 복잡도가 O(n)까지 증가할 수 있습니다.
2. 오픈 어드레싱 (Open Addressing)
오픈 어드레싱 방식은 해시 충돌이 발생했을 때, 탐사를 통해 빈 공간을 찾아 해결하는 방식입니다.
체이닝 방식과는 달리, 오픈 어드레싱은 해시 테이블의 전체 슬롯 수보다 더 많은 데이터를 저장할 수 없습니다.
충돌이 발생하면 테이블 내부에서 빈 공간을 찾기 위해 탐사(프로빙, Probing)를 수행하여 데이터를 삽입합니다.
다만, 개별 체이닝과는 달리 모든 데이터가 자신의 해시 값에 해당하는 위치에 저장된다는 보장은 없습니다.
선형 탐사 (Linear Probing)
오픈 어드레싱 방식 중 가장 단순한 방식으로, 충돌이 발생하면 해당 위치에서부터 순차적으로 한 칸씩 이동하여 빈 공간을 찾습니다.
특정 위치에 데이터가 이미 있다면, 그 다음 위치를 차례로 확인하는 방식입니다.
비어 있는 공간을 발견하면 데이터를 삽입하며, 이 방법은 구현이 간단하고 성능도 비교적 안정적입니다.
문제점: 클러스터링 (Clustering)
선형 탐사는 데이터들이 테이블에 고르게 분포되지 않고 특정 영역에 집중되는 클러스터링 현상을 초래할 수 있습니다.
이렇게 형성된 클러스터들이 점점 커지면서 다른 인접 클러스터와 합쳐지면, 특정 영역에는 데이터가 몰리고 다른 영역에는 데이터가 거의 없는 불균형이 발생할 수 있습니다. 이는 탐사 시간을 증가시키고, 전체 해시 효율을 저하시키는 원인이 됩니다.
리해싱 (Rehashing)
오픈 어드레싱 방식은 해시 테이블의 버킷(슬롯) 크기를 초과하는 데이터를 저장할 수 없으므로, 일정 수준 이상 테이블이 채워지면 테이블의 크기를 늘리는 리해싱 작업이 필요합니다. 이를 위해 로드 팩터(Load Factor)를 기준으로 공간이 부족해지면, 그로스 팩터(Growth Factor)에 따라 더 큰 버킷을 생성하고 기존 데이터를 새 버킷에 재배치합니다.
파이썬의 해시 테이블 구현 방식
파이썬에서 리스트와 함께 가장 많이 사용되는 자료형인 딕셔너리는 해시 테이블로 구현되어 있습니다.
"파이썬에서 해시 테이블로 구현된 자료형이 무엇인가?"라는 질문에 주저 없이 "딕셔너리"라고 답할 수 있습니다.
그렇다면, 파이썬의 해시 테이블은 충돌이 발생했을 때 어떤 방식을 사용할까요? 답은 "오픈 어드레싱 방식"입니다.
Cpython 구현 선택 이유
파이썬의 Cpython 구현에서는 오픈 어드레싱 방식을 선택한 이유가 다음과 같이 설명되어 있습니다:
- 체이닝 방식을 사용하려면 메모리를 동적으로 할당(malloc)해야 하며, 이로 인해 메모리 오버헤드가 발생합니다.
- 연결 리스트를 생성하는 데 필요한 추가 메모리 할당이 상대적으로 느린 작업이기 때문에 연결 리스트 대신 오픈 어드레싱 방식을 택했습니다.
오픈 어드레싱과 성능 최적화
그림3과 같이 파이썬의 오픈 어드레싱 방식에서 사용되는 선형 탐사 방식은 일반적으로 체이닝 방식에 비해 성능이 더 좋습니다. 하지만 테이블의 슬롯이 80% 이상 차게 되면 급격히 성능이 저하될 수 있으며, 체이닝과 달리 전체 슬롯 개수 이상 데이터를 저장할 수 없습니다. 빈 슬롯을 탐사하는 선형 탐사는 슬롯이 가득 찰수록 탐사에 시간이 더 오래 걸리기 때문입니다.
모던 언어인 파이썬은 이 문제를 해결하기 위해 오픈 어드레싱을 사용하면서도, 로드 팩터를 낮게 설정해 성능을 유지합니다. 파이썬의 로드 팩터는 약 0.66으로, 이는 해시 테이블의 성능 저하를 방지하기 위한 최적화된 값입니다.