Hash Tables

해시 테이블은 딕셔너리를 구현하는데 효과적이다.

해시 테이블에서 요소를 검색하는 기대 시간은 O(1)이지만, 최악의 경우 검색 시간은 O(n)이 될 수 있다.

 

해시 테이블은 가능한 모든 키에 대해 하나의 배열 위치를 할당하는 것이 불가능하거나 비효율적일 때 사용한다.

실제 저장되는 키의 개수가 가능한 키의 개수에 비해 작을 때 사용한다.

---

 Direct-Address Tables, Hash Tables

직접 주소 테이블은 동적 집합(Dynamic set)을 유지 관리 해야한다. 각 요소는 key를 가지며, 두 요소가 동일한 키를 가지지 않는다고 가정한다.

 

Dynamic Set은 원소를 입력, 삭제, 검색할 수 있는 컴퓨터 상에 구현된 집합이다.

동적 집합의 관련 연산

 

학생 30여명의 인적사항 기록을 위한 두가지 형태의 ID(출석번호와 주민등록번호)가 있다고 가정해보자.

이러한 ID를 데이터 검색을 위한 구분자 즉, key라고 부른다.

 

Direct addressing

학생을 (출석번호, 이름, 인적사항)으로 저장한다고 가정하자.

배열과 관련 연산을 통한 Dynamic set의 일반적인 구현이며, 출석번호를 배열의 index로 사용한다.

 

직접 주소 테이블은 T로 표현하며, 요소 x가 키 k를 가지면 T[k] 는 x를 가리키는 포인터를 저장한다.

이름이 김홍도인 학생이 출석번호가 3이라면, T[3]에는 김홍도를 가리키는 포인터가 저장될 것이다.

배열 index를 통한 Insertion, Deletion, Search는 각각 O(1)의 시간을 소요한다.

 

Hashing

학생을 (주민등록번호, 이름, 인적사항)으로 저장한다고 가정하자.

이때, 주민등록번호를 배열의 index로 사용하는 것은 곤란하다. 주민등록번호의 possible key space는 실제 인원에 비해 매우 큰 수이기 때문이다. 주민등록번호는 13자리인데, 이 13자리로 표현할 수 있는 key 숫자들은 너무 많은 것에 비해 학생 수는 30여명 밖에 안되는 것이다.

 

대신, 주민등록번호를 hash function에 입력하여 나온 결과값(hash value)을 배열의 인덱스처럼 사용한다.

이를 키 k가 슬롯 h(k)로 해싱 된다고 한다.

hash value는 h로 표현

 

hash vlaue는 실제인원 범위 내의 값이 되어야 하며, 이를 위해 hash function은 mod 연산을 사용한다.

해싱에서 해시값에 의해 addressing 되는 단위를 slot이라고 부른다. 슬롯은 통상 0, 1, ..., m-1까지로 넘버링한다.

 

사진에서 보이듯이 h(k2)와 h(k5)가 충돌(Collision)되었다. 두 개 이상의 키가 동일한 슬롯으로 해싱된 것이다.

슬롯은 하나의 데이터를 저장하는 단위 장소이기 때문에, 충돌은 해결되어야한다.

가능한 키의 수가 슬롯의 수보다 많을 때(|U| > m)충돌이 발생할 수 있다. 주어진 키의 수가 슬롯 수보다 많을 때(|K| > m)는 충돌이 반드시 발생한다.

 

Hash functions

위에서 해시 함수는 mod연산을 사용한다고 했다.

mod연산은 key를 m으로 나누는 것이다. h(k) = k mod m

mod연산을 사용하면 계산이 빠르며, 나눗셈 한 번으로 해시 값을 구할 수 있다. 하지만, 특정 값 m($2^p$)을 피해야한다는 단점이 존재한다.  m이 $2^p$인 경우, 해시 분포가 균일하지 않을 가능성이 많아진다.

 

컴퓨터에서 자연수 k는 이진수로 표현되는데, $m = 2^p$라면 이는 숫자의 하위 비트만 사용하게 된다.

예를 들어 k1=1101, k2= 0101 이고, m= 1000 이라면, 동일한 하위비트 101을 가진 k1과 k2는 동일한 해시 값을 가지게 된다.

이렇게 하위 비트만 사용하게 되면 충돌이 높아지는 문제가 생긴다. 따라서 $m = 2^p-1$의 값을 사용하는것이 좋다.

 

