[알고리즘] 해시 알고리즘

Components of Hashing

1. Key : 해시 함수에 입력값으로 들어가는 문자열 혹은 정수를 의미한다. Key를 통해 해시 테이블의 인덱스 값이나 위치를 알 수 있다.
2. Hash Function : 입력 key 값을 받아 해시 테이블의 인덱스 값을 반환하는 함수이다.
3. Hash Table : key-value 형태의 자료구조 이며, 해시 함수를 통해 해시 인덱스를 구성한다.

What is Hash functions?

해시 함수는 수학적인 연산을 통해서, key와 value 사이의 매핑을 만든다. 해시 함수의 결과는 hash value 또는 해시라고 불려진다. hash value는 원래의 문자열을 대표하지만, 일반적으로 원본보다는 길이가 짧다.

 

해시 함수의 종류

Division Method

해시값을 만들기 위한 가장 간다하고 쉬운 방법이다. K를 M으로 나눈 나머지를 해시값으로 사용한다. 해시 테이블의 엔트리에 대해 고르게 분포하도록 M을 소수로 지정하는 것이 효과적이다. 

h(K) = k mod M
k : the key value
M : the size of the hash table

• 장점 : 어떠한 M 값이라도 동작한다. 하나의 나누기 연산만 수행하기 때문에 매우 빠르다.
• 단점 : 연속된 key 값은 연속된 해시값으로 매핑되기 때문에 성능상 좋지 않다(? 이해가 안됨). M의 값을 선정하는데 주의가 필요하다.

Mid Square Method

계산방법

1. Key 값을 제곱
2. 가운데 r 자리를 해시값으로 추출

k = 60 , r = 2
k x k = 3600
h(60) = 60

r의 값은 테이블의 크기에 기반하여 결정한다.

• 장점 : Key 값에 포함된 모든 숫자가 result를 만드는데 기여하므로 성능이 좋다. 원래 Key 값의 상위 혹은 하위 숫자에 의해 value값이 좌우되지 않는다.
• 단점 : Key 값의 크기가 이 방법의 제약사항이다. Key 값이 크다면 result를 추출하기 위한 Key^2은 Key의 자릿수에 두 배가 될 것이다.

Digit Folding Method

계산방법

1. Key 값의 숫자들을 숫자 묶음으로 분리(12345 → 12, 34, 5)
2. 분리된 숫자 묶음을 전부 더하기(12 + 34 + 5 = 51)

k = 12345
k1 = 12, k2 = 34, k3 = 5
s = k1 + k2 + k3 = 51
h(k) = 51

각 부분의 자릿수는 해시 테이블의 크기에 따라 달라진다.

Multiplication Method

계산방법

1. 0 < A < 1 의 숫자를 지정
2. Key값에 A를 곱함
3. kA의 소숫점 아래 숫자만 남김
4. 추출한 수숫점 아래 숫자를 해시 테이블의 크기(M)으로 곱함
5. (4)의 결과값을 반올림

k = 12345
A = 0.357840
M = 100

h(12345) = floor[ 100 (12345*0.357840 mod 1)]
               = floor[ 100 (4417.5348 mod 1) ]
               = floor[ 100 (0.5348) ]
               = floor[ 53.48 ]
               = 53

• 특징 : 해시 테이블의 사이즈가 2의 거듭제곱일 떄 효과적이다.

 

Properties of a Good hash function

모든 item을 각각의 고유한 슬롯으로 매핑하는 해시 함수에 대해 완벽한 해시 함수라고 지칭한다. 만약 item들과 해당 요소들이 변경되지 않는다면 완벽한 해시 함수를 만들 수 있을 것이다. 하지만, 임의의 요소들에 대한 완벽한 해시 함수를 만드는 것은 시스템적으로 불가능하다.

 

따라서, 해시 함수를 만든 때 아래 사항을 유의해야 한다.

1. 효율적 계산가능
2. Key값이 테이블에 균등하개 배분되어야 함
3. 충돌을 최소화
4. 부하율(테이블의 항목 수를 테이블 크기로 나눈 값)이 낮아야 함

 

