해시 (Hash)

1. 해시 (Hash)

• 해시 함수 (Hash Function) : 효율적인 데이터 관리를 위해 임의의 길이를 가지고 있는 데이터를 고정된 길이의 데이터로 매핑 (Mapping) 하는 함수
• 키 (Key) : 매핑 전 원래 데이터의 값
• 해시 값 (Hash Value) : 매핑 후의 데이터 값
• 해싱 (Hashing) : 매핑하는 과정 자체

특징

• 해시 함수는 언제나 동일한 해시 값을 반환하고, 해당 인덱스만 알면 해시 테이블의 크기에 상관없이 데이터에 빠르게 접근할 수 있으며, 인덱스는 간단한 함수 (상수 시간) 로 계산되기 때문에 매우 효율적이다.
  • 결국, 해시는 데이터 액세스 (삽입, 삭제, 탐색) 시 계산 복잡도가 \(O(1)\) 이 되도록 한다.
• 해시 함수는 원래의 문장을 복호화 할 수 없게 뭉개버린다는 장점도 있다.
• 키 값과 해시 값 사이에 선형적 관계가 없기 때문에, 해시 값만 가지고는 키 값을 온전히 복원하기 어려워 해시를 보안분야에서도 많이 사용한다.
• 또한, 해시 함수는 길이가 서로 다른 Input 데이터에 대해 일정한 길이의 Output을 만들 수 있어 '데이터 축약' 기능도 수행할 수 있다.

 

2. 해시 테이블 (Hash table)

• 해시 함수를 사용하여 키를 해시 값으로 매핑하고, 이 해시 값을 인덱스 혹은 주소로 삼아 데이터의 값을 키와 함께 저장하는 자료구조
• 해시 충돌 (Hash Collision) 이 발생할 가능성이 있음에도 불구하고 해시 테이블을 사용하는 이유는 적은 리소스로 많은 데이터를 효과적으로 관리하기 위함이다.
  • 예컨대, 해시 함수로 하드 디스크나 클라우드에 존재하는 무한에 가까운 데이터 (Key) 를 유한한 개수의 해시 값으로 매핑하여 작은 크기의 캐시 메모리 (Cache Memory) 로도 프로세스를 관리할 수 있게 된다.
  • 이 때, 데이터가 저장되는 곳을 버킷 (Bucket) 또는 슬롯 (Slot) 이라고 한다.

• 각 버킷에는 아래 표와 같이 데이터가 저장된다.

인덱스 (해시 값)	데이터
01	(John Smith, 521-1234)
02	(Lisa Smith, 521-8976)
...	...
14	(Sandra Dee, 521-9655)

 

2-1. Directed-address Table

• 전체 키의 개수와 동일한 크기의 버킷을 가진 해시 테이블

특징

• 키의 개수와 해시 테이블의 크기가 동일하기 때문에 해시 충돌이 발생하지 않는다.
• 전체 키 개수가 실제 사용하는 키보다 훨씬 많은 경우, 사용하지 않는 키들을 위한 공간 까지 마련해야 하기 때문에 메모리 효율성이 크게 떨어진다.
  • 위의 예시의 경우, 0 1 4 6 7 9의 버킷이 낭비되는 것이다.
• 보통, Directed-address Table 보다는 "실제 사용하는 Key 개수 \((n)\) 보다 적은, 크기가 \(m\) 인 해시 테이블" 을 운용한다.
  • 그 이유는 다뤄야할 데이터가 많고, 메모리 등의 리소스 문제가 생기기 때문이다.
  • 이 때, \(n \, / \, m\) 을 Load Factor \((\alpha)\) 라고 하며, 해시 테이블의 한 버킷에 평균 몇 개의 키가 매핑되는지를 나타내는 지표이다.
• Directed-address Table의 Load Factor는 1 이하이며, 1 보다 클 경우 해시 충돌이 발생할 수 있다.

 

3. 해시 충돌 (Hash Collision)

• 해시 함수에서 보통 해시 값보다 더 많은 개수의 키 값을 해시 값으로 변환 (Many-to-One 대응) 하기 때문에, 서로 다른 두 개의 키에 대해 동일한 해시 값을 내는 해시 충돌이 발생한다.
  • 아래의 그림은 John Smith, Sandra Dee 의 키 값들이 해시 함수를 통해 동일한 해시 값을 산출하여 충돌이 생긴 예시이다.

 

3-1. 체이닝 (Chaining)

