해시 충돌 Hash Collision

1. 해싱(Hashing)과 해시 충돌

1.1. 해시 함수와 해시 테이블

해시 함수(Hash Function)는 임의의 길이의 데이터를 고정된 길이의 데이터(해시 값 또는 해시)로 매핑하는 함수입니다. 좋은 해시 함수는 결정론적(입력이 같으면 항상 같은 출력을 냄)이고, 계산이 빠르며, 출력 값이 해시 공간 전체에 고르게 분포(Uniformity)되는 특징을 가집니다.

해시 테이블(Hash Table) 또는 해시 맵(Hash Map)은 이러한 해시 함수를 사용하여 키(Key)를 값(Value)에 매핑하는 데이터 구조입니다. 내부적으로는 배열(버킷 배열, Bucket Array)을 사용하여 데이터를 저장하며, 키를 해시 함수에 입력하여 얻은 해시 값을 배열의 인덱스로 사용하여 값에 매우 빠르게 접근할 수 있습니다. 이론적으로 삽입, 삭제, 탐색 연산에 대해 평균적으로 O(1)의 시간 복잡도를 가집니다.

1.2. 해시 충돌의 정의와 필연성

해시 충돌(Hash Collision)은 서로 다른 두 개 이상의 키가 해시 함수를 거쳤을 때 동일한 해시 값, 즉 동일한 배열 인덱스를 결과로 갖게 되는 현상을 말합니다.

해시 충돌은 비둘기집 원리(Pigeonhole Principle)에 의해 필연적으로 발생합니다. 해시 함수가 가질 수 있는 입력 키의 경우의 수는 거의 무한하지만, 출력 값인 해시 값(배열의 인덱스)의 개수는 유한하기 때문입니다. 따라서 아무리 좋은 해시 함수를 사용하더라도 충돌은 피할 수 없으며, 해시 테이블의 핵심은 이 충돌을 얼마나 효율적으로 처리하고 관리하느냐에 있습니다.

2. 해시 충돌 해결 전략

해시 충돌을 해결하는 방법은 크게 두 가지, 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing)으로 나뉩니다.

2.1. 분리 연결법 (Separate Chaining / Open Hashing)

개념:
분리 연결법은 각 버킷(배열의 각 칸)을 다른 데이터 구조로의 포인터로 활용하는 방식입니다. 충돌이 발생하면, 해당 버킷에 연결된 데이터 구조에 새로운 키-값 쌍을 추가합니다. 이 연결되는 데이터 구조로는 주로 연결 리스트(Linked List)가 사용됩니다.

구현:

1. 키를 해시 함수에 넣어 인덱스를 계산합니다.
2. 해당 인덱스의 버킷을 확인합니다.
3. 버킷이 비어있으면(NULL 포인터), 새로운 연결 리스트를 생성하고 키-값 쌍을 추가합니다.
4. 버킷에 이미 연결 리스트가 존재하면, 리스트의 끝에 새로운 노드를 추가하거나, 리스트를 순회하며 동일한 키가 있는지 확인하고 값을 갱신합니다.

장점:

• 구현이 비교적 간단하고 직관적입니다.
• 테이블의 적재율(Load Factor)이 1을 초과해도 동작하며, 성능 저하가 점진적으로 일어납니다. (테이블이 꽉 찰 걱정이 없음)
• 데이터 삭제가 간단합니다. 해당 노드를 찾아서 연결만 끊어주면 됩니다.

단점:

• 포인터를 저장하기 위한 추가적인 메모리 공간이 필요합니다.
• 하나의 버킷에 데이터가 집중되면(최악의 경우 O(n)), 연결 리스트의 순차 탐색으로 인해 성능이 저하됩니다.
• 노드들이 메모리상에 흩어져 있어 캐시 지역성(Cache Locality)이 좋지 않아, 개방 주소법에 비해 캐시 효율이 떨어질 수 있습니다.

심화: Java 8의 HashMap에서는 하나의 버킷에 연결된 노드의 개수가 특정 임계값(8개)을 초과하면, 성능 향상을 위해 연결 리스트를 균형 잡힌 이진 탐색 트리(Balanced Binary Search Tree, Red-Black Tree)로 변환하여 탐색 시간을 O(log n)으로 개선합니다.

2.2. 개방 주소법 (Open Addressing / Closed Hashing)

개념:
개방 주소법은 모든 데이터를 해시 테이블 배열 내에 직접 저장하는 방식입니다. 충돌이 발생하면, 정해진 규칙에 따라 비어있는 다른 버킷을 찾아 데이터를 저장합니다. 이 '다른 버킷을 찾는 과정'을 조사(Probing)라고 합니다.

조사(Probing) 기법:

