해싱(Hashing)?

해시함수란?

데이터의 효율적 관리를 목표로 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말한다.

이때 매핑전 원레 데이터의 값을 키(key), 매핑 후 데이터 값을 해시값(Hash Value), 매핑하는 과정을 해싱(Hashing)이라한다.

 

해시테이블의 크기가 m이라면 좋은 해시함수는 임의의 키값을 임의의 해시값에 매핑할 확률이 1/m이다. 특정한 값에 치우지지 않고 해시값을 고르게 만들어내는 해시함수가 좋은 해시함수라 할 수 있다.

 

division method

간단하면서 빠른 연산이 가능한 해시함수, 숫자로 된 키를 해시테이블 크기 m으로 나눈 나머지 값을 해시값으로 반환한다. m은 대게 소수를 쓰며 특히 2의 제곱수와 거리가 먼값을 사용하는 것이 좋다. 해시함수의 특성 때문에 해시테이블의 크기가 정해지는 단점이 존재한다.

 

multiplication method

나눗셈 방법보다는 다소 느린 방식이다. 숫자로 된 키가 k, A는 0과 1사이의 실수 일 때,  h(k) = (kA mod 1) x m 의 식을 사용하여 구한다.

m의값은 보통 2의 제곱수로 정한다.

 

universal hashing

다수의 해시함수를 만들고 이 해시함수의 집합 H에서 무작위로 해시함수를 선택해 해시값을 만드는 기법이다. 

 

해시함수의 경우 해시값의 개수보다 많은 키값을 해시값으로 변환하여 사용하기 때문에 해시함수가 서로 다른 키에 대해 동일한 해시값을 내는 해시충돌(Collision)이 발생하게 된다.

 

 

해시충돌을 해결하기 위한 방법

 

Chaining

해시충돌 문제를 해결하기 위한 방법중 하나로 한 버킷 당 크기의 값에 제한을 두지 않아 모든 자료를 해시테이블에 담는 방법이다. 해당 버킷에 이미 데이터가 존재한다면 연결리스트의 방식으로 노드를 추가하여 다음 노드를 가리키는 방식으로 구현할 수 있다. 유연하다는 장점을 가지고 있지만, 메모리 문제를 야기시킬 수 있다.

Chaining을 사용할 경우 최근 데이터는 연결리스트의 Head에 추가한다. O(1), tail에 저장할 시 O(n)이라고 한다.

Open Addressing

Chaining과 달리 한 버킷당 들어갈 수 있는 노드는 하나 뿐인 해시 테이블 방식이다.

해시함수로 얻은 주소가 아닌 다른 주소값에 저장할 수 있도록 하는 방식으로 메모리 문제가 발생하지 않으나 해시충돌이 발생할 수 있다.

빈 공간을 탐색하는 방법으로는 선형 탐색과 제곱 탐색이 존재한다.

선형 탐색의 경우 기존의 해시값의 버킷에 이미 노드가 존재하는 경우 고정된 값의칸(보통 1칸?) 씩 이동하며 빈 버킷을 찾아가는 방식이다. 단, 특정 해시값 주변 버킷이 모두 채워져 있는 문제에 대해 취약하다.

제곱 탐색의 경우 고정 폭으로 이동하는 선형 탐사와 달리 그 폭이 제곱수로 늘어는 방식이다. 충돌이 일어날 경우 제곱수 칸만큼 옮기는 방식이다. 단, 여러 개의 서로 다른 키들이 동일한 초기 해시값을 갖는 문제에 취약하다. 초기 해시값이 같으면 다음 탐사 위치 또한 동일하기 때문에 효율성이 떨어진다.