1. 해싱(hashing)

- 어떤 데이터셋을 앞으로 입력받아 메모리상에 저장해야 하는데, 그 데이터셋의 각 데이터가 길이가 일정하지 않을 것이라고 하자. 어떻게 저장해야 할까? 어떤 데이터가 들어올지 알 수 없으므로 각 길이마다 가능한 모든 형태의 데이터가 들어올 것이라고 가정하고 그에 해당하는 크기만큼의 메모리를 할당을 해두어야 할까? 이는 한 방법이 될 수 있지만, 지나치게 비효율적인 방법이다. 이때, 이보다 훨씬 적은 영역을 할당해두고 앞으로 들어올 데이터 값마다 그에 대응되는 그 영역 내 각 공간을 대응시키는 방법을 생각할 수 있다. 이는 앞의 방법보다 훨씬 메모리 공간을 효율적으로 사용한다. 이처럼 어떤 데이터셋을 그 데이터가 실제 가질 수 있는 값의 범위보다 훨씬 적은 영역에 할당하는 매핑 관계를 만드는 것을 해싱이라 하며, 해싱하기 전 원본 데이터를 키(key), 해시된 후 값을 해시값(hash value), 키와 해시값 사이에 지정된 매핑관계를 해시함수(hashfunction)라 한다.

- 해싱은 수많은 키값을 적은 수의 해시값에 매핑하기 때문에, 데이터가 계속 들어오다 보면 한 해시함수가 여러 개의 키값에 하나의 해시값을 대응시키는 충돌(collision) 문제가 반드시 일어나게 된다. 그러나 해시값의 범위를 충분히 넓게 잡도록 해시함수를 정해두면 충돌이 일어날 확률은 매우 낮은 반면, 메모리 공간을 활용하는 효율은 매우 높고, 키값을 해싱해 해시값을 얻는 시간은 상수시간 안에 가능한 등 많은 이점이 있어 현재 널리 쓰이고 있다.

2. 해시 테이블(hash table)

- 어떤 데이터셋의 각 데이터가 키값과 그 대응되는 어떤 데이터값의 쌍으로 이루어져 있을 때, 키값에 대응되는 해시값과 그 키값에 대응되는 데이터셋 내 원래 데이터값을 짝지어 저장하는 테이블을 해시 테이블이라 한다. 한 해시 테이블의 안에서 특정 해시값이 값에 대응되는 테이블 내 각 위치를 버킷(bucket)이라 하는데, 각 버킷은 하나 이상의 슬롯(slot)을 갖는다. 각 슬롯에는 원래의 데이터셋의 원본 키값과 짝을 지었던 데이터값 하나가 담긴다.

  • 각 버킷마다 슬롯이 하나뿐인 해시 테이블 유형도 있고, 둘 이상인 해시 테이블 유형도 있다.

- 입력으로 들어올 수 있는 키 개수(\(n\)) 대비 할당돼있는 해시값의 개수(\(m\)) 비율(\(m/n\))을 load factor라 하며, 이 값이 1 이하(\(n < m\))면 해시충돌 문제가 발생하지 않지만 1을 넘으면(\(n > m\)) 해시충돌 문제가 발생할 수 있다.

3. 해시 충돌 문제의 해결하는 해시 테이블 구성 방식

1) chaining

- 하나의 버킷마다 하나 이상의 슬롯으로 이루어진 연결 리스트를 두어, 충돌이 일어날 경우 슬롯을 늘려나가는 식으로 해시 테이블을 구성해 충돌 문제를 해결하는 방법.

  • 데이터 삽입의 시간복잡도: \(O(1)\)

  • 데이터 탐색의 시간복잡도: 총 \(n\)개의 데이터들이 \(m\)개의 해시값에 균등하게 할당돼 있음을 전제할 때 시간복잡도는 \(O(n/m)\)이다.

- C++의 hash_map, Java의 HashMap 같은 자료구조가 chaining 방식으로 구현돼 있다.

2) open addressing

- 하나의 버킷마다 슬롯을 하나만 두고, 충돌이 일어날 경우 현재 버킷의 바로 옆 버킷에 나중에 들어온 데이터를 저장하는 식으로 해시 테이블을 구성해 충돌 문제를 해결하는 방법.

