해시 충돌(Hash Collision)이란 무엇이며, 어떻게 해결할까?

백엔드 개발에서 성능은 매우 중요하며, 데이터를 빠르게 조회하기 위해 해시(Hash) 기반의 자료 구조(해시 테이블, 해시맵 등)를 빈번하게 사용합니다. 해시 자료 구조의 핵심과 성능 저하의 주범인 '해시 충돌'에 대해 알아보겠습니다.

---

해시(Hash) 자료 구조란?

해시 자료 구조는 키-값 쌍(Key-Value pair)으로 이루어진 데이터 구조입니다.

가장 큰 특징은 키(Key)를 이용해 값(Value)을 평균 $O(1)$의 매우 빠른 시간 복잡도로 찾을 수 있다는 것입니다.

이것이 가능한 이유는 내부적으로 키를 해시 함수(Hash Function)에 통과시켜 반환된 '해시 값'을 배열의 인덱스로 사용하여 값을 관리하기 때문입니다.

해시 충돌 (Hash Collision) 이란?

해시 자료 구조는 키를 해시 함수에 넣어서 나오는 결과를 기반으로 값을 관리합니다. 하지만 해시 함수는 종종 서로 다른 키를 사용해도 같은 해시 값을 반환하는 경우가 존재합니다.

이처럼 서로 다른 키가 같은 인덱스(버킷)로 매핑되는 상황을 해시 충돌(Hash Collision)이라고 합니다.

해시 충돌이 발생하면 $O(1)$의 시간 복잡도를 보장할 수 없게 되며, 충돌이 많아질수록 성능은 $O(n)$에 가까워질 수 있습니다. 따라서 이 충돌을 효율적으로 관리하고 완화하는 것이 핵심입니다.

---

해시 충돌 완화 전략

해시 충돌을 완화하기 위한 접근 방법으로 크게 두 가지가 대표적입니다.

1. 분리 연결법 (Separate Chaining)
2. 개방 주소법 (Open Addressing)

1. 분리 연결법 (Separate Chaining)

분리 연결법은 이름 그대로 충돌이 발생한 데이터를 기존 데이터에 '연결'시키는 방식입니다.

즉, 각 버킷을 단순한 값이 아닌 연결 리스트(Linked List)나 트리(Tree) 형태로 관리하여, 충돌이 발생하더라도 해당 버킷에 데이터를 계속해서 추가할 수 있도록 합니다.

• 장점: 구현이 비교적 간단하고, 데이터가 많아져도(적재율이 높아져도) 개방 주소법에 비해 성능 저하가 완만한 편입니다.
• 단점: 연결 리스트나 트리를 위한 추가적인 메모리 공간이 필요합니다.

(추가) 분리 연결법의 성능 최적화 (List to Tree)

하나의 버킷에 데이터가 계속 쌓여 연결 리스트가 길어지면, 해당 버킷을 탐색하는 시간은 $O(n)$이 되어 성능이 저하됩니다.

많은 현대 언어의 해시맵 구현체(예: Java의 HashMap)는 이 문제를 해결하기 위해, 특정 버킷의 연결 리스트 길이가 일정 임계값(예: 8개)을 초과하면, 해당 버킷의 자료 구조를 연결 리스트에서 레드-블랙 트리(Red-Black Tree)와 같은 균형 잡힌 이진 탐색 트리로 변환합니다.

• 연결 리스트: 탐색 시간 $O(n)$
• 트리: 탐색 시간 $O(\log n)$

이를 통해 최악의 경우에도 탐색 성능을 $O(\log n)$으로 보장할 수 있습니다.

2. 개방 주소법 (Open Addressing)

개방 주소법은 충돌이 발생했을 때, 해당 버킷이 이미 사용 중이라면 다른 비어있는 해시 버킷을 찾아 데이터를 삽입하는 방식입니다.

• 장점: 추가적인 메모리 공간이 필요 없으며, 데이터가 적을 때는 분리 연결법보다 빠를 수 있습니다. (캐시 효율성)
• 단점: 데이터가 많아질수록(적재율이 높아질수록) 빈 버킷을 찾는 과정이 길어져 성능이 저하될 수 있으며, 데이터 삭제가 까다롭습니다.

---

개방 주소법의 '다른 버킷' 찾는 방법 (Probing)

개방 주소법에서 빈 버킷을 찾기 위한 탐사(Probing) 방법에는 여러 가지가 존재합니다.

1. 선형 탐사법 (Linear Probing)

임의의 고정된 크기(예: 1)만큼 한 칸씩 순차적으로 이동하며 빈 버킷을 찾는 가장 간단한 방법입니다.

• 단점: 특정 버킷 주변이 모두 채워져 있는 1차 군집 현상(Primary Clustering)이 발생하기 쉽고, 이 경우 해시 성능이 크게 저하될 수 있습니다.

2. 제곱 탐사법 (Quadratic Probing)

선형 탐사법처럼 한 칸씩 찾는 것이 아닌, $1^2, 2^2, 3^2, ...$ 만큼의 보폭으로 제곱으로 늘려가며 빈 버킷을 찾습니다.

• 장점: 보폭이 점점 늘어나기 때문에 1차 군집 현상을 완화하여 특정 영역을 빠르게 벗어날 수 있습니다.
• 단점: 여러 키가 해시 함수로 같은 값을 갖게 될 경우, 모두 같은 순서로 탐사하게 되어 비효율적인 상황(2차 군집 현상, Secondary Clustering)이 발생할 수 있습니다.

3. 이중 해싱 (Double Hashing)

해시 충돌이 발생하는 경우, 두 번째 보조 해시 함수(Auxiliary Hash Function)를 사용하는 방법입니다.

첫 번째 해시 값으로는 초기 위치를 정하고, 충돌 시 두 번째 해시 함수의 결과값만큼 일정하게 이동하며 빈 버킷을 찾습니다.

• 장점: 키마다 이동하는 보폭이 달라지므로, 군집 현상(Clustering)이 발생할 가능성이 가장 작습니다.
• 단점: 추가적인 보조 해시 함수 연산이 필요하므로 다른 방식에 비해 연산량이 많습니다.

---

(추가) 해시 성능 유지를 위한 핵심: 적재율과 리해싱

해시 충돌은 피할 수 없지만, 충돌이 '너무 자주' 일어나지 않도록 관리하는 것이 중요합니다. 이때 사용되는 개념이 적재율(Load Factor)입니다.

• 적재율 (Load Factor): 해시 테이블의 전체 버킷 수 대비 현재 얼마나 많은 데이터가 저장되어 있는지를 나타내는 비율입니다.
  • 적재율 = (저장된 데이터 개수) / (전체 버킷 수)

적재율이 너무 높아지면(예: 0.75 이상) 빈 공간이 줄어들어 해시 충돌이 급격하게 증가하고 성능이 저하됩니다.

리해싱 (Rehashing)

이 문제를 해결하기 위해 해시 테이블은 적재율이 특정 임계값(예: Java HashMap의 기본값 0.75)을 초과하면 리해싱(Rehashing)을 수행합니다.

리해싱이란, 기존보다 더 큰 크기(보통 2배)의 새로운 버킷 배열을 생성한 뒤, 기존의 모든 데이터를 새로운 해시 함수(또는 변경된 인덱스 계산)에 따라 새 배열에 다시 삽입하는 과정을 말합니다.

리해싱은 비용이 많이 드는 작업이지만, 적재율을 낮춰 다시 $O(1)$의 평균 시간 복잡도를 유지할 수 있도록 해주는 필수적인 작업입니다.