이러한 단점을 극복하기 위해 나눗셈 형태의 mod 연산 대신, multiplication 형태의 연산을 사용하기도 한다. mod보다 느리지만, m의 값이 특별히 중요하지 않다. 

w bits로 구성된 key와 w bits로 구성된 '임의로 선정된 s'를 곱하여, 2w bits로 구성된 곱셉 결과를 얻는다. 이중 가운데 부분을 선정하여 hash value로 선정한다.

 

예시를 들어보자면,

m = 8, w = 5, k = 21,  s = 13을 선택했다고 하자. (p = 3, w = $2^3$이기 때문)

21 × 13 을 곱한 273을 $2^5$(단어의 크기)로 나누면, 몫은 8, 나머지는 17이 나온다.

나머지 17을 이진수로 변환하면 10001이고, 여기서 가장 높은 p = 3개의 비트를 추출한다. → 100 = 4

따라서 최종 해시값은 h(k) = 4 가 된다.

---

 

Two Resolutions for Collison: 충돌 해결

Chaining

여러 개의 데이터가 하나의 슬롯으로 매핑될 때, 이들을 linked list로 연결하는 방법이다.

 

• Insertion: 삽입 시, 요소가 이미 리스트에 존재하지 않는다고 가정한다. 이미 삽입되었는지 확인하려면 추가적인 검색이 필요하다. 최악의 경우 실행 시간은 O(1) 이다.
• Search: 키 k를 가진 요소를 리스트에서 검색한다. 실행 시간은 체인의 길이에 비례한다.
• Deletion: 삭제할 요소에 대한 포인터가 주어지므로, 요소를 찾기 위한 추가 검색이 필요하지 않다. 리스트가 이중 연결 리스트 (doubly linked)인 경우 실행시간은 O(1)이지만, 리스트가 단일 연결 리스트 (singly linked)인 경우 검색 시간만큼 소요된다. (단일 연결 리스트에서 각 노드가 다음 노드에 대한 포인터만 가지는 구조이다. 따라서 특정 노드를 삭제하려면 이전 노드를 찾아야하기 땜누에 검색 시간이 소요된다.)

체이닝을 사용하는 해싱의 분석 기준은 부하율 $\alpha = n/m$ 이다.

n은 테이블에 저장된 요소의 개수를, m은 테이블 슬롯의 개수를, $\alpha$는 슬롯 당 평균 요소 개수를 나타낸다.

부하율이 1보다 크면 평균적으로 리스트 길이가 1보다 긴 것이고, 부하율이 1보다 작으면 평균적으로 리스트 길이가 1보다 짧은 것이다. 부하율이 1이라면, 평균적으로 리스트 길이가 정확히 1이다.

 

해싱에서의 검색 시간을 분석해보자.

체이닝 해싱에서 검색 연산의 시간 복잡도는 두 가지 요소로 구성된다. 해시 함수 계산 시간 O(1)과, 체인 내 요소 검색 시간이다. 체인 내 요소 검색 시간은 체인의 평균 길이에 비례하므로, $O(\alpha)$에 비례하는 것이다. 따라서 검색 연산의 시간 복잡도는 $\Theta(1+\alpha)$가 된다.

왜 $Theta$ 일까?

$Theta$ 표기는 평균 및 최악의 경우를 모두 포함하는 상한과 하한을 의미한다.

해시 함수가 이상적으로 작동하고 키가 균일하게 분배되면 $\alpha$는 상수로 유지될 수 있으므로, 전체 시간 복잡도가 $O(1)$이 된다.

그러나 최악의 경우, $\alpha$가 증가하면서 검색 시간이 $O(\alpha)$에 비례하게 된다.

따라서, 체이닝 해싱의 검색 시간은 일반적으로 $\Theta(1+\alpha)$로 표현된다.

---

Open Addressing

충돌 발생 시 체인을 사용하지 않고, 다른 슬롯에 데이터를 저장하는 방법이다.

초기 슬롯들의 값은 NIL로 초기화되어 있다. 데이터가 삽입됨에 따라, 슬롯들은 NIL 또는 key값을 가진다.

hash value를 구하고, 해당 슬롯에서 값을 확인하는 것을 probing이라고 한다.

