해싱(Hashing)에 관한 공부

자료구조에 대해서 공부를 시작하려는데 책하나를 가지고 앞에서부터 주욱 공부해 나가는게 좋은 방식이겠지만...

어떤 계기가 있어서 해싱에 대해서 좀 찾아보게 됐고 공부야 뭐 여러가지 그림이나 이해를 돕기위한 자료들로 했지만 일단은 내 머리속에서의 흐름대로 정리하기 위해 간단하게 글로 포스팅한다.

일반적으로 탐색 알고리즘은 키값을 비교해서 그 데이터의 주소를 얻는다.

그래서 속도를 빠르게 하려고 비교 횟수를 줄이기 위한 노력들을 많이 하는데... 주로 데이터를 미리 정렬해놓고 이진검색을 하거나 보간검색을 하는 등 확률적으로 최대한 키값을 빨리 찾아내도록 알고리즘을 만든다.

하지만 해싱을 이런 방식과는 완전히 다르게 탐색시간을 획기적으로 줄일 수 있는 듯 하다.

해싱은 해시테이블에 데이터를 집어넣을 때 일정한 규칙을 가지고 키값을 연산하여 해당 주소에 집어넣는다.

그러므로 해당 키값에 대한 데이터를 찾을때는 키값을 연산하여 주소를 구할수 있고 옵티멀한 경우 한번의 연산만으로도 데이터의 주소를 얻을 수 있다.

이때 연산하는 규칙으로 주로 mod연산을 많이 사용한다고 한다.

하지만 연산에 의한 값이므로 다른 키값에 대한 연산결과가 테이블의 같은 주소를 가르킬 수도 있다.

이런 경우를 충돌이라고 하는데 이 충돌을 해결하기 위해서 충돌 발생시 비어있는 다른 주소를 찾아주는 선형조사법, 이차조사법, 이중 해싱법 등을 사용한다.

선형조사법은 충돌 발생시 바로 다음 주소에 데이터를 집어넣는 방식이다. 단순한 방식이지만 데이터가 특정 구간에 몰리는 clustering 현상이 발생하기 쉽다.

상식적으로 생각해봐도 데이터를 그 바로 다음 부분에 집어넣으면 해시테이블에서 데이터가 들어있는 부분들이 붙어있게 되고 그 붙어있는 덩어리가 커질수록 새로운 키 연산결과가 그 큰 덩어리 가운데 어딘가일 확률도 높아진다. 그냥 덩어리만 붙어있으면 별 상관이 없겠지만 덩어리 바로 다음부분의 빈공간을 찾을때까지 계속 1씩 증가하며 확인과정을 거쳐야 하므로 연산 효율이 크게 떨어진다.

이차조사법은 선형조사법의 군집화 문제를 피하기 위해서 1씩 증가된 주소에 넣는것이 아니라 1 4 9 16 이런식으로 제곱단위로 증가된 주소에 데이터를 넣는 방식이다. 완전히 극복되지는 않는듯.

이중 해싱법은 새로운 연산, 보통 C - key mod C(C는 테이블 크기보다 약간 작은 소수) 이런식으로 많이 정해서 쓰는데 이 연산의 값만큼 뒷쪽 주소에서 빈공간을 찾는 방식이다. 마찬가지로 완전히 극복되지는 않는 듯.

또 아예 충돌이 발생하면 뒷쪽에 연결리스트로 달아버리는 체이닝 기법도 있다. 보통 모든경우에 결과가 위 방식들보다 빠르다고 알고있다.