해시 알고리즘

해시 함수는 어떤 길이의 데이터를 입력해도 정해진 길이의 결괏값을 준다.

 

데이터를 저장하는 방식으로 볼 때, 해시 함수에는 다양한 방식이 있다.

 

Direct-address tables

Direct-address tables는 크기가 U인 테이블 T를 생성하고 key K를 slot K에 저장하는 방식이다.

이때 중복되는 key는 없다고 가정한다. 전체 크기가 U인 곳에서 actual key K가 존재한다고 생각한다. 해당되는 데이터를 table에 저장하고 필요한 key값과 그에 해당하는 data를 확인하는 자료구조이다.

 

해당 방식은 수행 시간이 매우 짧다는 장점이 있다. key값을 알고 있으면 table에서 바로 data를 찾을 수 있기 때문이다. 하지만 공간 복잡도 측면에서는 실제 사용 공간이 적어 공간이 낭비될 수 있다.

 

또한, Hashing은 key k를 저장할 때 slot k가 아니라, slot h(k)에 저장하는 것을 의미한다. 이때 h(k)를 k의 해쉬값이라고 하고 h()를 해쉬 함수라고 한다. 이 경우, 값들은 동일한 hash값을 가질 수 있게 되고 충돌 문제가 일어날 수 있게 된다.

 

Chaining

이러한 충돌이 있을 경우, 대부분 중복되는 key가 있을 경우 해당 slot을 연결리스트로 저장하여 중복이 일어나더라도 충돌 문제가 일어나지 않도록 한다. 

하지만 이런 경우, 하나의 slot에 아주 긴 리스트가 생겨나서 시간 복잡도 측면에서 문제가 생길 수 있다. 그러니 가능하면 최대한 중복 값을 방지하고 해시값이 전체에 걸쳐서 균등하게 발생하도록 하는 해시 함수를 사용해야 한다.

 

대표적인 해시 함수는 나머지 값을 h(k)로 하는 것이다. 즉, key를 m이라는 수로 나누고 그 나머지로 h(k)의 결괏값을 만드는 것이다. 이때 보다 효율적이기 위해서는 m은 2의 제곱수가 아니어야 하고 소수로 지정하는 것이 좋다.

 

** key -> hash function -> hash value

즉, HashFunction( Key ) = HashValue 이다.

나눗셈 법의 경우 Hash Value = Key % m이다.

 

해시 함수는 언제나 동일한 해시값을 리턴한다. 이러한 해시는 보안 분야에서도 자주 사용된다. 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만으로는 그 키값을 온전히 복원하기 어렵기 때문이다. 또한 해시함수는 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있기 때문에 데이터 축약의 기능도 있다.

 

Open Addressing

보다 균등하게 해시값들에 데이터를 저장하기 위해서, 해시값의 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 하여 보다 균일하게 분포되도록 하는 방법도 있다. 해당 방법은 만약 해당 해시값으로 이미 저장된 데이터가 있다면, 그다음 해시값으로 변경하여 데이터를 저장하는 것이다.

 

7이 m이라고 할 때, 50과 85의 해시값은 모두 1이다. 하지만 이미 50이 저장된 상태이므로 85의 해시값을 그보다 1이 큰 곳에 저장한다. 데이터가 균일하게 분포되지만 그 구조상 해시 충돌 문제가 발생할 수 있다.

 

Double Hashing

이중 해싱은 탐사할 해시값의 규칙성을 제거하여 clustering을 방지한다. 2개의 해시함수를 사용한다. 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시 충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용한다. 만약 최초 해시값이 같더라도 탐사 이동폭이 달라진다. 마찬가지로 탐사 이동폭이 같더라도 최초 해시값이 달라져서 primary, secondary clustering을 모두 완화할 수 있다.

 

 

예시로, 해당 방법에서 h1()은 m1, h2()는 m2를 사용한다고 하자

 

m1와 m2는 서로소이어야만 한다.

( 서로소 realatively prime - 3, 5처럼 공약수가 1 뿐인 경우 )

 

최초의 해시값을 h1으로 얻으면 ( h1의 제수, m1은 3이다 )

키가 3일 경우 h1(3) = 0

키가 6일 경우 h1(6) = 0

키가 11일 경우 h1(11) = 2

 

해시 충돌이 일어나서 h2를 사용하면 ( h2의 제수, m2은 5이다 )

h2(3) = 3

h2(6) = 1

h2(11) = 1

 

이처럼, 두 해시값이 다르기 때문에 clustering을 완화할 수 있다.

 

이번 예시는나눗셈 법, division method를 사용하였다. 간단하면서도 빠른 연산이 가능하다.

 

 

 

나눗셈 법 이외에도 다양한 해시 함수 방법이 있다.

 

multiplication method

숫자 key k이고  A는 0과 1 사이의 실수이다. 이때 m은 그 값이 크게 중요하지 않지만 보통 2의 제곱수로 한다. 나눗셈 법에 비해서는 느리지만 2진수 연산에 최적화된 컴퓨터 구조를 고려한 해시함수이다.

Universal Hashing

다수의 해시함수를 만들고, 해시함수들의 집합 H에서 무작위로 해시함수를 선택하여 해시값을 만든다. H에서 무작위로 뽑은 해시함수가 주어졌을 때 임의의 키값을 임의의 해시값에 매핑할 확률을 1/m으로 만드는 것을 목적으로 한다.

 

• 해시 테이블의 크기 m을 소수로 정한다.
• 키값을 k0부터 kr까지 총 r+1개로 쪼갠다.
• 0부터 m-1 사이의 정수 가운데 하나를 무작위로 뽑는다. (r+1)만큼 반복해서 뽑으며 a = [a0, a1, ... , ar]로 저장한다.
• 해시 함수는 다음과 같다.

 

• a와 해시함수의 집합 H의 요소 수는 다음과 같다.