11. Hash

해시 함수(hash function)

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

 

해시는 매핑을 통해 원하는 데이터를 더욱 빠르게 접근해 사용할 수 있도록 돕습니다.

또한, 해시는 복호화가 어렵다는 특징을 가지기 때문에 암호학 및 블록 체인 구현에 있어 중요한 요소입니다.

대표적인 알고리즘으로 MD5, SHA 등이 있습니다.

 

입력한 데이터와 출력된 데이터 'input - key / output - value' 이렇게 표현합니다.

크기는 동적으로 변화하며, 해시 값 자체를 index로 사용하기 때문에 탐색 시간 복잡도는 O(1)입니다.

충돌과 관련된 방법을 익히고 계셔야 O(1)라고 말할 수 있는 근거가 있다고 생각합니다. 각 방식을 단순 외우기보단 꼭 이해해 보시기 바랍니다.

 

아래와 같이 key가 입력되고 hash 함수를 통해 변형시키면 value를 얻을 수 있습니다.

그림 1. Hash

노란색으로 표시한 부분은 해시 충돌이 발생하는 모습을 나타냈습니다.

 

해시 충돌 (Collision)

해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황

해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, *비둘기집 원리에 의해 해시 충돌은 항상 존재

즉, 입력값 > 출력값 인 경우

 

해시 함수는 해시 충돌이 발생할 수 밖에 없는데, 해시 충돌은 성능 저하를 유발하게 됩니다.

특히, 해시 슬롯이 충돌로 인해 항상 동일한 슬롯을 반환하는 경우 시간복잡도는 O(1) -> O(N)까지 저하됩니다.

 

 

이렇게 충돌로 인한 성능 저하를 막기 위해 해시 충돌을 해결하기 위한 방법이 존재합니다.

SeparateChaining, Open Addressing 입니다.

 

Separate Chaining (Java hash)

충돌 시 해시 테이블 인덱스에 연결 리스트를 이용해서 여러 값을 연결한 형태로 저장합니다.

즉, 충돌이 나면 그 위치에 리스트로 붙여 회피하는 방식입니다.

그림 2. Chaining

 

 

상대적으로 적은 메모리를 사용하나, 해시 함수가 고른 분포를 만들지 못하면 이 또한 성능에 좋지 않습니다.

예를 들어 해시가 하나의 버킷에 몰리면, 결국 단일 연결리스트 구성이 되고, 연결리스트 탐색은 O(N)의 복잡도를 가지기 때문입니다.

 

 

Open-Addressing

충돌 시, 연결이 아닌 비어있는 인덱스를 찾아 데이터를 저장하는 방식입니다.

단순하게 말해 충돌 발생시 정해둔 규칙에 따라 비어있는 인덱스를 찾고 저장합니다.

 

Linear Probing

i개 후에 비어있는 슬롯에 노드를 저장한다. 비어있지 않으면 i를 1씩 증가

충돌이 나면 데이터를 바로 뒷 슬롯에 담기 때문에 데이터가 밀집 돼 덩어리를 이루는 문제점 발생 (Primary clustering)

$$ h(k, i) = h(k)+i .. (mod, m) $$

 

Quadratic Probing

2차식 형태로 만들어 해시의 위치를 찾는다. (Primary clustering 해결 방안)

그러나 처음 해시값이 같을 경우 동일한 위치의 슬롯에 접근해 지속적인 충돌 발생 (Secondary clustering)

$$ h(k, i) = h(k)+c_1*i+c_2*i^2 .. (mod, m) $$

 

Double Hashing

다른 해시 함수 (해시 함수 두개로 활용) 를 한 번 더 적용한 해시에 데이터를 저장한다. (Secondary clustering 해결 방안)

$$ h(k, i) = h_1(k)+i * h_2(k) .. (mod, m) $$

 

 

이렇게 해시를 사용하는 이유와 구조적인 구성, 그리고 해싱간 발생하는 충돌에 대해 알아봤습니다.

자신이 사용하는 언어에서 어떻게 적용되고 있는지 아는 것도 중요할 것 같은데.. 한 번 찾아보시는 것이 좋겠습니다.

 

 

 

 

* 비둘기집 원리: 비둘기 집 10개에 비둘기 11마리를 나누어 넣는 경우 비둘기 집 10개 중  최소 하나의 집에는 비둘기 2마리가 존재한다는 원리

 

참고 자료

Wikipedia - Linear probing

Wikipedia - Quadratic probing

Wikipedia - Double hashing

Hash.kr - Hash

Stack overflow - HashTable - why is it faster than array?

Hash function cryptography

geeks for geeks - Hashing in Java