• 해시 충돌을 해결하기 위한 방법 중 하나이며, 하나의 버킷당 들어갈 수 있는 엔트리 (Entry) 의 수에 제한을 두지 않음으로써 모든 데이터를 해시 테이블에 담는 방법이다.
  • 해당 버킷에 데이터가 이미 존재한다면, 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식 (LinkedList) 으로 구현한다.
  • 해시 테이블의 크기를 유연하게 만드는 장점이 있지만, 메모리 문제를 야기 할 수 있다.

• 위의 예시에서 해시 함수를 통해 John Smith와 Sandra Dee는 동일한 해시 값 (152) 을 매핑하였다.
  • 이 경우, 해당 해시 값에 대응하는 동일한 버킷에 두 개의 데이터를 저장한다.
  • 위 그림처럼 LinkedList로 저장할 경우, 최근 데이터는 LinkedList의 head에 추가된다.

 

3-2. 개방 주소 지정 / 폐쇄 해싱 (Open Addressing)

• 체이닝과 달리, 하나의 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시 테이블이다.
  • 해시 함수를 통해 얻은 주소가 아닌 다른 주소에 저장할 수 있다.
  • 메모리 문제를 야기시키진 않으나, 해시 충돌이 발생할 수 있다.

• 해시 함수를 '키 값을 7로 나눈 나머지'로 정의하고 50, 700, 76, 85, 92, 73, 101 순으로 데이터를 저장한다고 해보자.
  • 위의 예시 중 85를 봤을 때, 이를 7로 나누면 나머지는 1이다.
    • 하지만, 해시 값이 1인 버킷은 이미 50인 데이터가 존재한다.
  • 따라서, 그 다음 버킷인 2에 저장한다.
  • 다음 값인 92를 7로 나눈 나머지 또한 1인데, 해시 값이 1인 버킷은 50이 있고, 그 다음 해시 값이 2인 버킷은 85가 들어있다.
    • 따라서, 버킷 3 에 92를 저장한다.
  • 73, 101도 역시 버킷에 데이터가 있으므로, 그 다음으로 비어 있는 버킷에 할당한다.

 

3-3. 탐사 (Probing)

• Open Addressing은 구조 상 해시 충돌 문제가 발생할 수 있다.
  • 위의 예시처럼 특정 해시 값에 키 값이 몰리게 되면 효율성이 크게 떨어진다.
• 이러한 문제를 해결하기 위해 탐사 (Probing) 방법을 사용한다.
  • 탐사란 삽입 (Insert), 삭제 (Remove), 탐색 (Search) 를 수행하기 위해, 해시 테이블 내 새로운 주소 (해시 값) 를 찾는 과정이다.

 

3-3-1. 선형 탐사 (Linear Probing)

• 앞선 예시에 나온 것이며, 가장 간단한 방법이다.
  • 최초 해시 값에 데이터가 존재한다면, 해당 해시 값에서 고정된 폭 (ex. 1칸) 을 옮긴 다음, 그 해시 값에 해당하는 버킷에 액세스 (삽입, 삭제, 탐색) 한다.
  • 하지만, 이동폭이 고정되어 있기 때문에 특정 해시 값 주변 버킷이 모두 채워져 있는 Primary Clustering 문제에 취약하다.
• 아래 그림처럼 52 ~ 56에 데이터가 저장되어 있고, 임의의 키의 최초 해시 값이 52라면 탐사를 4번 수행해야 한다.

 

3-3-2. 제곱 탐사 (Quadratic Probing)

• 고정 폭으로 이동하는 선형 탐사와 달리, 폭이 제곱 수로 늘어난다.
  • 예를 들어, 임의의 키 값에 해당하는 데이터에 액세스 할 때 해시 충돌이 발생한다면 1의 제곱 칸을 옮긴다.
  • 만약 충돌이 또 발생한다면, 2의 제곱, 3의 제곱 칸으로 옮기는 방식이다.
• 제곱 탐사의 단점은 서로 다른 여러 개의 키가 동일한 초기 키 값 (Initial Probing) 을 갖는 Secondary Clustering에 취약하다.
  • 초기 해시 값이 같으면 다음 탐사 위치 또한 동일하기 때문에 효율성이 떨어진다.
• 아래 그림과 같은 경우, 초기 해시 값이 7인 데이터를 삽입해야 할 경우, 선형 탐사 보다 큰 폭으로 이동하더라도 탐사를 네 번 하고 난 뒤에 비로소 데이터를 저장할 수 있다.

 

3-3-3. 이중 해싱 (Double Hashing)

• 탐사할 해시 값의 규칙성을 제거하여, Clustering을 방지하는 기법이다.
  • 2개의 해시 함수를 준비한 후, 하나는 해시 값을 얻을 때 사용하고 나머지 하나는 해시 충돌이 발생할 경우 탐사 이동 폭을 얻기 위해 사용한다.
  • 이러한 경우 초기 해시 값이 동일하더라도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 초기 해시 값이 달라져 Primary / Secondary Clustering을 모두 완화할 수 있다.
