Hash란?

Hash

해시는 Hashtable, Hashmap, SHA, MD와같이 알고리즘, 암호학에 사용된다.

해시함수를 통하여 어떠한 데이터를 고정길이의 데이터로 매핑한다. 원 데이터 값은 Key, 매핑 후의 값은 HashValue, 이 과정들을 Hashing이라한다.

Collision

Hashing은 Key를 고유의 계산식을 통하여 HashValue를 만드는 것이라고 하였다.

그럼 충돌은 무엇이고, 왜 일어날까?

충돌은 각각 다른 A, B의 Key를 Hashing했을 때, 둘 다 같은 HashValue를 가진 경우를 충돌했다고 한다.

서로 같은 HashValue를 들고 Bucket(저장공간)에 접근을 했다면, 충돌이 일어난 주소에는 누구를 저장해야할까?

위의 그림을 예시로 생각해보자.

그림이 마치 배열을 연상하게끔 하는데, 배열로 보면 {1,2,3,4,5,6,7}은 Index, 그 옆은 값을 저장하는 공간이고, 홍길동과 임꺽정은 포인터다.

배열에서는 각각의 값마다 고유의 Index를 가지고 정해진 양의 데이터를 정해진 공간에 저장하므로 같은 Index의 공간에 서로 저장하려고 하는 

저런 경우가 없지만, Hash는 Hash Function의 고유 계산식을 통해 값을 산출하는 방식이므로 위처럼 동일한 값이 나올 수 있다.

그래서 Key 홍길동의 HashValue는 3, Key 임꺽정의 HashValue는 3이라고 가정했을 때, 서로는 같은 곳을 차지하려하고 있다.

그렇게 동일 값이 나오면 어떻게 해야할까?

Collision Resolve

충돌을 해결하는 방법에는 첫번째로 chaining이 있다.

위처럼 같은 HashValue를 가질 경우, Bucket에 Linked-List를 이용하여 값을 연달아 저장하는 방식이다.

3번 Bucket에는 Linked-List가 있고, 첫번째는 길동이집주소가, 두번째에는 꺽정이집주소가 저장되는 것이다.

또, open addressing방식이 있다. 이는 chaining처럼 bucket에 Linked-List를 이용하여 여러 값을 넣는 것과는 달리 이는 한 bucket에 하나만 들어갈 수 있다.

linear probing(선형 탐색)은 꺽정이가 늦게 왔다고 가정했을 때, 3번 bucket에는 길동이가 먼저 차지했다. 그렇다면 꺽정이는 다음 방인

4번 bucket으로 가서 자리가 있는지 확인을 하고, 비어있다면 그 곳을 차지한다. 혹여나 4번 bucket에도 누군가 자리를 차지했다면 5번으로 간다.

즉 한칸씩 옆으로 가서 확인하고 자리를 차지하는 방식이다. (무조건 한칸씩이 아닌, 정해진 폭만큼 이동한다.(2칸씩일 수도 있다.))

quadratic probing(제곱 탐색)은 linear probing처럼 옆칸으로 가지만, 정해진 폭만큼이 아닌 제곱의 폭만큼 이동한다.

3번 bucket이 길동이가 차지하고 있어서 4번을 갔더니 거기도 누군가 차지하고 있었다. 그럼 4(2의 제곱)만큼 떨어진 7번 bucket으로 간다.

거기도 꽉차있으면 9(3의 제곱)만큼 떨어진 12번 bucket으로 간다. 거기도 꽉차있으면 16(4의 제곱)만큼 떨어진 19번 bucket으로 간다.

이를 제곱 탐색이라고 한다.

double hasing(더블 해싱)은 해시함수를 2개를 쓰는 방법인데, 1번 해시함수는 HashValue를 만든다. 그리고 2번 해시함수는 충돌시 이동하는 폭을 정한다. 단 이 방법은 1번 해시함수에서 나온 해시값과 2번 해시함수에서 나온 해시값은 서로소여야만하는 조건이 있다.

이 외에도 많은 collision resolve 방법이 있다.

Hash Function

해시함수는 해시값을 쉽게 계산해내고, 해시의 문제점인 Collision(충돌)을 최소화시키고, 그 충돌을 해결하고, 각 공간에 균일하게 값을 분포시키는 역할을 한다.

이 해시함수들은 각각 다른 고유의 계산식을 가지고 있어서 같은 Key를 Hashing하더라도 다른 HashValue가 도출된다.

Division Method(나눗셈법), Multiplication Method(2진수 연산에 최적화된 함수), Universal Hasing(다수의 해시함수를 두고 무작위로 골라 해싱) 등 여러 방법이 있다.

최적화된 해시함수는 임의의 Key가 특정한 HashValue로 치우치지 않고, 고루고루 분포되게 하는 함수가 최적의 함수이다.

참조

Hash Tables and Hash Functions (Computer Science)

https://www.youtube.com/watch?v=KyUTuwz_b7Q

What is a HashTable Data Structure - Intoduction to Hash Tables, Part 0 (Paul Programming)

https://www.youtube.com/watch?v=MfhjkfocRR0