- 어떤 영역의 버킷이 연달아 가득 차 있는 상황이 발생했을 때, 이 영역에 새 데이터를 추가한다든가 탐색한다든가 하는 연산을 해야 하는 경우에는 키값에 대응되는 해시값을 찾았다 해서 끝나는 게 아니라 원하는 버킷을 찾기 위해 거기서 추가로 탐사(probing)를 해야 한다. 탐사 방식에는 여러 가지가 있다.

  • linear probing: 충돌이 일어난 지점에서 원하는 버킷을 찾기 위해 이동할 때 일정한 간격으로 이동하는 방식. 이 방식은 아주 넓은 영역에 걸쳐 버킷이 모두 채워져 있는 경우(이를 primary clustering이라 한다)에는 매우 비효율적이다.

  • quadratic probing: 충돌이 일어난 지점에서 원하는 버킷을 찾기 위해 이동할 때 그 간격을 제곱수로 늘리며 이동하는 방식. 이 방식은 밀집도가 높긴 하지만 듬성듬성 빈 버킷이 있는 경우(이를 secondary clustering이라 한다)에는 비효율적이게 되는데, 빈 버킷이 있어도 이동 간격이 워낙 커 찾지 못하고 넘어가는 경우가 많기 때문이다.

  • double hashing: 충돌이 일어난 지점에서 원하는 버킷을 찾기 위해 이동할 때 그 간격을 얻기 위한 새로운 해시함수를 사용해 이로써 얻은 간격만큼 이동하는 방식. 서로 다른 키값에 첫 번째 해시함수를 적용하여 같은 버킷에 매핑되었다 하더라도, 거기서부터 자신의 진짜 버킷을 찾기 위한 두 번째 해시함수를 적용하면 결국 두 키값은 각각 다른 버킷으로 매핑되게 된다.

- open addressing은 버킷당 하나의 데이터만이 존재할 수 있기 때문에, chaining과 달리 입력으로 들어오는 키값의 수 \(n\)이 해시값의 수 \(m\)보다 적다고 가정한다. 만약 open addressing 방식으로 구성한 해시 테이블에 \(n\)이 \(m\)에 육박할 정도로 충분히 크다면, 그만큼 해시 테이블이 가득 차있어 탐사를 하는 횟수가 늘어날 것이다. 계산해보면, 탐사의 시간복잡도는 \(O(m/n)\)으로 계산된다.

  • 이처럼 해시 테이블에 매핑되는 키값의 수가 늘어날수록 탐사 시간이 늘어나는 구조이기 때문에, open addressing 방식으로 구성된 해시 테이블은 내용이 가득 찰수록 삽입, 삭제, 탐색에 걸리는 시간이 느려진다. 따라서 open addressing 방식으로 구성된 해시 테이블은 해시 테이블이 일정 비율 이상 찼을 때 해시 테이블의 크기를 늘려주어야 한다.

- Python의 dict 같은 자료구조가 open addressing 방식으로 구현돼 있다.

4. 해시함수

- 입력으로 들어오는 키값의 분포에 따라 그에 대응되는 해시값이 최대한 균등하게 분포돼야 해시 테이블에 충돌이 적게 일어날 것이므로, 해시값이 균등하게 분포되도록 하는 해시함수를 정하는 것이 중요하다. 해시함수를 정하는 여러 방식이 있다.

  • division method: 키값을 어떤 정수로 나눈 나머지를 해시값으로 하는 해시함수를 쓰는 방법.

  • multiplication method: 키값에 임의의 실수를 곱한 후 소수점 이하 부분만 남기고 여기에 2의 지수승을 곱하는 해시함수를 쓰는 방법.

5. universal hashing

- 키값의 분포가 균일하다면 division method만으로도 그에 대응되는 해시값 분포를 균일하게 할 수 있다. 그러나 division method의 경우 키값이 불균등한 경우에는 그에 대응되는 해시값 분포가 매우 편향될 수 있다는 단점이 있다. 따라서 키값의 분포에 무관하게 해시값 분포를 균일하게 갖는 해시함수를 찾을 수 있는지가 중요한 문제가 된다. universal hashing은 이처럼 키값의 분포에 무관하게 해시값 분포를 균일하게 갖는 해시함수를 찾기 위해 고안된 아이디어이다.

