Hash Fuction, Hash Table, Hash Collision

Hash Function

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

해시 함수와 관련된 용어를 먼저 살펴보자.

1. Key : 매핑 전 값
2. Hash value : 매핑 후의 값
3. Hashing : 매핑하는 과정

위의 용어들을 기본으로 두고 자세히 살펴보자.

Hash Table

해시 테이블

해시 테이블은 Key를 Hash Function을 사용하여 Hash value로 매핑하고, 이 Hash Value를 index로 Data를 저장하는 방식이다.

듣다보면 파이썬, JS의 Dictionary, 자바의 Map이 떠오를건데 바로 Hash Table을 방식을 택한 자료구조 이다. 

위 사진을 보면 buckets 라는 것이 보인다. buckets 는 해시 테이블에서 데이터가 저장되는 전체 공간을 말하고,

bucket이 해시 테이블의 각 데이터 레코드가 저장되는 공간 하나 하나를 의미한다.

 

여기서 조심해야 할 것은 Key를 Hash Function을 통해 Hash Value로 매핑하는 과정에서 버킷의 총 공간이 부족하거나, 값이 중복되는 경우가 발생 할 수가 있다는 것이다.

 

결국 Hash Function 은 일종의 방식으로 다른 값으로 매핑을 시켜주는 건데 만약 key가 숫자고 Hash Function이 다음과 같다고 해보자.

$ F(key) = key \ mod \ 13 $ 이럴 경우에 key 0 과 key 13은 동일한 Hash Value를 가지게 되고 해시 충돌이 발생할 수가 있다.

 

이와 같이, 다른 키임에도 불구하고 Hash Function을 통해 매핑 된 Hash Value가 같아, 똑같은 버킷 공간을 사용하게 되는 상황을

Hash Collision 이라고 한다. 

따라서, 모든 키가 인덱스가 겹치지 않도록 설정하는 Hash Function을 설정하는 것이 중요한데, 이는 아래서 얘기하도록 한다.

Direct-Address Table

Direct-Address Table

정의는 다음과 같다.

키의 개수와 해시 테이블의 크기가 동일하여 해시 충돌 문제가 발생하지 않는 것

위 사진처럼 키의 개수가 해시 테이블의 크기가 같아 충돌 문제가 발생하지 않는다고 하는데, 여기서 든 의문은 모든 key에 대해서 알 고 있고, 매핑을 통한 Hash Value 가 겹치지 않는 경우를 전제로 얘기를 하는 것 같다. 만약 해시 테이블의 버킷의 사이즈가 키의 개수와 동일하더라도 Hash Value 가 동일하게 나온다면 해시 충돌이 발생 할 수 있다.

 

해시 충돌을 해결하는 기법을 배우기 전에 load-factor라는 용어를 한 번 알아보자.

load-factor

해시 테이블의 버킷에 평균 몇 개의 데이터가 저장되는지에 대한 지표이다. $ N / M $ (N : 키 개수, M : 해시 테이블 크기)

load-factor가 1 이상일 때, 해시 충돌이 발생할 수 있다.

 

해시 충돌(Hash Collision) 해결 기법

해시 충돌 해결 기법으로 크게 2가지를 사용한다.

1. Separate Chaining(분리 연결법)
2. Open Addressing(개방 주소법)

먼저 분리 연결법에 대해서 살펴보고, 이어서 개방 주소법에 대해서 살펴보자.

Separate Chaining

Separate Chaining

Separate Chaining은 그림과 같이, 해시가 충돌이 되면 추가적인 메모리를 사용해 LinkedList 혹은 Tree를 이용해서 구현하는 방식이다.

데이터의 사이즈가 커질수록 LinkedList의 탐색 효율은 떨어지게 될 것이다. 따라서, 데이터가 일정 수준으로 커지면 Tree를 사용해 해결을 한다.

특히, 자바의 Map, Set을 사용할 때에도 위와 같이 Hash Table을 사용해서 데이터를 저장하게 될텐데, JDK 1.8 이상부터는 데이터의 사이즈가 일정 수준 이상으로 커지면 Tree를 이용한다고 한다.

 

이때, Tree가 편향된 트리로 구성될 수도 있기 때문에, Red-Black Tree를 사용하여 트리의 균형을 맞추도록 하여 탐색을 하는데에 있어 $ O(logN) $ 을 보장 할 수 있도록 한다.

Open Addressing

Open Addressing

위에서 봤던 Separate Chaining에서는 버킷에서 충돌이 발생하면 리스트 혹은 트리를 사용해서 해시 충돌을 해결했는데, Open Addressing은 한 버킷에 하나의 데이터만 들어 갈 수 있습니다.

개방 주소법에서는 해시 충돌이 발생하면 비어 있는 다른 공간을 찾아서 적재하는 방식으로 해결하는데, 이러한 방식을 Probing 이라고 합니다. 

Probing 에는 크게 3 가지 방법이 있습니다.

1. Linear Probing (선형 탐사)
2. Quadratic Probing (제곱 탐사)
3. double Hashing (이중 해싱)

각각의 기법마다 장점들이 있고, 단점들이 있습니다. 차례대로 한 번 살펴봅시다.

