Data Structure - Hashing ( Hash Functions )

Hash Function

hash function은 key를 bucket에 mapping시켜주기 위한 함수입니다.

• 이는 계산하기 쉬워야합니다. 그리고 collision을 최소화 시킬 수 있어야 합니다.
• 이는 편향적인 결과를 내면 안됩니다. ( 하나에 몰빵되면 안됨 )

 

Uniform hash Function

random key K가 있다고 해 봅시다. 이 때 h(k) = i이 나올 확률은 1/b에 근사해야 합니다. 이러한 hash function을 uniform hash function이라고 합니다.

 

Division

Division은 가장 널리 사용되는 hash function중 하나입니다.  여기서 저희는 key는 음수가 아니라고 가정합니다. 그리고 home bucket은 modulo ( % )연산에 의해 결정됩니다.

이 함수는 bucket address를 0 ~ D-1의 범위에서 줍니다. 이 떄 hash table은 최소 D개가 있어야 합니다.

 

division hash function은 uniform hash function입니다. 하지만 아주 취약한 문제점이 하나 있는데, 실제 사전에서는 D의 값에 따라 overflow가 되는 빈도가 바뀌게 된 다는 것입니다. 

 

• D가 small prime factors 즉 작은 소수 일 떄 편향되게 됩니다. ( e.g. 2, 3, 5, 7 )
• 또한 여기서 D가 증가할 때마다 편향되는 정도는 줄어들었습니다.
• 그래서 저희는 D를 odd and b = D로 설정할 겁니다. 즉 홀수로 설정하고 이 값을 bucket의 개수로 설정해야 한다는 것입니다.
• Array doubling을 나중에 볼거지만 bucket의 수를 증가시키는 과정입니다. 이 떄 두배를 시키면 무조건 D가 2배가 되므로 짝수가 됩니다 그래서 저희는 D를 홀수로 만들어 주기 위해 b -> 2b + 1로 설정해 주어야 합니다. ( D도 마찬가지 )

Mid-Square

mid-square hash function은 home bucket의 키를 key를 squaring하면서 구하는 법입니다.

• 적당한 비트의 수를 정합니다. 그리고 그 비트들을 가져와서 수를 만듭니다.
• 여기서 key는 정수라고 가정합니다.
• 또한 r bit가 사용된다면, 2^r - 1개의 값이 사용됩니다.

예를 들겠습니다. r = 5, k = 20이라고 해 봅시다. 그러면 나올수 있는 b의 값은 2^5(32)개 입니다.그리고 k를 square를 때리게 되면 20^2이므로 400이고 이를 2진수로 표현하면 11001000이게 됩니다. 여기서 MSB을 제외한 5개의 bit를 가져오게 되면 10010이므로 이는 18이 됩니다. 여기서 몇번째 비트부터 5개를 선택할 지도 자명히 있는게 맞다고 교수님께서 설명하셨습니다.

Folding

Foding법은 key를 마지막 부분을 제외한 모든 부분의 길이가 동일하게 여러 부분으로 나누고, 이들 부분을 모두 더하거나 XOR연산을 하 home bucket address로 이용하는 방법입니다.

 

이 중 Shift Folding이란, 각 부분의 값을 계산하기 위해 마지막을 제외한 모든 부분을 이동시켜 최하위 비트(LSB)가 마지막 부분의 자리와 일치하도록 우측 끝을 마추어 더한 값을 버킷 주소로 이용하는 방법입니다.

그 다음에 bouondary Folding이란, Shift Folding과는 기본 개념이 비슷하지만, 나누어진 각 부분의 경계선을 종이 접듯이 접어 역으로 정렬한 다음 같은 자리에 위치한 수를 더한 값을 버킷 주소(인덱스)로 사용하는 방법입니다.

 

Converting Keys to Integer

또한 keys는 해시 함수를 적용하기 위해서 음수가 아닌 정수들로 변화되어야 합니다. 이것은 필수가 아닌데, 그 이유는 몇몇의 해시 함수들은 같은 home bucket으로 다른 키들을 매핑시켜주기 때문입니다.

 

이를 변환하는 코드는 간단히 아래와 같습니다.