해시 테이블 충돌 해결법
Hash table 충돌예방법
지난 포스팅에서 해시 테이블에서의 충돌과 적재율의 개념에 대해 다루었다.
오늘은 지난 포스팅에서 예고한 대로, 충돌을 예방할 수 있는 방법에 대해서 설명해보도록 하겠다.
크게 chaining과 open addressing 방법이 있다.
1. chaining
chaining 방법은 linked list를 사용해서 이미 다른 원소가 그 칸을 차지하고 있더라도 linked list로 이어 주는 것이다.
지난 포스팅에 썼던 예시를 똑같이 사용해보도록 하겠다.
지난 포스팅처럼 x mod 5라는 해시 함수가 존재한다고 하고 9라는 숫자가 들어갔다고 가정해보자.
.png)
그렇다면 이제는 table 자체에 9가 들어가는 것이 아니라 위의 그림처럼 linked list로 9라는 숫자가 들어가게 되는 것이다. 여기에 만약 14라는 숫자가 또 들어온다면 어떻게 될까? 14도 14 mod 5에 따르면 4 자리에 들어가야 하기 때문에 4 자리로 가준다. 하지만 이미 9라는 원소가 들어있다. chaining을 사용하지 않았다면 이전에는 충돌이 일어났지만 이제 우리는 chaining을 사용하기 때문에 linked list로 단순히 연결해주면 된다.
.png)
위 그림처럼 말이다. chaining은 적재율 (load factor)가 1이 넘더라도 사용할 수 있다는 장점이 있지만 추가적으로 linked list가 필요하다는 단점도 있다.
2. open addressing
chaining은 하나의 추가적인 linked list를 잡아먹는다는 단점이 있다. 이것을 보완하기 위해 나온 open addressing은 추가 공간을 허용하지 않고 충돌이 일어나면 다른 공간으로 재배치시키는 과정이라고 볼 수 있다.
즉 open addressing 방법은 충돌이 일어났을 때 추가적인 hash 함수를 사용하여 원소를 다른 곳에다가 재배치시켜준다.
여기서 해시 함수를 정하는 방법에 따라 open addressing은 추가적으로 3가지 type으로 나뉘게 된다.
i ) linear probing
ii) quadratic probing
iii) double hashing
hashing의 경우 한번 open addressing을 하더라도 또 충돌이 있을 수 있기 때문에 일반화하여 i번 hashing을 수행한다고 할 수 있다. i번째 hash 함수를 우리는 hi(x)라고 정의하겠다. (여기서 i는 작은 첨자라고 생각해주면 된다)
i) linear probing
첫번째 linear probing 부터 알아보자
linear probing의 경우 hi(x)는 (h(x) + i) mod m 으로 정의된다. 즉 충돌이 일어난 h(x)에서 i만큼 떨어진 자리에다가 값을 저장하겠다는 것이다. 하지만 i만큼 일차 함수 보폭으로 이동하는 것이기 때문에 특정 영역에 몰릴 경우 굉장히 성능이 저하된다는 단점이 있다. 이것을 "primary clustering"이라고 부르기도 한다.
ii) quadratic probing
이러한 단점을 보완하기 위해 나온 것이 quadratic probing이다. 위 linear probing에서 primary clustering이라는 현상이 나타난 이유가 일차 함수 보폭으로 이동하기 때문인 것이어서 quadratic probing에서는 이차함수 거리로 점프하면서 보는 것이다.
즉 hi(x)는
.png)
이라고 정의할 수 있다. 이렇게 정의한다면 위 primary clustering의 문제점은 해결할 수 있으나, 원소 몇개가 초기에 같은 값을 가지게 되었다면 계속 같은 과정을 거쳐야 한다는 점에서 비효율적인 모습도 다소 있다. 이러한 것을 secondary clustering이라고 부른다. 즉, quadratic probing은 primary clustering의 문제점은 해결할 수 있으나, secondary clustering의 문제점을 가지고 있는 것을 알 수 있다.
iii) double hashing
세 번째 방법은 double hashing이라는 방법이다. double hashing 방법은 secondary clustering을 해결하기 위해 나온 방법으로, 매번 같은 점프를 하는 것을 어느정도 방지할 수 있다.
이 경우에 hi(x)는
(h(x) + if(x)) mod m이라고 정의할 수 있다.
여기서 f(x)는 h(x)와는 또 다른 해시 함수로, double hashing의 의미는 서로 다른 hashing 함수 두개를 사용하였다는 것이다.
double hashing의 경우에 f(x)의 값은 h(x)와 항상 서로소가 되어야 한다.
즉 예를 들어 h(x)의 함수가 x mod 17이라면, f(x)의 함수는 x mod 11로 함으로써 m과 항상 서로소로 만들 수 있다.