• Insertion: 프로빙하면서 해당 위치의 값이 NIL이면 해당하는 key를 삽입한다.
• Serch: 프로빙의 연속이다. key를 hash function의 입력으로 하여 프로빙한 결과, 해당 슬롯이 key값을 가지면 프로빙은 성공한 것이다. 해당 슬롯이 NIL을 가지면 프로빙은 실패한 것이다. 해당 슬롯이 다른 key값을 가지면 계속하여 다른 슬롯을 원하는 값을 찾거나 NIL값을 찾을 때까지 프로빙한다. 이를 sequential probing 이라고 하는데, 해시 함수를 h(k)가 아닌 h(k, i)로 수정하여 프로빙하는 것이다. 주어진 key에 대해 h(k, 0)로 프로빙해보고, 해당 위치의 값이 원하는 key값이 아니면, h(k, 1)로 프로빙하고, 최대 h(k, m-1)이 될때까지 프로빙한다.
• Deletion: 삭제하기를 원하는 key를 포함한 슬롯에 NIL을 바로 삽입하면, 문제가 발생한다. k'를 찾기 위해 검색하는 동안에, k를 저장한 슬롯 j를 거쳐야만 하는 경우가 있다고 하자. 만일 k'를 검색하기 전에 k를 먼저 삭제하기 위해 해시 함수를 구하고, 슬롯 j에 NIL을 입력함으로써 k를 삭제한다면, 이후로는 k'를 검색할 수 없게 된다. 검색 도중 슬롯 j에서 NIL이 발견되면, 검색 실패로 판단하게 되며, k'가 테이블에 존재함에도 불구하고 더이상 검색을 진행하지 않게된다. 이러한 문제를 해결하기 위해서는 슬롯 j에 NIL을 입력하는 대신, Deletioin marking을 해둔다. 이후에 k'를 검색할 때, Deletion mark를 지나서 k'를 찾도록 절차를 마련할 수 있다. 또는 k''를 삽입하려면, Deletion mark된 슬롯에 삽입한다.

---

Three ways to make probing sequences

Linear probing

h(k, i) = (h'(k) +i) mod m

h'(k)와 i(중복횟수)를 더하여 해시값을 만든다. h'(k)를 시작으로 연속된 m개의 해시값을 만들게 된다.

이러한 프로빙 시퀀스는 데이터들이 연속적으로 몰리는 clustering을 구성하게 되면서 평균 실행시간 증가를 유발한다. (임의의 k를 m회 선택하면, m가지의 수열을 만들게 된다.)

 

Quadratic probing

h(k, i) = (h'(k) + c1・$i$ + c2・$i^2$) mod m

리니어 프로빙의 단점을 보완하기 위해 c2・$i^2$라는 term을 추가한 것인데, 이는 clustering을 완화시키지만, secondary clustering을 유발할 수 있다.

 

Double hashing

h(k, i) = (h1(k) + i・h2(k)) mod m

h1(k)와 h2(k) 두 개의 해시 함수 중 하나를 임의로 골라서 사용한다. (임의의 k를 m회 선택하면, $m^2$가지의 수열을 만들게 된다.)

---

Perfect Hashing

해싱은 key 집합이 정적일 때 최악의 경우에도 뛰어난 성능을 제공한다. 정적 키 집합이란, 테이블에 키를 저장한 후 키 집합이 변경되지 않는 경우다. 완벽 해싱은, 검색 연산이 O(1)의 시간을 갖는 것이다.

 

완벽 해싱을 구현하기 위해, two-level hashing을 사용한다.

이중 레벨 해싱이란, 두 단계로 나누어진 해싱 구조를 사용하면서 각 단계에서 보편 해싱(Universal Hashing)을 적용한다.

• 보편 해싱:  해싱 함수 h를 무작위로 선택하여 실제 저장될 키와 독립적으로 설정한다.
• 해시 함수는 h(k) = ((ak + b) mod p) mod m
• 1차 레벨: 체이닝 방식 해싱과 동일하다.
• 2차 레벨:  슬롯 j 마다 작은 2차 해시 테이블을 생성한다. a 와 b는 헤더에 주어져 있다.

정적 키를 가지므로, 2차 레벨에 충돌이 없는 매핑 가능한 고정적인 해시 함수 제공이 가능하다.

검색 연산은 1차 레벨과 2차 레벨을 수행하는 시간으로 나뉜다. 각각 O(1)의 시간을 갖는다.

---

** 대학교 수업을 듣고 이해한 부분을 최대한 풀어서 작성한 글입니다.

틀린 정보가 존재할 수 있으며, 언제나 피드백은 환영입니다. **