해시 함수와 충돌 해결

핵심 정리

해시 함수는 임의 길이의 데이터를 입력받아 해시 값을 계산하는 함수이다. 해시 함수는 임의의 비트열을 고정 길이의 비트열로 사상한다. 주어진 출력에 대응하는 입력을 찾거나 같은 출력을 내는 다른 입력을 찾기는 계산상 어렵다. 해시 테이블에서는 탐색키를 테이블의 주소인 슬롯으로 옮길 때 이 함수를 사용한다.

서로 다른 탐색키가 해시 함수를 거쳐 같은 해시 주소로 사상되는 충돌이 발생할 수 있다. 해시 탐색의 성능은 충돌을 어떻게 처리하는지에 따라 달라진다. 충돌이 없으면 주소를 한 번 계산해 탐색을 끝내지만, 충돌이 많아질수록 같은 주소에 모인 원소를 더 확인해야 한다.

충돌이 전혀 없으면 해시 탐색의 시간 복잡도는 O(1)이다. 이 성능은 충돌이 없다는 조건에서 성립한다. 반면 최악의 경우에는 모든 키가 한 버킷에 모여 선형 시간이 걸리므로, 이진 탐색의 O(log n)보다 느릴 수 있다.

탐색키를 여러 부분으로 나눈 뒤 더하거나 XOR하여 주소를 얻는 해시 함수는 폴딩(접지) 함수이다. 충돌을 해결하는 대표적인 기법은 체이닝과 선형 조사법이다. 체이닝은 같은 해시 값을 가진 원소들을 연결 리스트로 묶어 충돌을 해결하는 기법이다.

자세히

충돌이 없을 때와 최악의 경우

해시 탐색은 키마다 주소가 따로 있으면 주소를 한 번 계산해 원소에 도달한다. 충돌이 생기면 같은 주소에 모인 원소를 차례로 확인해야 하므로 탐색 시간이 늘어난다. 탐색 시간을 묻는 문제에서는 충돌이 없는 경우와 모든 키가 한 버킷에 모인 경우를 구별해야 한다. 최악의 경우에는 해시 함수가 키를 고르게 분산하지 못하므로 해시 탐색의 상수 시간 장점이 사라지고 선형 시간이 걸린다.

폴딩 함수

폴딩 함수는 탐색키를 여러 부분으로 나눈 뒤 각 부분을 더하거나 XOR하여 주소를 만든다. 나눈 조각을 합치는 연산으로 주소를 정하므로 주소 계산이 단순하다. 폴딩은 주소를 얻는 방법이지 충돌 해결 기법이 아니므로, 체이닝이나 선형 조사법과 구분해야 한다.