Problem with Hahsing

 

해싱 프로세스는 Key값보다 더 작은 크기를 가진 해시값을 생성하기 때문에, 서로 다른 두개의 Key가 같은 해시값을 생성할 수도 있다. 이 경우 충돌이 발생한다.

How to handle Collisions?

해시 충돌을 다루는 방법은 크게 Seprate Chaining(Open Hashing)과 Open Addressing(Closed Hashing)으로 나뉜다.

 

1. Separate Chaining

해시 테이블의 각 셀을 연결 리스트로 만드는 방법이다. 같은 해시값을 갖는 경우, 해시 인덱스에 위치한 슬롯에 있는 연결 리스트에 추가될 것이다. 체이닝은 간단하지만, 해시 테이블 외부의 추가적인 메모리 공간을 요구한다.(Java에서 지원하는 방식, 다만 특정 threshold 이후 부터는 TreeMap으로 동작)

2. Open Addressing

Open Addressing 방식에서, 추가적인 메모리 공간할당 없이 모든 요소들이 해시 테이블에 저장된다.

2.a) Linear Probing

선형 탐색 방식에서, 해시 테이블에 대해 Key 값으로 도출한 해시값의 위치가 이미 사용중일 경우, 해시 테이블의 다음 인덱스를 탐색한다. 만약 다음 인덱스에 자리가 있으면, 그 곳에 해시값을 할당한다.

1. hash 값을 계산. EX) key = data % size
2. hashTable[key]가 비어있는지 확인하고, 비어있으며 그곳에 data를 할당
3. 만약 해시 인덱스가 이미 사용중이라면, key = (key + 1) % size를 수행하여 다시 탐색한다.
4. 다음 인덱스가 사용가능하다면 할당하고, 아니라면 다시 반복한다.
5. 적절한 공간을 찾을 때까지 반복한다.
EX> data % 5

2.b) Quadratic Probing

해시 테이블의 비어있는 slot을 찾기 위해, 원래의 해시 인덱스 값에 임의의 2차 다항식의 연속 값을 추가한다. 예를 들어 H 라는 해시 인덱스가 이미 사용중이면, H + 1^2 에 해당하는 인덱스를 확인하고, 이후 H + 2^2 … H + 3^2 형식으로 탐색을 수행한다.

만약 hash(x) % n의 slot이 사용중이면, (hash(x) + 1^2) & n 을 수행하다.
만약 (hash(x) + 1^2) & n의 slot이 사용중이면, (hash(x) + 2^2) & n 을 수행하다.
만약 (hash(x) + 2^2) & n의 slot이 사용중이면, (hash(x) + 3^2) & n 을 수행하다.
비어있는 slot을 찾을 때까지 위 방식을 반복한다.

2.c) Double hashing

두 가지의 해시 함수를 사용한다. 첫번째는 기본 해시 함수이고, 두번째는 첫번쨰 해시 함수를 통해 얻어낸 해시값의 이미 사용중일 떄 사용하는 함수이다.

h(k, i) = (h1(k) + i * h2(k)) % n
- i : 충돌 횟수
- k : Key 값
- n : 해시 테이블 크기

 

 

 

 

 

번외 : Java의 HashMap은 어떻게 동작할까?

JAVA8 기준으로, 해시 충돌을 위해 seperate chaining을 사용한다. 추가적으로, 일정 threshold를 넘어가면 lisked list를 balanced tree로 전환한다. HashMap은 내부적으로 Array<Node> 자료형을 갖는다. Array는 element가 담길 bucket을 의미하고, Node클래스의 인스턴스는는 다음 Node의 래퍼런스를 갖으며, seperate chaining을 지원하기 위한 자료형이다.

 

 

 

- 참고자료

https://www.geeksforgeeks.org/introduction-to-hashing-data-structure-and-algorithm-tutorials/

Internal Working of HashMap in Java.

JEP 180: Handle Frequent HashMap Collisions with Balanced Trees