해시의 충돌 및 충돌 회피 방법

기초지식

키들의 전체 집합을 U라고 했을 때, 실제로 저장되는 키들의 집합은 K라고 하고 이 K는 U에 비해 상대적으로 작다. 실제 저장되는 K집합이 U에 비해 상대적으로 작기 때문에 해시테이블 T를 위해서 할당된 대부분의 공간이 낭비될 수 있다. 그래서 이렇게 사전에 저장된 키들의 집합 K가 모든 가능한 키들의 전체 집합 U에 비해 훨씬 작을 때 해시 테이블은 직접 주소 테이블보다 훨씬 작은 공간을 필요로 한다. 이때 해시 테이블의 크기를 m이라고 하고 일반적으로 |U|보다 훨씬 작다.

 

해싱을 이용한 방법에서는 키 k를 갖는 원소는 위치h(k)에 저장된다. 즉 키로부터 저장될 위치를 계산하기 위해 해시 함수 h를 사용한다. 여기서 h는 키들의 전체 집합 U를 해시 테이블 T[0..m-1]의 각 위치에 대응시킨다.

 

이런 해싱을 이용하는 경우에는 키 두 개가 동일한 위치에 해시될 수 있다는 단점이 있다. 이런 상황을 충돌(collision)이라고 한다. 가장 이상적인 해결방법은 충돌을 완전히 피하는 것이다. 이를 위해선 적절한 해시함수를 선택하는 것이 중요하다. 그러나 |U| > m이기 때문에 동일한 해시값을 가지는 키가 두 개 이상 존재할 수 있다. 그래서 완전히 충돌을 회피한다는 것은 불가능하다. 따라서 충돌을 해결하는 방법이 필요하다.

 

체이닝(chaining)에 의한 충돌 해결

체이닝에선 같은 위치에 해시되는 모든 원소를 같은 연결 리스트에 넣는다. 이 체이닝을 이용하는 해싱의 수행시간은 최약의 경우 매우 크다. 해싱의 평균 성능은 해시 함수 h가 저장될 키들의 집합을 m개의 위치에 평균적으로 얼마나 잘 분산시키느냐에 달려 있다. (임의의 원소가 기존에 해시된 다른 원소의 위치에 상관없이 m개의 위치에 골고루 해시된다고 가정하고, 이를 단순 균등 해싱(Uniform Distribution Hashing)이라 한다.)

 

개방 주소화 방법(open-addressing)에 의한 대안적 충돌 해결

모든 원소가 해시 테이블 그 자체에 저장된다. 즈, 테이블의 각 저장 위치는 동적 집합의 원소나 null을 포함한다. 이는 체이닝과는 달리 외부에 저장된 리스트나 원소가 없다. 그러므로 open-addressing 방법에서는 해시 테이블이 꽉 차서 더 이상 삽입이 가능하지 않을 수도 있다. 그러므로 적재율은 절대 1을 넘을 수 없다.

 

Open-addressing의 장점은 포인터를 사용하지 않는다는 것이고 대신 조사될 위치의 순서를 계산한다. 포인터를 저장하지 않음으로써 얻어진 추가적인 메모리는 해시 테이블의 저장 공간 확장에 이용된다. 이는 결과적으로 충돌을 줄이고 빠른 접근을 가능하게 한다.

 

Open-addressing 방법에서 원소 삽입을 하기 위해선 키를 저장할 빈 공간을 찾을 때까지 해시 테이블을 연속해서 조사해야 한다.

 

Open-addressing 해시 테이블에서의 삭제는 어렵다. 어떤 위치의 키를 삭제하고자 할때 단순히 null로써 표시해 삭제한다면 그 원소의 다음 위치로 넘어간 키를 검색하는 것이 불가능해진다. 이를 해결하기 위해 null대신  특별한 값 DELETED를 사용할 수 있긴하지만, 이를 사용하면 검색 시간이 해시 테이블의 적재율에 의존하지 않는다. 따라서 키의 삭제가 빈번할 때는 open-addressing 대신 체이닝이 충돌 해결 기법으로 많이 사용된다.

 

Open-addressing에서 요구되는 조사 순서를 계산하기 위해서는 일반적으로 3가지 방법이 있다.

선형조사(Linear Probing)

2차원 조사(Quadratic Probing)

중복 해싱(Double hashing)

 

선형조사(Linear Probing)

일반 해시함수 h'를 보조 해시 함수로 삼는다.

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

여기서 k는 주어진 키, m은 해시 테이블의 크기 i = 0, 1, …, m-1 이다.

Linear probing은 구현하기는 쉽지만, first clustering이라는 문제때문에 어려움을 겪는다. 다시말하면, 데이터가 연속적으로 길게 저장되면 체증을 일으켜 평균 검색 시간이 증가한다.

 

2차원 조사(Quadratic Probing)

h(k, i) = (h'(k) + c1*i + c2*i^2 ) mod m

여기서 h'는 보조 해시 함수이고, c1과 c2는 양의 보조 상수, i = 0, 1, …, m-1이다.

이 방법은 Linear probing보다는 훨씬 잘 작동하지만 해시 테이블을 최대한 사용하기 위해서는 상수 c1, c2, m값을 잘 정해줘야한다. 그런데, quadratic probing은 Second Clustering이라는 primary clustering보다는 가벼운 군집을 초래한다. 예를 들어, h(k1, 0) = h(k2, 0)이면 h(k1, i) = h(k2, i)가 되므로 두 개의 키가 같은 초기 조사 위치를 가지면 그 조사 순서도 같다. 이처럼 Linear Probing과 같이 초기 조사가 전체 조사 순서를 결정하기 때문에 단지 m가지의 조사 순서가 존재한다.

 

중복 해싱(Double hashing)

Double hashing은 생성된 조사 순열이 무작위 순열의 특징을 많이 지니고 있기 때문에 open-addressing 방법에서 가장 좋은 방법 중 하나를 제공한다. 이는 다음과 같은 형태의 해시함수를 이용한다.

 

h(k, i) = (h1(k) + i*h2(k)) mod m

 

여기서 h1과 h2는 보조 해시 함수다.

Double hashing 방법은 linear probing과 quadratic probing과는 달리 초기 조사 위치와 오프셋이 모두 다를 수 있어서 조사 순서는 각 단계마다 두 갈래로 다양해진다.

 

h2(k)값은 검색되어야할 전체 해시 테이블의 크기 m과 서로소인 값이어야 한다.