• 예를 들면, 해시 값을 반환해주는 함수 \(H_{1}\) 을 '3으로 나눈 나머지', 탐사 이동폭을 반환해주는 함수 \(H_{2}\) 를 '5로 나눈 나머지'라고 하자.
  • 키 값이 각각 3, 6인 데이터의 초기 해시 값은 0으로 동일하다.
  • 하지만, 해시 값 3의 탐사 이동폭은 3, 6은 1로 달라진다.
  • 반대로 키 값이 각각 6, 11인 경우, 탐사 이동폭은 모두 1이지만, 데이터의 초기 해시 값은 각각 6은 0, 11은 2로 달라진다.
• 단, 제수 (위의 경우 3과 5) 는 서로소 이어야 원하는 효과를 볼 수 있다.

 

3-4. 해시 함수 (Hash Function)

• 해시 테이블의 크기가 \(m\) 일 때, 좋은 해시 함수는 임의의 키 값을 임의의 해시 값에 매핑할 확률이 \(1 \, / \, m\) 이 될 것이다.
  • 즉, 특정 값에 치우치지 않고 고르게 해시 값을 만들어내는 함수가 좋은 해시 함수라는 이야기이다.

 

3-4-1. Division Method

• 숫자로 된 키 값을 해시 테이블 크기 \(m\) 으로 나누고, 그 나머지를 해시 값으로 반환한다.
  • 보통 \(m\) 은 소수 (Prime Number) 를 사용하며, 특히, 2의 제곱수와 거리가 먼 소수를 사용하는 것이 좋다고 한다.
• 해시 함수의 특성 때문에 해시 테이블의 크기가 정해진다는 단점이 있다.

 

3-4-2. Multiplication Method

• 숫자로 된 키 값이 \(k\)이고 A는 0과 1사이의 실수일 때, 곱셈법은 아래와 같이 정의된다.
  • \(m\) 이 얼마든 중요하지 않으며, 보통 2의 제곱수로 정한다.
• 나눗셈범보다 조금 느리고 2진수 연산에 최적화된 컴퓨터 구조를 고려한 해시 함수라고 한다.

 

3-4-3. Universal Hashing

• 해시 함수를 여러 개 만들고, 이 해시 함수의 집합 \(H\) 에서 무작위로 해시 함수를 선택해 해시 값을 만드는 기법이다.
  • \(H\) 에서 무작위로 뽑은 해시 함수가 주어졌을 때, 임의의 키 값을 임의의 해시 값에 매핑할 확률을 \(1 \, / \, m\) 으로 만드는 것이 목적이다.
• 다음과 같은 특정 조건의 해시 함수 집합 \(H\) 는 \(1 \, / \, m\) 으로 만드는 것이 가능하다고 증명됐다.
  • 해시 테이블의 크기 \(m\) 을 소수로 정한다.
  • 키 값을 다음과 같이 \(r \, + \, 1\) 개로 쪼갠다 :  \(k_{0}, k_{1}, \ldots, k_{r}\)
  • 0부터 \(m - 1\) 사이 정수 가운데 하나를 무작위로 뽑는다.
    • 분리된 해시 값 개수만큼 반복해서 뽑는다.
  • 이를 \(a \, = \, [a_{0}, a_{1}, \ldots, a_{r}]\) 로 둔다. 따라서 \(a\) 의 경우의 수는 모두 \(m^{r+1}\) 가지이다.
  • 해시 함수를 다음과 같이 정의한다.
    • \(h_{a}(x) \, = \, \Sigma^{r}_{i=0}(a_{i}k_{i} \, mod \, m)\)
• 위와 같은 조건에서는 키 값이 동일하더라도 \(a\) 가 얼마든지 랜덤하게 달라질 수 있고, 이에 해당하는 해시 함수 \(h_{a}\) 또한 상이해지기 때문에 \(H\) 는 Universal 함수가 된다.

 

Reference

• https://namu.wiki/w/%ED%95%B4%EC%8B%9C
• https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/
• https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98
• https://en.wikipedia.org/wiki/Open_addressing
• https://en.wikipedia.org/wiki/Linear_probing
• https://en.wikipedia.org/wiki/Quadratic_probing
• https://en.wikipedia.org/wiki/Double_hashing
• https://en.wikipedia.org/wiki/Primary_clustering
• https://stackoverflow.com/questions/27742285/what-is-primary-and-secondary-clustering-in-hash