해시 테이블 — 해싱의 작동 원리와 충돌 해결

해시 테이블은 각 키를 해싱해서 배열의 인덱스로 바꾸는 방식으로 키-값 쌍을 저장합니다. 그래서 저장된 모든 항목을 하나씩 순서대로 확인하지 않고도, 올바른 위치에 가까운 곳으로 바로 이동할 수 있습니다.

이 때문에 해시 테이블은 평균적으로 조회, 삽입, 삭제가 $O(1)$에 가까운 경우가 많습니다. 다만 조건이 중요합니다. 해시 함수가 키를 꽤 고르게 퍼뜨려야 하고, 테이블에는 충돌을 처리하는 규칙도 필요합니다.

해시 테이블이 하는 일

해시 테이블은 "name" -> "Ada" 또는 42 -> "blue" 같은 키-값 쌍을 저장합니다. 핵심 구성 요소는 두 가지입니다:

• 슬롯 또는 버킷으로 이루어진 배열
• 각 키를 그 슬롯 중 하나에 대응시키는 해시 함수

배열에 $m$개의 슬롯이 있다면, 해시 함수는 $0$부터 $m-1$까지의 인덱스를 만든다고 생각할 수 있습니다.

작은 정수 예시에서는 규칙이 다음과 같을 수 있습니다.

$$h(k) = k \bmod 8$$

그러면 키 $10$은 $10 \bmod 8 = 2$이므로 슬롯 $2$로 갑니다.

실제 해시 함수는 특히 문자열이나 더 큰 데이터셋을 다룰 때 훨씬 더 신중하게 설계됩니다. 하지만 핵심 아이디어는 같습니다. 인덱스를 빠르게 계산한 뒤, 그 위치에 저장된 항목을 확인하는 것입니다.

해시 충돌을 피할 수 없는 이유

충돌은 서로 다른 두 키가 같은 슬롯에 매핑될 때 발생합니다.

이것은 정상입니다. 보통 테이블의 슬롯 수는 가능한 전체 키의 수보다 훨씬 적기 때문입니다. 다음과 같이

$$h(k) = k \bmod 8$$

정의하면 키 $10$, $18$, $26$은 모두 슬롯 $2$에 매핑됩니다. 즉, 함수가 정의대로 정확히 작동하더라도 테이블은 여전히 해결해야 할 충돌을 만나게 됩니다.

따라서 해시 테이블은 모든 키에 대해 고유한 슬롯을 보장하지 않습니다. 대신 충돌이 잘 처리된다는 조건 아래에서, 탐색 범위를 빠르게 좁히는 방법을 제공합니다.

예제로 보기: 하나의 테이블, 하나의 충돌

어떤 테이블에 슬롯이 $8$개 있고 다음을 사용한다고 합시다.

$$h(k) = k \bmod 8$$

키 $10$, $18$, $7$을 삽입해 봅시다.

먼저 $10$은 $10 \bmod 8 = 2$이므로 슬롯 $2$로 갑니다.

다음으로 $18$도 해시 결과가 슬롯 $2$이므로 충돌이 발생합니다.

그다음 $7$은 슬롯 $7$로 가므로, 이 삽입에서는 충돌이 일어나지 않습니다.

중요한 패턴은 항상 같습니다:

1. 키를 해싱한다.
2. 제안된 슬롯으로 이동한다.
3. 그 자리에 이미 다른 키가 있으면 충돌 처리 규칙을 적용한다.

이 패턴이 분명해지면, 두 가지 대표적인 충돌 처리 전략도 이해하기 쉬워집니다.

체이닝 vs 개방 주소법

체이닝은 각 슬롯에 버킷을 둔다

체이닝에서는 각 슬롯이 하나의 항목만 저장하는 것이 아니라, 작은 항목 모음을 저장합니다.

만약 $10$과 $18$이 모두 슬롯 $2$로 해시된다면, 버킷 $2$에는 다음과 같이 저장될 수 있습니다.

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

키 $18$을 찾으려면, 테이블은 버킷 $2$로 이동한 뒤 그 버킷 안의 항목들만 비교하면 됩니다.

체이닝은 개념적으로 단순하고, 삭제도 보통 개방 주소법보다 쉽습니다. 대신 버킷이 길어지면 연산 속도가 느려진다는 단점이 있습니다.

