해시 테이블(Hash Table)은 평균적으로 O(1)에 가까운 매우 빠른 삽입과 검색 속도를 제공하는 데이터 구조다. 그러나 해시 테이블을 실제로 구현할 때 충돌(Collision)이 발생하는 것은 불가피하며, 이를 어떻게 다루느냐에 따라 성능이 크게 좌우된다. 특히 개방 주소법(Open Addressing) 기반 해싱에서는 **클러스터링(Clustering)**이라는 심각한 성능 저하 문제가 발생할 수 있다. 이 글에서는 클러스터링이 무엇인지, 왜 발생하는지, 그리고 이를 어떻게 해결할 수 있는지 구체적으로 설명하고자 한다.
클러스터링이란 무엇인가?
클러스터링은 해시 충돌 처리 과정에서 데이터들이 해시 테이블의 특정 영역에 몰려 뭉치는 현상을 의미한다. 개방 주소법 중 특히 **선형 탐사(Linear Probing)**를 사용할 때 이 문제가 두드러진다. 선형 탐사에서는 충돌이 발생하면 다음 인덱스를 차례로 순회하면서 빈 슬롯을 찾는다. 이 과정이 반복되다 보면 데이터가 한 곳에 집중되는 클러스터가 형성된다.
클러스터가 형성되면 새로운 데이터 삽입 시, 빈 슬롯을 찾기 위해 이 연속된 영역을 모두 지나야 하므로 평균 검색 및 삽입 시간이 O(1)에서 O(n)에 가까워질 수 있다. 결국 해시 테이블의 가장 큰 장점인 빠른 접근 속도가 무력화된다.
클러스터링 문제 예시
해시 테이블의 크기를 10으로 하고, 간단히 key % 10이라는 해시 함수를 사용한다고 가정해 보자. 키 10, 20, 30을 삽입하면 이들은 모두 해시값 0을 가지게 된다. 선형 탐사 방식에서는 충돌이 발생할 경우 다음 슬롯을 순서대로 확인한다. 이에 따라 다음과 같은 상태가 된다.
| Index | 데이터 |
|---|---|
| 0 | 10 |
| 1 | 20 |
| 2 | 30 |
| 3 | |
| 4 | |
| … | … |
여기서 새로운 키 31을 삽입하려 하면, 0번 슬롯 충돌 → 1번 충돌 → 2번 충돌을 지나 3번 슬롯에 삽입된다. 이후 키 32를 삽입하면 또 다시 이 클러스터를 통과해야 한다. 결과적으로 해시 테이블 초반부에 데이터가 몰리면서, 검색이나 삽입 시 걸리는 시간이 점점 늘어나게 된다.
이와 같은 클러스터가 한번 형성되면 새로운 충돌은 클러스터의 가장자리에 추가되므로, 클러스터는 계속해서 성장하게 된다. 이를 Primary Clustering이라고 부른다.
클러스터링이 문제가 되는 이유
- 탐색 시간 증가: 빈 슬롯을 찾기 위해 클러스터 전체를 순회해야 한다.
- 삽입 성능 저하: 삽입 과정에서 클러스터를 우회해야 하므로 시간이 많이 소모된다.
- 테이블 활용 비율 악화: 테이블이 충분히 비어 있어도, 일부 구역에만 몰려서 공간이 비효율적으로 사용된다.
- 삭제 처리 복잡화: 삭제된 슬롯을 특별하게 관리해야 하며, 그렇지 않으면 검색 실패가 조기에 발생할 수 있다.
클러스터링을 해결하는 방법
클러스터링 문제를 완화하기 위해 다양한 충돌 해결 기법이 개발되었다. 대표적인 방법은 다음과 같다.
이차 탐사 (Quadratic Probing)
선형적으로 한 칸씩 이동하는 대신, 이동 거리를 제곱에 비례하게 증가시킨다. 즉, 충돌이 발생할 때마다 1², 2², 3², 4² 만큼 점프하는 식이다.
- 1회 충돌: +1 이동
- 2회 충돌: +4 이동
- 3회 충돌: +9 이동
이 방법은 근접한 슬롯에 데이터가 몰리는 것을 방지해, 클러스터 크기를 줄여준다. 하지만 여전히 Secondary Clustering(해시값이 같은 키들이 같은 탐사 경로를 따르는 문제)이 발생할 수 있다.
이중 해싱 (Double Hashing)
또 다른 독립적인 해시 함수를 추가로 사용해, 충돌 시 이동 거리를 다르게 한다. 예를 들어:
h(k, i) = (h1(k) + i * h2(k)) % TABLE_SIZE
여기서 h1은 기본 해시 함수, h2는 보조 해시 함수다. h2(k)는 항상 0이 아닌 값을 반환해야 한다. 이 방법은 Secondary Clustering 문제까지 효과적으로 해결할 수 있어 개방 주소법에서는 가장 성능이 좋은 방법으로 간주된다.
재해싱 (Rehashing)
테이블이 일정 부하율(load factor, 예: 0.7)을 넘으면, 더 큰 크기의 새 해시 테이블로 모든 데이터를 재삽입하는 방법이다. 이는 테이블 내 빈 공간을 늘려 충돌 가능성을 줄인다. 이 방법은 추가적인 비용이 들지만, 장기적으로 성능을 유지하는 데 도움이 된다.
결론
해시 테이블은 매우 빠른 자료구조지만, 충돌 처리 전략에 따라 실제 성능은 천차만별이다. 특히 개방 주소법과 선형 탐사를 사용할 때 발생하는 클러스터링 문제는 해시 테이블의 속도를 심각하게 저하시킬 수 있다. 이를 방지하려면 이차 탐사나 이중 해싱과 같은 보다 세련된 충돌 해결 방법을 도입하고, 필요 시 재해싱을 통해 테이블의 부하율을 관리해야 한다. 해시 테이블을 제대로 활용하려면 단순한 구현만으로는 부족하며, 충돌과 클러스터링에 대한 깊은 이해가 필수적이다.
답글 남기기