- universal hashing에서는 ‘해시함수 집합에서 임의로 어느 한 해시함수를 뽑아서 키값에 대응되는 해시값을 구한다’라고 문제를 바라보고 이때 해시값 분포를 균일하게 갖는 해시함수 집합을 찾을 수 있다고 본다. 즉, 임의의 해시함수를 원소로 갖는 해시함수 집합 \(H\)가 있고, 해시 테로블이 갖는 해시값 수의 최댓값이 \(m\)이라 하자. 어느 한 키값에 대한 해시값을 구할 때 \(H\)에서 임의로 해시함수 어느 하나를 선택해 해시값을 구하기로 한다고 하자. 이때 입력으로 들어오는 키값의 분포가 어떤 분포를 갖더라도 충돌이 발생할 확률을 \(1/m\) 이하로 할 수 있는 해시함수 집합 \(H\)를 찾을 수 있다고 본다.

  • 이를 만족하는 여러 해시함수 집합이 알려져 있으며, 다음은 그 중 한 사례이다.
\[H = \left\{ h_a \mid h_a(k) = \sum_{i=0}^{r-1} \left(a_i \cdot k_i \bmod m \right) \right\}\]

  • 여기서 \(a\)는 \(m^r\)보다 작은 음 아닌 정수 중 임의의 정수이며, \(a_i\)는 \(a\)를 \(m\)진법으로 표현한 수의 각 자릿수이다.

  • \(k_i\)는 \(k\)를 \(m\)진법으로 표현한 수의 각 자릿수이다.

6. 동적 해싱과 확장 해싱

1) 정적 해싱과 동적 해싱

- 처음에 해시 테이블의 크기를 정해놓은 다음에 데이터셋을 해시 테이블에 저장하는 방식을 정적 해싱이라 하며, 구현이 간단하다는 장점이 있으나 해시 테이블의 크기를 너무 작게 설정하면 충돌 빈도가 높고 해시 테이블의 크기를 너무 크게 설정하면 공간 낭비가 심하다는 단점이 있다. 처음엔 충돌 빈도가 낮더라도 점점 충돌 빈도가 증가하면 주기적으로 해시 테이블의 크기를 크게 키워야 할 필요가 있으며, 해시 테이블의 크기를 키우는 주기가 짧아지면 그만큼 오버헤드도 커진다는 단점이 있다. 싱 - 해시 테이블에 저장되는 데이터 값이 늘어나거나 줄어들 때마다 해시값이 갖는 범위를 늘리거나 줄이고 버킷의 개수를 늘리거나 줄이는 식으로 해시 테이블을 구성하는 방식을 동적 해싱이라 한다. 충돌 빈도가 너무 높아진다거나 해시 테이블 크기를 비효율적으로 설정한다든가 하는 단점은 극복했으나, 각 버킷 사이에 트리 같은 자료구조를 따로 사용해야 한다는 점, 구현이 복잡하다는 점, 버킷의 개수를 늘리거나 줄일 때마다 발생하는 오버헤드가 있다는 점, 버킷을 찾아갈 때 트리 탐색을 해야 한다는 점 같은 단점이 있다.

2) 확장 해싱

- 확장 해싱은 가장 많이 쓰이는 동적 해싱의 특수한 형태로, 키값을 연산한 연산 결과를 2진수로 표현한 후 끝 몇자리만을 해시값(이를 확장 해싱에서는 pseudo key라 한다)으로 하는 해시함수를 사용한다. pseudo key의 자릿수를 몇자리로 하는지는 해시 테이블에 값이 얼마나 채워져있는지에 따라 달라진다.

  • global depth: pseudo key의 자릿수.

  • local depth: 버킷의 크기(=버킷에 담기는 데이터의 개수). global depth보다 작거나 같다.

  • 디렉토리: 각 pseudo key에 대응되는 일종의 인덱스로, 각 pseudo key에 대응되는 버킷의 주솟값이 담겨 있다. global depth의 크기를 \(d\)라 할 때, 디렉토리의 크기는 \(2^d\)이다.

3) 확장 해싱에서 오버플로우를 처리하는 방법

- 확장 해싱에서 버킷 하나가 가득 차면 일단 그 버킷을 쪼개 새 버킷을 만드는데, 디렉토리에 그 새 버킷만을 가리킬 곳이 없다면 그때 global depth를 하나 늘리고 디렉토리 크기를 두 배로 늘린다.

  • 디렉토리 크기가 두 배로 늘어난 후, 새로 생긴 디렉토리 영역 중에 오버플로우로 인해 새로 만든 버킷을 가리킬 공간이 생겼다면 그 공간은 그 새로 만든 버킷을 가리키게 한다. 이때, 그 외 특별히 오버플로우가 일어난 버킷이 따로 없다면, 그 밖의 새로 생긴 디렉토리 영역들은 기존 디렉토리 영역이 가리키던 버킷을 같이 가리키게 한다.