개방 주소법은 배열 내부에서 해결한다

개방 주소법에서는 배열의 각 슬롯이 최대 하나의 항목만 가집니다. 원래 가야 할 슬롯이 차 있으면, 테이블은 정해진 규칙에 따라 다른 슬롯들을 조사합니다.

대표적인 규칙 중 하나는 선형 조사법입니다. 슬롯 $2$가 이미 차 있으면 $3$, 그다음 $4$, 그다음 $5$를 시도하고, 필요하면 끝에서 다시 처음으로 돌아갑니다.

이 방식은 별도의 버킷 목록이 필요 없다는 장점이 있습니다. 하지만 가까운 슬롯들이 연달아 차면서 클러스터가 생길 수 있습니다. 또 조회와 삭제도 삽입 때 사용한 것과 같은 조사 규칙을 따라야 합니다.

언제 $O(1)$이라고 말할 수 있을까

해시 테이블은 평균적으로 조회, 삽입, 삭제가 $O(1)$이라고 자주 설명됩니다. 하지만 이 평균 시간 복잡도는 몇 가지 조건에 달려 있습니다:

• 해시 함수가 키를 꽤 고르게 퍼뜨려야 한다
• 적재율이 적절하게 유지되어야 한다
• 충돌 처리 전략이 올바르게 구현되어야 한다

적재율은 다음 비율입니다.

$$\text{load factor} = \frac{\text{number of stored entries}}{\text{number of slots}}$$

테이블이 너무 가득 차면 충돌이 더 자주 발생하고, 성능도 나빠집니다. 그래서 많은 구현에서는 배열이 차오르면 크기를 늘립니다.

최악의 경우에는 너무 많은 키가 같은 영역에 몰리면서 성능이 $O(n)$에 가까워질 수도 있습니다.

해시 테이블에서 흔한 실수

충돌이 생기면 해시 함수가 실패했다고 생각하는 것

그렇지 않습니다. 충돌은 예상되는 현상입니다. 진짜 중요한 질문은 테이블이 그것을 효율적으로 처리하느냐입니다.

$O(1)$을 무조건적인 성질로 받아들이는 것

$O(1)$은 보통 평균적인 경우에 대한 설명이지, 모든 입력과 모든 순간에 대한 보장은 아닙니다.

여기서의 해싱을 암호화와 혼동하는 것

기본적인 자료구조 맥락에서 해시 함수의 목적은 주로 빠른 인덱싱이지, 비밀 유지가 아닙니다. 이 둘은 목표가 다릅니다.

실제 키 비교를 잊는 것

서로 다른 두 키가 같은 해시 결과를 가질 수 있습니다. 따라서 올바른 버킷이나 조사 위치에 도착한 뒤에도, 테이블은 키가 실제로 일치하는지 확인해야 합니다.

해시 테이블은 언제 쓰일까

해시 테이블은 키를 기준으로 빠르게 조회하는 일이 중요할 때 사용됩니다. 대표적인 예로는 사전, 심볼 테이블, 캐시, 인덱싱, 데이터에서의 빈도수 계산이 있습니다.

항목을 정렬된 순서로 유지하는 것보다 키로 정확히 찾는 일이 더 중요할 때 특히 잘 맞습니다. 반대로 정렬된 순회, 범위 질의, 가장 가까운 값 찾기가 필요하다면 다른 자료구조가 더 적합할 수 있습니다.

비슷한 충돌 예제를 직접 해보기

슬롯이 $8$개인 작은 배열을 만들고 $h(k)=k \bmod 8$을 사용해 보세요. 그런 다음 $3$, $11$, $19$, $27$ 같은 몇 개의 키를 삽입해 보고, 한 번은 체이닝으로, 또 한 번은 선형 조사법으로 충돌을 해결해 보세요.

이 한 가지 연습만으로도 핵심 아이디어가 아주 빠르게 분명해집니다. 충돌은 피할 수 없고, 어떤 충돌 처리 규칙을 쓰느냐에 따라 테이블의 동작이 달라집니다. 다음 단계로는 테이블 크기를 바꿔서 직접 실험해 보고, 충돌 양상이 어떻게 달라지는지 확인해 보세요.