1. 선형 조사 (Linear Probing):
   • h(k, i) = (h'(k) + i) mod m (m은 테이블 크기, i는 0, 1, 2, ...)
   • 충돌이 발생한 버킷 바로 다음 칸, 그 다음 칸 순서로 순차적으로 빈 공간을 찾습니다.
   • 문제점: 기본 클러스터링(Primary Clustering) 현상이 발생합니다. 데이터들이 특정 영역에 연속적으로 뭉치게 되어, 이 클러스터 주변에 해싱되는 모든 키들이 긴 탐사 길이를 갖게 되어 성능이 저하됩니다.
2. 제곱 조사 (Quadratic Probing):
   • h(k, i) = (h'(k) + c1*i + c2*i^2) mod m
   • 충돌 발생 시, 1, 4, 9, 16, ... 만큼 떨어진 칸을 순서대로 조사합니다.
   • 선형 조사법의 기본 클러스터링 문제는 완화하지만, 동일한 초기 해시 값을 갖는 키들은 모두 같은 순서로 조사를 진행하게 되는 이차 클러스터링(Secondary Clustering) 문제가 발생할 수 있습니다.
3. 이중 해싱 (Double Hashing):
   • h(k, i) = (h1(k) + i * h2(k)) mod m
   • 두 개의 해시 함수를 사용합니다. h1은 초기 인덱스를 결정하고, h2는 충돌 시 이동할 폭(step)을 결정합니다.
   • h2는 0이 아닌 값을 반환해야 하며, 테이블 크기 m과 서로소인 값을 반환하는 것이 좋습니다.
   • 클러스터링 문제를 효과적으로 해결하여 데이터를 테이블 전체에 가장 고르게 분산시킬 수 있어, 개방 주소법 중 가장 성능이 좋은 방식 중 하나입니다.

장점:

• 포인터를 사용하지 않아 추가 메모리 부담이 없습니다.
• 데이터가 배열에 연속적으로 저장되므로, 캐시 지역성이 좋아 캐시 효율이 높습니다.

단점:

• 데이터 삭제가 복잡합니다. 단순히 데이터를 지우면, 이후의 탐사 과정이 끊어져 다른 데이터를 찾지 못할 수 있습니다. 이를 해결하기 위해 삭제된 데이터를 표시하는 특별한 마커(e.g., DELETED 상태)를 사용해야 합니다.
• 테이블의 적재율이 높아질수록 성능이 급격하게 저하됩니다. 따라서 적재율을 일정 수준 이하로 유지하기 위한 재해싱(Rehashing)이 필수적입니다.
• 클러스터링 문제에 취약할 수 있습니다.

2.3. 고급 충돌 해결 전략

• 재해싱 (Rehashing): 적재율(Load Factor, α = 저장된 데이터 수 / 테이블 크기)이 특정 임계값을 넘어서면, 기존보다 더 큰 새로운 테이블을 생성하고, 기존의 모든 데이터를 새로운 해시 함수(또는 새로운 테이블 크기에 맞게)를 사용해 다시 삽입하는 과정입니다. 비용이 큰 작업이지만, 해시 테이블의 O(1) 성능을 유지하기 위해 필수적입니다.
• 쿠쿠 해싱 (Cuckoo Hashing): 두 개의 해시 함수와 두 개의 테이블을 사용합니다. 모든 키는 두 테이블 중 한 곳에 위치할 수 있습니다. 삽입 시, 첫 번째 위치가 차있으면 두 번째 위치에, 두 번째 위치도 차있으면 기존 원소를 "둥지에서 쫓아내" 다른 위치로 보내는 방식입니다. 최악의 경우에도 O(1)의 탐색 시간을 보장하지만, 삽입이 복잡하고 재해싱이 자주 발생할 수 있습니다.
• 로빈 후드 해싱 (Robin Hood Hashing): 개방 주소법의 변형으로, 공평함에 초점을 맞춘 기법입니다. 삽입 시 충돌이 발생하면, 새로 삽입될 키와 기존 키의 '탐사 거리(초기 해시 위치로부터 얼마나 멀리 떨어졌는가)'를 비교합니다. 새로 삽입될 키의 탐사 거리가 더 길면(더 '가난'하면), 기존 키와 자리를 바꾸고 기존 키를 다시 삽입하는 과정을 진행합니다. 이는 탐사 거리의 분산을 줄여 최악의 경우 탐색 시간을 줄이는 효과가 있습니다.

3. 계층별 해싱의 활용

해싱은 컴퓨터 과학의 전 영역에서 활용됩니다.

• 응용 프로그램 계층: 개발자들이 가장 흔하게 접하는 영역입니다. C++의 std::unordered_map, Python의 dict, Java의 HashMap 등 대부분의 프로그래밍 언어에서 연관 배열(associative array)이나 딕셔너리 구현의 핵심으로 사용됩니다.
• 운영체제 계층: 커널은 내부 자원을 효율적으로 관리하기 위해 해시 테이블을 광범위하게 사용합니다.
  • 프로세스 관리: 특정 PID를 가진 프로세스 제어 블록(PCB)을 빠르게 찾을 때.
  • 파일 시스템: 열린 파일 목록 관리, 파일 경로에 해당하는 inode를 빠르게 찾기 위한 디렉터리 캐시(dentry cache) 등.
  • 네트워킹: 수신된 패킷을 어떤 TCP/UDP 연결에 전달할지 결정하기 위해 (출발/도착 IP, 포트) 튜플을 키로 사용하는 해시 테이블.
  • 메모리 관리: 가상 메모리 시스템에서 페이지 테이블 항목을 관리하거나, 파일 기반 데이터의 캐시인 버퍼 캐시를 관리할 때.
• 하드웨어 계층: 하드웨어 수준에서도 해싱과 유사한 원리가 적용됩니다.
  • CPU 캐시: CPU 캐시는 메모리 주소를 키로 사용하는 하드웨어 해시 테이블로 볼 수 있습니다. 특히 세트-연관 캐시(Set-associative cache)에서 메모리 주소의 특정 비트들을 사용해 캐시 '세트(set)' 인덱스를 결정하는데, 이는 해시 함수와 동일한 역할을 합니다. 여러 메모리 주소가 같은 세트로 매핑되는 것이 바로 해시 충돌이며, 세트 내에 여러 캐시 라인을 저장할 수 있는 구조가 분리 연결법과 유사한 충돌 해결 방식입니다.

4. 충돌 해결 전략 비교

특징	분리 연결법 (Separate Chaining)	개방 주소법 (Open Addressing)
데이터 저장 위치	테이블 외부 (연결 리스트 등)	테이블 내부
캐시 효율성	낮음 (데이터가 흩어져 있음)	높음 (데이터가 인접해 있음)
메모리 사용	포인터로 인한 추가 오버헤드	오버헤드 없음 (데이터만 저장)
적재율(α) 한계	1 초과 가능, 성능 점진적 저하	1 미만으로 유지해야 함, 성능 급격 저하
삭제 연산	간단함	복잡함 (삭제 마커 필요)
구현 복잡도	비교적 간단함	클러스터링, 재해싱 등 고려할 것이 많아 복잡함
주요 장점	안정적인 성능, 간단한 삭제	캐시 효율, 메모리 절약
주요 단점	캐시 비효율, 추가 메모리	적재율에 민감, 복잡한 삭제

5. 구술형 요약

 해시 충돌은 서로 다른 데이터를 해시 테이블에 저장할 때, 해시 함수가 같은 메모리 주소(인덱스)를 반환하는 현상을 말합니다. 입력 데이터의 종류는 무한한데 저장할 공간은 한정되어 있어 필연적으로 발생합니다.

이 문제를 해결하는 대표적인 방법은 두 가지가 있습니다.

 첫 번째는 분리 연결법(Separate Chaining)입니다. 각 메모리 주소를 '연결 리스트'의 시작점으로 사용하는 방식입니다. 충돌이 나면, 해당 주소의 연결 리스트에 새로운 데이터를 추가하기만 하면 됩니다. 구현이 간단하고 데이터가 아무리 많아져도 유연하게 대처할 수 있다는 장점이 있지만, 데이터들이 메모리 여러 곳에 흩어져 저장되므로 캐시 효율이 떨어지고, 최악의 경우 하나의 주소에만 데이터가 몰리면 리스트를 순차 검색해야 해서 성능이 느려질 수 있습니다.

 두 번째는 개방 주소법(Open Addressing)입니다. 충돌이 발생하면, 테이블 내의 다른 비어있는 공간을 찾아 데이터를 저장하는 방식입니다. 비어있는 공간을 찾는 방법에는 순서대로 바로 다음 칸을 보는 '선형 조사', 제곱수만큼 건너뛰며 보는 '제곱 조사', 그리고 또 다른 해시 함수로 이동폭을 정하는 '이중 해싱' 등이 있습니다. 이 방식은 데이터가 한 곳에 모여 있어 캐시 효율이 좋다는 큰 장점이 있지만, 테이블이 점점 차오를수록 성능이 급격히 나빠지고, 데이터를 삭제하는 과정이 복잡하다는 단점이 있습니다.

어떤 방식을 선택할지는 상황에 따라 다릅니다. 데이터의 삽입/삭제가 빈번하고 최대 데이터 양을 예측하기 어렵다면 분리 연결법이 유리하고, 데이터 접근 속도가 매우 중요하고 테이블 크기를 어느 정도 예측할 수 있다면 캐시 효율이 좋은 개방 주소법이 더 나은 선택이 될 수 있습니다.