체이닝(Chaining)을 활용한 해싱이란?
해싱(Hashing)은 데이터를 빠르게 저장하고 검색하기 위한 대표적인 자료구조 기법입니다. 하지만 서로 다른 키가 동일한 해시 값에 매핑되는 충돌(Collision) 현상은 피할 수 없습니다. 체이닝(Chaining)은 이러한 충돌을 해결하는 대표적인 기법으로, 같은 해시 값에 해당하는 여러 요소를 하나의 연결 리스트(Linked List)로 묶어 저장하는 방식입니다.
충돌 자체를 완전히 제거할 수는 없지만, 체이닝을 활용하면 충돌 발생 가능성을 줄이고, 동일한 해시 값을 가진 여러 요소도 문제없이 저장할 수 있습니다.
체이닝의 동작 원리
해시 함수 h(x)의 출력 범위가 0부터 6까지라고 가정해 보겠습니다. 이 경우 해시 테이블에는 총 7개의 슬롯(slot)만 존재하므로, 요소가 7개를 초과하면 반드시 두 개 이상의 요소가 같은 슬롯에 배치되어 충돌이 발생합니다.
체이닝에서는 각 슬롯에 연결 리스트를 만들어 충돌한 요소들을 함께 저장합니다. 새로운 요소는 항상 리스트의 맨 앞(head)에 추가하므로, 삽입 연산을 O(1) 시간 안에 수행할 수 있다는 큰 장점이 있습니다.
예제
다음 요소들을 해시 테이블에 저장한다고 가정해 보겠습니다.
{15, 47, 23, 34, 85, 97, 65, 89, 70}
사용하는 해시 함수는 다음과 같습니다.
h(x) = x mod 7
각 요소의 해시 값은 아래와 같습니다.
| 요소 | 계산 과정 | 해시 값 |
|---|---|---|
| 15 | 15 mod 7 | 1 |
| 47 | 47 mod 7 | 5 |
| 23 | 23 mod 7 | 2 |
| 34 | 34 mod 7 | 6 |
| 85 | 85 mod 7 | 1 |
| 97 | 97 mod 7 | 6 |
| 65 | 65 mod 7 | 2 |
| 89 | 89 mod 7 | 5 |
| 70 | 70 mod 7 | 0 |
이 요소들을 체이닝 방식으로 해싱하면 다음과 같은 구조가 됩니다.
최종 결과 정리
- 0번 슬롯: 70
- 1번 슬롯: 15 → 85 (충돌 발생)
- 2번 슬롯: 23 → 65 (충돌 발생)
- 3번, 4번 슬롯: 비어 있음
- 5번 슬롯: 47 → 89 (충돌 발생)
- 6번 슬롯: 34 → 97 (충돌 발생)
이처럼 체이닝은 충돌이 발생해도 연결 리스트를 통해 모든 요소를 유연하게 저장할 수 있으며, 검색 시에는 해당 해시 값의 리스트만 순회하면 되므로 효율적인 데이터 관리가 가능합니다.