Linear Probing

Linear Probing 과정

Probing 방식 중 가장 간단한 방식입니다. 최초 해시값에 해당하는 버킷에 다른 데이터가 있다면 순차적으로 이동하여 해결합니다.

정의처럼 상당히 이해하기가 간단합니다.

[단점] : 특정 해시 값 주변 버킷이 모두 채워져 있는 primary clustering에 취약합니다. 즉, 이동하면서 해시 충돌이 연쇄되어 발생할 수 있습니다. 

Quadratic Probing

Quadratic Probing 과정

순차적으로 이동하는 Linear Probing과 달리 Quadratic Probing은 폭을 제곱 수 만큼 늘려서 이동합니다. Linear Probing과 달리 순차적으로 데이터를 저장하지 않기 때문에 primary clustering은 해결할 수 있었으나, 또 다른 문제가 있습니다.

[단점] : 서로 다른 key가 동일한 Hash Value를 가지는 상황인 secondary clustering 에 취약합니다.

Double Hashing

마지막 방식은 위에서 보인 Linear Probing과 Quadratic Probing의 문제를 해결하기 위해서 등장했습니다. 

이름 그대로 두 개의 해시 함수를 사용하여 해싱하는 기법인데, 초기에 사용 될 Hash Function 1개, 해시 충돌 시 사용 될 Hash Function 1개를 사용하여 해시 충돌 문제를 해결합니다. 이에 따라, 위에서 발생했던 2가지 문제점을 해결 할 수 있으나, 이 역시 단점이 존재합니다.

[단점] : 데이터 저장 시 캐시는 참조 지역성의 원리에 따라 저장을 하는데 이와 같이 Double Hashing을 사용하게 되면 캐시의 효율이 굉장히 떨어지게 됩니다. 충돌 시 재 매핑 할 해시 함수가 어떤 Hash Value를 도출하느냐에 따라 현재 적재 된 메모리 공간에서 매우 멀리 떨어져 있는 공간 일 수도 있기 때문입니다. 

또한, 다른 Probing 방식은 해시 함수를 1개를 쓰는데에 비해서, Double Hashing은 2개의 해시 함수를 쓰기 때문에, 상대적으로 연산량이 많다는 문제점도 있습니다.

 

따라서, 데이터의 삽입이 적고 데이터 집합의 크기가 고정적이라면 캐시의 효율성을 위해서 Linear Probing을 사용하는 것이 좋을 것이고, 만약 데이터 집합이 크기가 변동적이고, 데이터의 삽입이 잦다면 Double Hashing 사용하는 것이 좋을 것이다.

이 처럼, 각 기법의 특징을 이해하고 방식을 택하는 것이 중요하다.

 

그런데, 여기서 이런 고민이 생기기도 했다.

음, 데이터를 적재하다가 한 바퀴 돌고 다시 돌았는데도, 버킷에 공간이 없으면 어떡하지?

이것을 방지하기 위해서 Hash Table을 Resize 한다고 한다. Resize도 어느정도의 비용이 발생하기 때문에 적절한 기준을 잡아서 실행하는 것이 중요한데, key-value 쌍 데이터 개수가 약 75% 이상이 되면 Resize 한다고 한다.

해시 충돌을 줄이는 해시 함수

무엇보다 중요한 것은 각각의 키들이 해시 충돌을 발생시키지 않도록 하는 해시 함수를 만드는 것이 가장 중요할 것이다. 해시 충돌이 발생하지 않으면 자연스럽게 해시 충돌에 들어가는 비용을 생각하지 않아도 되기 때문이다! (불가능하긴 하지만)

해시 충돌을 줄이는 해시 함수와 방식은 여러가지가 있지만 3가지만 소개해보겠다.

1. division method
2. multiplication method
3. universal hashing

Division Method

Division Method는 숫자로 된 키를 해시 테이블의 크기 m으로 나눈 나머지를 해시값으로 반환합니다. 이 때, m은 2의 제곱수와 거리가 먼 소수를 사용하는 것이 좋다고 알려져 있습니다. 장점으로는 간단하면서도 빠른 연산이 가능하다는 것이 특징인데, 위와 같은 이유로 해시 함수의 특성으로 인해 해시 테이블 크기가 정해져야 한다는 단점이 있습니다.

Multiplication Method

Multiplication Method는 숫자로 된 키가 k이고, A가 0과 1사이의 실수 일 때 사용합니다.

Division Method와 달리 해당 기법에서 m이 얼마가 되든 크게 중요하지 않지만, 주로 2의 제곱 수로 사용한다고 합니다.

나눗셈법 보다는 다소 느리지만, 2진수 연산에 최적화 된 컴퓨터 구조를 고려하여 만들어진 해시함수 라고 합니다. 

$ h(k) = (kA \ mod \ 1) * m $

Universal hashing

Universal hashing은 다수의 해시 함수를 만들어두고, 해시 함수의 집합에서 해시 함수를 무작위로 선택 해 Hash Value를 반환하는 기법입니다. 

 

참고 
https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/
https://d2.naver.com/helloworld/831311