해시 | 충돌 처리

충돌처리

서로 다른 키에 대해서 해시 함수의 결과값이 같으면 충돌(collision)이라고 합니다. 하나의 버킷에 2개의 값을 넣을 수는 없으므로 해시 테이블을 관리할 때는 반드시 충돌처리를 해야 합니다.

그림을 보면 두 키는 서로 다르지만 해시 함수를 적용해 하시값이 17이 나왔습니다. 이렇게 되면 해시 테이블의 같은 위치를 나타내므로 충돌이 발생합니다. 여기서는 이런 충돌이 발생하면 어떻게 처리해야하는지 알아보겠습니다.

 

체이닝으로 처리하기

체이닝은 해시 테이블에 데이터를 저장할 때 해싱한 값이 같은 경우 충돌을 해결하는 간단한 방법입니다. 체이닝은 충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결합니다.

그림을 보면 키 B와 C를 해싱했을 때 3입니다. 즉, 해시 테이블의 같은 위치를 가리키므로 데이터를 저장할 때 충돌이 발생합니다. 이때 체이닝은 링크드리스트로 충돌한 데이터를 연결하는 방식으로 충돌을 해결합니다. 이후 어떤 데이터가 해시 테이블 상 같은 위치에 저장되어야 하면 이런 방식으로 데이터를 저장합니다. 이처럼 체이닝은 충돌을 링크드리스트로 간단히 해결한다는 장점이 있지만 2가지 단점이 있습니다.

 

해시 테이블 공간 활용성이 떨어짐

충돌이 많아지면 그만큼 링크드리스트의 길이가 길어지고, 다른 해시 테이블의 공간은 덜 사용하므로 공간 활용성이 떨어집니다.

 

검색 성능이 떨어짐

충돌이 많으면 링크드리스트 자체의 한계 때문에 검색 성능이 떨어집니다. 링크드리스트로 연결한 값을 찾으려면 링크드리스트의 맨 앞 데이터부터 검색해야 하기 때문입니다. 다음 그림을 보면 맨 뒤의 키 K에 해당하는 값을 검색하려면 B, C, K를 거쳐 확인해야 합니다. 만약 N개의 키가 있고 모든 키가 충돌하여 체이닝되었다면 마지막 버킷을 검색하는 경우 시간 복잡도는 O(N)입니다.

참고로 자바에서 HashMap 클래스는 체이닝을 사용하여 해시 충돌을 처리합니다. 다만 충돌 발생 시 데이터 접근 시간 복잡도가 O(N)으로 늘어나는 문제가 있으므로 링크드리스트로 연결하는 데이터가 일정 개수가 넘어가면 자동으로 해당 링크드리스트를 이진 탐색 트리로 변환하여 데이터 접근 O(logN)의 성능이 나오도록 개선합니다.

 

개방 주소법으로 처리하기

개방 주소법(open addressing)은 체이닝에서 링크드리스트로 충돌값을 연결한 것과 다르게 빈 버킷을 찾아 충돌값을 삽입합니다. 이 방법은 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용합니다.

 

선형 탐사 방식

선형 탐사(linear probing)방식은 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동합니다. 수식은 다음과 같습니다.

※ 보통 간격은 1로 하는 것이 일반적입니다.

 

h(k,i) = (h(k) + i) mod m

 

m은 수용할 수 있는 최대 버킷입니다. 선형 탐사 시 테이블의 범위를 넘으면 안 되므로 모듈러 연산을 적용한 겁니다. 수식을 그림으로 표현하면 다음과 같습니다.

 

키5에 해시 함수를 적용하면 값2가 있는 위치 정보를 참조하므로 충돌이지만 선형 탐사 방법으로 1칸씩 아래로 내려갑니다. 값3, 값4를 지나 그다음 위치에 값5를 넣습니다. 하지만 이 방법도 단점이 있습니다. 충돌 발생 시 1칸씩 이동하며 해시 테이블 빈 곳에 값을 넣으면 해시 충돌이 발생한 값끼리 모이는 영역이 생깁니다. 이를 클러스터를 형성한다고 하는데요 , 이런 군집이 생기면 해시값은 겹칠 확률이 더 올라갑니다.

※ 그래서 이를 방지하기 위해 제곱수만큼 이동하여 탐사하는 방법도 있습니다.

 

이중 해싱 방식

이중 해싱 방식은 말 그대로 해시 함수를 2개 사용합니다. 때에 따라 해시 함수를 N개로 늘리기도 합니다. 두 번재 해시 함수의 역할은 첫 번째 해시 함수로 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치를 정할지 결정하는 역할을 합니다. 예를 들어 보겠습니다. h1이 1차 해시 함수, h2가 2차 해시함수입니다.

 

h(k,i) = (h₁(k) = i * h₂(k)) mod m

 

수식을 보면 선형 탐사와 비슷하게 더하는 방식으로 데이터의 위치를 정하지만 클러스터를 줄이기 위해 m을 제곱수로 하거나 소수로 합니다. 이는 주어지는 키마다 점프하는 위치를 해시 함수로 다르게 해서 클러스터 형성을 최대한 피하기 위함입니다.

 

실제 코딩 테스트 문제에서 해시 문제의 핵심은 키와 값을 매핑하는 과정입니다. 특정 값이나 정보를 기준으로 빈번한 검색을 해야 하거나 특정 정보와 매핑하는 값의 관계를 확인해야 하는 작업이 문제에 있으면 해시를 고려해야 합니다.