해시 테이블 충돌 체이닝, 버킷에 연결 리스트를 다는 방식
해시 충돌은 서로 다른 키가 같은 버킷으로 몰리는 현상이고, 체이닝은 버킷마다 연결 리스트를 매달아 그 원소들을 이어 붙인다. 동작 원리와 개방 주소법과의 차이, 로드 팩터가 성능을 좌우하는 방식을 개발자 눈높이로 정리했다.
해시 테이블에서 충돌(collision)은 서로 다른 키가 해시 함수를 거쳐 같은 버킷 번호로 매핑되는 현상이다. 체이닝(chaining), 정식 명칭으로는 분리 연쇄법인 이 방식은 그런 충돌을 버킷마다 연결 리스트를 매달아 해결한다. 같은 자리로 온 원소들을 그 리스트에 차례로 이어 붙이고, 조회할 때는 해당 버킷의 리스트만 훑는다. 자바의 HashMap과 C++의 unordered_map이 대표적으로 이 방식을 쓴다.
이 글은 자료구조 관점에서 체이닝의 동작 원리, 개방 주소법과의 차이, 그리고 로드 팩터가 성능을 어떻게 좌우하는지를 개발자 눈높이로 정리한다. 자바 8 이후의 HashMap과 C++ 표준 라이브러리를 기준으로 설명하며, 암호학적 해시 함수의 안전성이나 분산 해시 테이블(DHT) 같은 네트워크 주제는 다루지 않는다.
해시 충돌은 왜 반드시 생기나
버킷의 개수가 유한하기 때문이다. 해시 함수는 사실상 무한한 키 공간을 정해진 크기의 배열 인덱스로 압축한다. 키가 버킷 수보다 많아지는 순간, 서로 다른 키 두 개가 같은 인덱스로 떨어지는 일은 피할 수 없다. 비둘기 열 마리를 둥지 아홉 개에 넣으면 한 둥지에는 두 마리가 들어가는 비둘기집 원리 그대로다.
해시 테이블이 평균 O(1)에 값을 찾는 것은 배열이 인덱스로 즉시 주소를 계산하는 성질 위에 서 있다. 키를 정수 해시값으로 바꾸고 그 값을 버킷 수로 나눈 나머지를 인덱스로 쓰면 원하는 자리로 한 번에 점프한다. 문제는 이 나머지 연산이 서로 다른 키를 같은 자리로 보낼 수밖에 없다는 점이고, 그래서 충돌 처리는 선택이 아니라 필수다.
체이닝은 충돌을 어떻게 처리하나
버킷을 값 자체가 아니라 연결 리스트의 머리로 취급한다. 각 버킷은 원소를 직접 담는 대신 그 자리로 온 원소들의 리스트를 가리킨다. 삽입은 키의 버킷을 찾아 같은 키가 이미 있는지 확인한 뒤 노드를 잇고, 조회는 버킷 리스트를 순회하며 키를 비교한다. 삭제도 리스트에서 노드 하나를 떼면 끝이라 별도 표식을 남길 필요가 없다.
여기서 노드와 포인터로 원소를 잇는 연결 리스트가 그대로 쓰인다. 파이썬으로 최소한의 체이닝 테이블을 짜 보면 구조가 한눈에 들어온다.
class HashTable:
def __init__(self, size=16):
self.buckets = [[] for _ in range(size)]
def put(self, key, value):
bucket = self.buckets[hash(key) % len(self.buckets)]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value) # 기존 키 갱신
return
bucket.append((key, value)) # 새 키 추가
def get(self, key):
bucket = self.buckets[hash(key) % len(self.buckets)]
for k, v in bucket:
if k == key:
return v
return None
버킷 하나에 원소가 여러 개 몰려도 리스트가 길어질 뿐 테이블 전체 구조는 그대로 유지된다. 이 단순함이 체이닝의 가장 큰 강점이고, 삭제가 잦거나 로드 팩터를 1 이상으로 밀어붙여야 하는 상황에서 특히 편하다.
체이닝과 개방 주소법은 무엇이 다른가
충돌한 원소를 어디에 두느냐가 갈린다. 체이닝은 버킷 밖 리스트에 매달고, 개방 주소법(open addressing)은 테이블 안의 다른 빈 슬롯을 찾아 넣는다. CPython의 dict가 개방 주소법 쪽이다. CPython은 충돌이 나면 연결 노드를 만드는 대신 정해진 규칙으로 다음 슬롯을 탐사(probing)해 빈 자리에 값을 넣는다.
| 구분 | 분리 체이닝 | 개방 주소법 |
|---|---|---|
| 충돌 저장 위치 | 버킷 밖 연결 리스트 | 테이블 안 다른 빈 슬롯 |
| 로드 팩터 | 1 초과 가능 | 1 이하로 제한 |
| 삭제 처리 | 노드 제거로 단순 | 삭제 표식 필요 |
| 캐시 효율 | 노드가 흩어져 낮음 | 연속 배열이라 높음 |
| 대표 구현 | 자바 HashMap | 파이썬 dict |
개방 주소법은 모든 데이터가 배열 안에 연속으로 놓여 CPU 캐시에 유리하지만, 지운 자리에 삭제 표식(tombstone)을 남겨야 하고 로드 팩터가 1을 넘을 수 없다. 체이닝은 정반대다. 리스트 노드가 메모리 여기저기 흩어져 캐시 효율은 떨어지지만, 로드 팩터 제한이 없고 삭제가 깔끔하다. 어느 쪽이 낫다기보다 저장 특성이 다른 두 전략으로 보는 편이 맞다.
로드 팩터가 성능을 어떻게 좌우하나
로드 팩터(load factor)는 저장된 원소 수를 버킷 수로 나눈 값으로, 체이닝에서는 버킷 하나에 걸린 평균 체인 길이와 같다. 이 값이 커질수록 리스트 순회가 길어져 조회가 느려진다. 그래서 실무 구현은 로드 팩터가 일정 선을 넘으면 버킷 수를 늘리고 전체를 재배치(rehash)한다.
오라클의 자바 SE 21 공식 문서는 HashMap의 기본 로드 팩터 0.75가 시간과 공간 비용 사이의 좋은 절충이며, 값을 키우면 공간은 줄지만 조회 비용이 오른다고 설명한다. 기본 초기 용량은 16이고, 저장된 항목 수가 용량과 로드 팩터의 곱인 12를 넘으면 버킷 수를 약 두 배로 늘린다. 로드 팩터를 이 선에서 유지하면 체이닝의 평균 조회는 O(1)에 가깝고, 특정 버킷에 원소가 몰린 최악의 경우에만 O(n)으로 나빠진다.
실무에서 체이닝을 쓸 때 주의할 점
가장 큰 위험은 해시 함수가 값을 골고루 흩뿌리지 못할 때다. 여러 키가 한 버킷에 몰리면 그 버킷 리스트가 길어지고 조회가 O(n)까지 떨어진다. 악의적인 입력으로 일부러 충돌을 유발해 서버를 느리게 만드는 해시 충돌 공격(HashDoS)도 바로 이 약점을 노린다.
자바는 이 최악 상황을 완화하는 장치를 넣었다. 자바 8의 HashMap 구현은 한 버킷의 항목이 8개를 넘고 전체 용량이 64 이상일 때 그 버킷의 연결 리스트를 레드-블랙 트리로 바꿔, 긴 버킷의 조회를 O(n)에서 O(log n)으로 끌어올린다. 항목이 다시 6개 아래로 줄면 리스트로 되돌린다. C++ 표준 라이브러리의 unordered_map은 버킷 API를 표준으로 제공하며 사실상 분리 체이닝으로 구현되는데, cppreference 문서 기준 GCC와 Clang은 단일 연결 리스트를 쓴다. 언어가 무엇이든 좋은 해시 함수와 적절한 로드 팩터가 체이닝 성능의 대부분을 결정한다.
