해시 충돌(Hash Collision)과 해결 방법

🔍 해시란?

해시(Hash) 자료 구조는 키-값 쌍으로 데이터를 저장하고, 키를 이용해 값을 평균 O(1)의 시간 복잡도로 조회할 수 있게 도와줍니다.

해시 테이블에서는 해시 함수를 통해 키를 특정 위치(버킷)에 매핑합니다.

하지만, 서로 다른 키가 같은 해시값(버킷)으로 매핑되는 경우가 존재하는데 이를 해시 충돌(Hash Collision)이라고 합니다.

⚠️ 해시 충돌이란?

✅ 정의

해시 충돌이란 서로 다른 키들이 동일한 해시 인덱스에 위치하는 현상입니다. 해시 함수가 완전하지 않거나, 저장 공간이 제한된 경우 필연적으로 발생할 수 있습니다.

✅ 예시

Key1 → hash(Key1) = 3
Key2 → hash(Key2) = 3

→ Key1과 Key2 모두 같은 버킷(3번)에 저장되며, 충돌이 발생합니다.

🧩 해시 충돌 해결 전략

1️⃣ 개방 주소법 (Open Addressing)

충돌이 발생하면, 다른 빈 버킷을 찾아 데이터를 저장하는 방식입니다.

📌 선형 탐사법 (Linear Probing)

• 현재 인덱스에서 한 칸씩 순차적으로 이동하면서 빈 공간 탐색
• 충돌 발생 시: i+1, i+2, i+3, ...
• 문제점: 1차 군집 현상 발생 가능

📌 제곱 탐사법 (Quadratic Probing)

• 탐색 간격을 제곱 형태로 늘려 충돌을 피함
• 충돌 발생 시: i+1^2, i+2^2, i+3^2, ...
• 장점: 근접 버킷 밀집 완화
• 단점: 2차 군집 현상

📌 이중 해싱 (Double Hashing)

• 보조 해시 함수를 사용해 탐색 거리 계산
• 예: i + f2(key) * j
• 장점: 군집 최소화
• 단점: 해시 계산 복잡도 증가

2️⃣ 분리 연결법 (Separate Chaining)

• 해시 버킷에 리스트(또는 트리)를 연결하여 여러 데이터를 저장
• 충돌된 모든 키를 해당 리스트에 삽입

예시:

bucket[3] → [Key1:Val1] → [Key2:Val2]

• 장점: 충돌된 키 개수와 상관없이 저장 가능
• 단점: 탐색 시 O(n)까지 성능 저하 가능

🧠 정리

📝 결론

• 해시 자료 구조는 효율적인 검색을 가능하게 하지만 충돌이 불가피합니다.
• 사용 목적, 데이터 분포에 따라 적절한 충돌 해결 전략을 선택해야 합니다.
• Java, Python 등 대부분의 언어에서 내장 해시 구조는 분리 연결법을 기반으로 구현되어 있습니다.