🔑 해시 테이블(Hash Table) 개념과 충돌 처리 방식 정리

1. 해시 테이블이란? 

해시 테이블은 키(Key)를 해시 함수(Hash Function)에 입력하여 얻은 정수 값을 배열의 인덱스로 사용해 데이터를 저장하고 조회하는 자료구조다.

배열의 인덱스 접근 특성을 활용하기 때문에 평균적으로 탐색, 삽입, 삭제 연산을 O(1) 시간에 수행할 수 있는 것이 특징이다.

[관련 자료구조]

• Map
  키(Key)와 값(Value)의 쌍을 저장하고 관리하는 추상 자료형
• Set
  중복을 허용하지 않으며 특정 값의 존재 여부를 관리하는 추상 자료형

이러한 자료구조는 해시 테이블 기반으로 구현될 경우 평균적으로 탐색, 삽입, 삭제가 O(1)의 시간 복잡도를 가진다.

단 해시 충돌이 많아질 경우 해시 테이블의 최악의 시간 복잡도는 O(n)이 될 수 있으며 이진 탐색 트리 기반으로 구현되는 경우에도 O(log n)이 될 수 있다.

2. 해시 테이블의 주요 구성 요소

- 해시 함수 (Hash Function)

해시 함수는 입력값(Key)을 받아 정수 형태의 해시값(Hash Value)으로 변환하는 함수다.

좋은 해시 함수는 동일한 키에 대해 항상 동일한 해시값을 반환하고 서로 다른 키가 가능한 한 다른 해시값을 가지도록 균등하게 분포하도록 만든다.

하지만 입력 데이터의 범위에 비해 해시값의 공간이 제한적이기 때문에 서로 다른 키가 동일한 해시값을 가지는 경우가 발생할 수 있다.

- 버킷 인덱싱 (Bucket Indexing) 

해시 함수는 키를 정수 형태의 해시값으로 변환할 뿐이다. 따라서 실제 데이터를 저장하기 위해서는 해시값을 배열의 인덱스로 변환하는 과정이 필요하며 이를 버킷 인덱싱이라고 한다.

일반적으로 다음과 같은 방식으로 인덱스를 계산한다.

index = hash(key) % capacity

해시 함수로 얻은 정수값을 배열의 크기(capacity)로 나눈 나머지를 사용하여 인덱스를 결정한다. 나머지 연산을 사용하는 이유는 해시값이 아무리 큰 값이더라도 배열의 인덱스 범위를 벗어나지 않도록 하기 위함이다.

- 충돌 처리 (Collision Handling) 

해시 함수는 많은 키를 제한된 크기의 배열 인덱스 공간에 매핑해야 한다. 이 과정에서 서로 다른 키가 동일한 인덱스를 가리키는 경우가 발생할 수 있으며 이를 충돌(Collision)이라고 한다.

"dog" -> hash = 42 -> index = 42 % 16 = 10
"god" -> hash = 58 -> index = 58 % 16 = 10 (충돌)

위와 같이 서로 다른 키가 동일한 인덱스를 가지게 되면 충돌이 발생한다. 충돌을 적절히 처리하지 않으면 기존 데이터가 덮어써지거나 탐색, 삽입, 삭제 연산이 정상적으로 수행되지 않을 수 있다.

따라서 충돌을 어떻게 처리하느냐가 해시 테이블의 성능을 결정하는 중요한 요소가 된다.

3. 해시 충돌 해결 방법

- 체이닝 (Chaining, 분리 연결법)

같은 인덱스에 매핑된 키들을 연결 리스트(또는 트리) 형태로 저장하는 방식이다. 즉 배열의 각 버킷이 하나의 체인 구조를 가지게 된다.

bucket[10] -> [("dog", var1)] -> [("god", var2)] -> ...

구현이 비교적 단순하며 노드 연결만 변경하면 되기 때문에 삭제 연산이 쉽다는 장점이 있다. 또 *로드 팩터(load factor)가 1을 넘어도 동작이 가능하다.

*로드 팩터(Load Factor)란?
해시 테이블이 얼마나 채워져 있는지를 나타내는 비율
공식) 로드 팩터 α = 저장된 원소 수 / 전체 버킷 수

다만 각 노드가 포인터를 가지기 때문에 추가적인 메모리 오버헤드가 발생하며 데이터가 메모리 상에서 연속적으로 저장되지 않기 때문에 캐시 효율이 낮다는 단점도 존재한다.

- 오픈 어드레싱 (Open Addressing, 개방 주소법)

충돌이 발생했을 때 해시 테이블 내부에서 다른 빈 버킷을 찾아 저장하는 방식이다. 즉 모든 데이터가 배열 내부에 직접 저장된다.

bucket[10] -> 이미 사용중
bucket[11] 확인 -> 비어있음 -> 저장

별도의 연결 리스트나 포인터 구조가 필요 없고 데이터가 배열에 연속적으로 저장되므로 캐시 효율이 높다.

주의할 점은 삭제 시 값을 단순히 제거하면 탐색 경로가 끊어질 수 있으므로 보통 삭제 표시(tombstone) 방식을 사용하고 테이블이 채워질수록 빈 버킷을 찾기 위한 탐색 비용이 증가하므로 로드 팩터가 낮게 유지되어야 성능이 안정적이다.

4. 리사이즈 (Resize) / 리해시 (Rehash)

해시 테이블의 로드 팩터가 설정된 임계값(threshold)을 초과하면 테이블의 크기를 늘리는 작업이 수행된다.

일반적으로 다음과 같은 과정으로 진행된다.

1. 새로운 더 큰 배열을 생성한다. (보통 기존의 2배 크기)
2. 기존의 모든 데이터를 새로운 배열에 다시 삽입한다.
3. 이 과정에서 해시값을 다시 계산하여 재배치한다.

이 과정을 리사이즈 또는 리해시라고 한다.

리사이즈는 한 번 수행될 때 O(n)의 비용이 발생한다. 따라서 대량의 데이터를 저장할 것이 예상되는 경우 초기 용량을 충분히 설정하는 것이 성능에 유리하다.