1. 대표적인 회피 전략 #
Hash collision은 다양한 방법의 회피 전략이 있다. 기본적으로 두 종류의 회피 전략이 있다.
- 닫힌 주소(열린 해싱): 해시 테이블의 각 슬롯은 다른 자료구조로의 연결(예: 연결 리스트)을 가지고 있고, 이 자료 구조는 같은 해시 값을 가지는 키-값 쌍을 저장한다. 이 자료구조에 대해 같은 키 값을 가진 키-값 쌍이 검색되어 진다.
- 열린 주소(닫힌 해싱): 각 슬롯이 키-값 쌍을 저장한다. 충돌이 일어날 때 열린 주소 전략은 빈 슬롯을 찾기 위해 다른 위치를 계산한다(예: 다음 빈 슬롯). 이 전략은 해시 테이블이 빽빽하게 차 있을 때(로드 팩터 0.7 이상) 급격한 성능 하락을 경험할 수 있다.
2. 해시 충돌 회피 방법 #
해시 충돌은 해시 함수가 서로 다른 입력에 대해 동일한 해시 값을 생성할 때 발생한다. 이는 해시 테이블에서 키 충돌로 이어지며, 데이터의 무결성과 검색 성능을 저하시킬 수 있다.
해시 충돌 회피는 다음과 같은 방법들이 일반적으로 사용된다.
- 체이닝 (Chaining)
체이닝은 해시 충돌 시 연결 리스트를 사용하여 충돌이 발생한 버킷에 여러 개의 데이터를 저장하는 방식이다. 각 버킷은 링크드 리스트의 노드가 되며, 충돌이 발생하면 링크드 리스트의 새로운 노드를 추가한다.
- 개방 주소법 (Open Addressing)
개방 주소법은 충돌이 발생하면 다른 버킷을 사용하는 방식이다. 선형 조사 (Linear Probing), 이차원 조사 (Quadratic Probing), 이중 해시 (Double Hashing) 등 다양한 방법이 있다.
- 완벽 해시 (Perfect Hashing)
완벽 해시는 충돌이 전혀 없는 해시 함수를 사용하는 방식이다. 이를 위해서는 입력 데이터의 특성에 맞는 해시 함수를 찾아야 한다. 예를 들어, 정적인 데이터 집합에 대해 미리 계산된 해시 함수를 사용할 수 있다.
- 유니버설 해싱 (Universal Hashing)
유니버설 해싱은 해시 함수를 무작위로 선택하는 방식이다. 여러 개의 해시 함수를 미리 만들어 놓고, 입력 데이터에 따라 무작위로 선택한다. 이를 통해 충돌을 최소화할 수 있다.
- 분리 연쇄법 (Separate Chaining)
분리 연쇄법은 체이닝과 비슷한 방식으로 충돌이 발생하면 해당 버킷에서 연결 리스트를 사용한다. 하지만 체이닝과는 달리, 연결 리스트를 다른 배열에 저장한다. 이를 통해 캐시 효율성을 높일 수 있다.
- Cuckoo Hashing
Cuckoo Hashing은 두 개의 해시 함수와 두 개의 해시 테이블을 사용하는 방식이다. 충돌이 발생하면 다른 해시 테이블에 값을 저장한다. 이를 반복하다가 한 테이블이 꽉 차면 다른 해시 함수를 사용하여 다른 값을 저장한다.
3. 해시 충돌 회피 방법을 선택할 때 고려해야 하는 요소 #
해시 충돌 회피 방법을 선택할 때 고려해야 할 요소는 다음과 같다.
- 데이터 크기
데이터의 크기에 따라 체이닝이나 분리 연쇄법과 같은 방식이 유용할 수 있다. 대규모 데이터에 대해 빠른 검색 성능을 보장하는 방식을 선택해야 한다.
- 데이터 특성
데이터의 특성에 따라 해시 함수와 충돌 회피 방법을 선택해야 한다. 예를 들어, 입력 데이터가 균등하게 분포하지 않은 경우 유니버설 해싱이나 완벽 해시를 사용할 수 있다. 반면 입력 데이터가 균등하게 분포하는 경우 개방 주소법이나 체이닝을 사용하는 것이 좋다.
- 메모리 제약
메모리 제약이 있는 경우에는 분리 연쇄법과 같이 캐시 효율성이 높은 방식을 선택해야 한다.
- 삽입과 삭제 연산의 빈도
삽입과 삭제 연산의 빈도가 높은 경우에는 개방 주소법이나 분리 연쇄법과 같이 연결 리스트를 사용하는 방식이 적합하다. 반면, 삽입과 삭제 연산이 적은 경우에는 개방 주소법이나 완벽 해시를 사용하는 것이 좋다.
- 해시 함수의 성능
해시 함수의 성능에 따라 검색 성능이 크게 달라질 수 있다. 따라서 해시 함수를 공들여 설계하고, 충돌이 최소화되도록 만들어야 한다.
- 해시 테이블의 크기
해시 테이블의 크기에 따라 충돌이 발생할 확률이 달라진다. 따라서 해시 테이블의 크기를 충분히 크게 설정하여 충돌이 최소화되도록 해야 한다.