Chapter 8. Hashing

지환·2022년 5월 11일

8.1 INTRODUCTION

"dictionary"(ADT는 Chapter 5에)
DB의 index, spelling checker, compilers 등 여러 곳에서 이 dictionary가 쓰인다.

dictionary가 BST(binary search tree)로 구현됐다면 search, insert, delete 등의 작업은 O(n) 시간이 걸린다.
balanced BST라면 O(log n) 시간에 끝낼 수 있다.

우리는 이제 hashing이라 불리는 기술을 통해 위 작업이 O(1)에 끝나도록 한다.
(1)static hashing과 (2)dynamic hashing
둘로 나눠서 알아보자.

8.2 STATIC HASHING

8.2.1 Hash Tables

hash table 이라 불리는 table(ht)에 dictionary pairs을 저장한다.
hash table은 $b$ 개의 buckets으로 구성되며, 각 buckets는 $s$ 개의 slots으로 구성된다.
(ht[0], ht[1], ..., ht[b-1] 각각에 s개의 slots이 저장된다. 보통 s는 1)
(slot 1보다 크면, 뭐 포인터로 구현하든 알아서)
각 pairs의 address(location)은 hash function ( $h(k)$ )에 의해 결정된다.
$h(k)$ 는 $0$ ~ $(b-1)$ 의 값을 가져야하며, 이 값을 home address(or hash)라고 한다.

Definition
hash table의 key density 는, $n$ 이 table의 pairs 수이고 $T$ 가 possible key의 총 개수일때, $n/T$ 로 정의된다.
hash table의 loading density (or loading factor)인 $\alpha$ 는, $\alpha = n/(sb)$ 이다.(s는 slot size, b는 bucket size)
(위 두 density는 table이 채워짐에따라(n) 실시간으로 변동됨)
(T는 올 수 있는 모든 가능한 키의 경우의 수이다. 만약 알파벳 소문자 3자리가 키로 올 수 있도록 정의돼있다면, T는 26^3이다. 이에 반해 loading density는 실제 버킷의 크기를 반영하므로 우리가 생각하는 버킷의 밀도는 loading density를 보는 게 맞는 듯)

1) 이상적인 조건이라면 dictionary pairs은 home buckets에 저장된다. 그런데 그러기 위해서 버킷은 최소한 T만큼의 크기를 가져야 할 것이다.
2) 보통 가능한 key의 수인 $T$ 는 엄청나게 큰 경우가 많아서, 실제로 버킷의 크기인 b를 T만큼 만들긴 어렵다.
=> 따라서 다른 key $k_1$ , $k_2$ 가 같은 bucket을 가리킬 수도 있다.
이 경우 $k_1$ 과 $k_2$ 는 synonyms 라고 한다. ( $h(k_1) = h(k_2)$ )

synonyms으로 인해
bucket이 저장할 수 있는 pair를 넘치면 overflow라고 하고,
특정 pair를 특정 bucket에 저장하려는데 empty가 아니라면 collision이라고 한다.
(slot size가 1이라면 두개가 동시에 발생한다.)
(overflow 대응책은 8.2.3)

실제로 사용하려면 collision을 최소화하고 계산하기 쉬운 hash function을 골라야 한다.
물론 주로 $n/T$ 가 매우 작기 때문에 collisions을 완전히 피할 순 없다.(그래서 overflow 다루는 방법이 필요..)

이렇게 만든 hash table은 insert, search, delete 하는데 자료 개수에 상관없이 hash function 계산 시간에 따라 수행된다.
bucket내의 slot은 크기가 작기 때문에 뭐...

8.2.2 Hash Functions

hash function을 통해 key값이 hash table내의 buckect으로 mapping된다.
hash function은
1) 계산이 간단하고
2) collisions을 줄여야하며
3) 추가로, random key $k$ 에 대해 $f(k)$ 의 결과가 어떤 bucket으로 나올지 확률은 균등할수록 좋다.( $1/b$ 확률로 나오게)
(3을 만족하는 함수를 uniform hash function 이라고 한다.)

4개의 유명한 hash functions 알아보자.
(보통 arithmetic으로 진행되므로, arithmetic 가능하지 않은 type(ex. string)이라면 가능한 type(ex. int)로 바구는 것도 알아보자.)

8.2.2.1 Division

key가 0이 아닌 정수라면,
$h(k) = k\%D$
로 home bucket을 구한다.
(hash table에 최소 $D$ 개의 bucket이 있어야 한다.)

대부분 key space에선 어떤 $D$ 여도 $h$ 를 uniform hash function으로 만들지만,
주의해주면 좋은 사항들이 있다.
1. 2의 배수는 $D$ 로 사용하지 않는다.
: 실제 dictionary는 짝수나 홀수로 편향될 수 있는데, 2의 배수를 사용하면 hash function의 결과도 편향되게 나온다.
2. 작은 소수를 약수로 가지는 경우(prime factor)도 $D$ 로 사용하지 않는다.
: 2, 3, 5 같은 작은 prime factor를 약수로 가지면 편향된 결과를 가져올 수 있다고 밝혀졌다.( $D$ 의 최소 prime factor가 증가하면 bias도 줄어들었다.)
하지만, best performance를 위해서라면 $D$ 가 prime number여야한다. $D$ 의 가장 작은 prime factor는 $D$ 자신이다. 대부분의 경우, 20보다 작은 prime factor가 없다면 잘 기능(uniform distribution)했다.

사전 정보 없이 hash table과 function을 만들어야하면, 일단 홀수인 D로 만들고 table 개수도 D개가 되도록 한다.
그리고 더 늘려야하면 array doubling을 통해 늘린다.

8.2.2.2 Mid-Square

key를 제곱한 후, key의 중간에서 적절한 bits 몇개를 가져와 home buckey 주소로 사용한다.
높은 확률로 다른 key는 다른 주소를 산출한다.

bit몇개 가져올진 table 크기에 따라 다르다.
(mid-square에선 보통 table 크기는 2의 거듭제곱으로 한다.)

8.2.2.3 Folding

shift folding : key $k$ 를 하나를 여러 partition으로 분할한다.(마지막 부분 빼고 같은 길이, 마지막도 같을 순 있다.) 그렇게 나뉘어진 각 part를 모두 더한다.
ex) 12345678 : 123+456+78

folding at the boundaries : partition 경계에서 key값을 접는다고 생각하면 된다.
경계 너머의 숫자를 반대로 뒤집어서 더한다.
ex) 12345678 : 123+654+78

8.2.2.4 Digit Analysis

static file에 key가 있어서 table의 모든 key를 미리 알 수 있는 상황에 유용하다.

특정 radix $r$ 로 모든 digit을 분석한다.
가장 편향된 digits은 삭제
충분한 digits도 삭제 --> 남은 digits으로 hash table 범위의 address를 표현하기 충분할 정도로 작아질때까지..

8.2.2.5 Converting Keys to Integers

위 소개된 hash fucntions 사용하려면 nonnegative integers로 변환이 먼저 돼야한다.

어차피 위 함수들도 여러 key를 같은 home bucket으로 변환하기도 하니까, 굳이 숫자로 변환할때 unique하게 변환시킬 필욘 없다.

# 방법 1

unsigned int stringToInt(char *key) {
	int number = 0;
    while (*key)
    	number += *key++;
    return number;
}

# 방법 2

unsigned int stringToInt(char *key) {
	int number = 0;
    while (*key) {
    	number += *key++;
        if (*key) number+= ((int) *key++) << 8;
    }
    return number;
}

방법2는 방법1에 비해 더 큰 range를 결과로 반환한다.

8.2.3 Overflow Handling

overflow 다루는 두가지 유명한 방법
1) Open Addressing
2) Chaining

참고

8.2.3.1 Open Addressing

linear probing(linear open addressing)
quadratic probing
rehashing probing
random probing

이렇게 네가지정도의 open addressing methods가 있다.

linear probing

$ht[(h(k) + i)\%b],\ (0\leq i\leq b-1)$
위 식에서 $i$ 를 쭉 진행(바로 다음 장소를 찾아보는 것)하다가 처음으로 들어갈 수 있는 곳에 들어간다.
없다면, hash table이 꽉찼으므로 size를 늘려야한다.

실제론 꽉찼을때 늘리는게 아니라 loading density 기준(예를들어 0.75)을 정해두고 넘어섰을때 늘렸어야한다.
hash table을 늘려버리면 hash function도 수정해야한다. hash function이 수정되면 기존 값들도 remap돼야한다.

반대로, linear probing이 된 hash table에서 search 방법은 아래와 같다.
1) $h(k)$ 계산
2) $ht[h(k)]$ , $ht[(h(k) + 1)\%b]$ , ... 해서 나올때까지 찾는다.
(a) 저렇게 쭉 가다가 찾고자 하는 값을 찾았다면 찾은거다.
(b) $ht[h(k)+j]$ 가 비었다면, table에 찾고자 하는 값은 없다.
(c) 시작 지점인 $ht[h(k)]$ 로 돌아온다면, table은 꽉 찼고, 찾고자 하는 값은 table에 없다.

element* search(int k) {
	int homeBucket, currentBuncket;
    homeBuckey = h(k);
    for (currentBuckey = homeBuckey; ht[currentBucket] && ht[currentBuckey]->key != k;) {
    	currentBuckey = (currentBuckey + 1) % b;
        if (currentBuckey == homeBuckey)  //처음 위치로 돌아온 경우
        	return NULL;
    }
    if (ht[currentBuckey]->key == k)  //찾은 경우
    	return ht[currentBuckey];
    return NULL;  //못찾은 경우 == 여기 없음
}

linear probing을 이용해 overflow를 해결하면, key들은 모이는(cluster) 경향이 있다.
특정 값 기준으로 몰려있을때 취약하다.
Linear probing을 했을때 key를 찾기위한 comparison 평균 횟수는 대략 $(2-\alpha)/(2-2\alpha)$ 이다.
(책 p.404 Figure 8.4 예시에서 볼 수 있듯이, 위 수식으로 계산되는 평균은 1.36이지만, 실제 case는 41/11이 나온다. 즉 worst case는 평균이 작아도 나쁠 수 있다.)

clusters가 커지고 comparisons 횟수가 커지는건 quadratic probing으로 좀 개선될 수 있다.

quadratic probing

$h(k)$ , $(h(k)+i^2)\%b$ , $(h(k)-i^2)\%b$
이렇게 $1\leq i\leq (b-1)/2$ 의 범위에서 위 세 값으로 판단한다.
(linear probing과 다르게 $i$ 에 대한 quadratic(2차) function이 사용된다.)
(제곱 탐사는 선형 탐사와 달리 제곱된 값만큼 건너뛰며 빈칸을 찾는 셈이다.)

초기 hash 값이 같은 애들이 많은 경우 취약하다.
(값이 같으면 제곱하면서 뛰어다녀도 크게 의미가 없으니)

$b$ 값이 $4j+3$ (j는 integer) 형태의 prime number라면, quadratic search는 table의 모든 bucket을 조사한다.(이게 크게 무슨 의미를 가지는지는 모르겠네, 그냥 저런 수로 하면 다 조사하니가 좋단건가..)

rehashing

또 다른 cluster의 성장을 줄이는 방법으론, 연속된 여러 hash 함수를 쓰는 방법이 있다.
$h_1, h_2, ..., h_m$
이를 rehashing이라 한다.
(자리에 있으면 다음 hash function 써서 계산하고.. 이런 방식인듯)

random probing

말그대로 간단하게 랜덤값 이용해 조사하는 방식... 궁금하면 나중에 자세히 찾아보기

8.2.3.2 Chaining

위 방식들이 엄청 잘 수행되진 않는다(시간 꽤 걸릴 수 있음). 다른 값으로 비교하고 찾아야하기 때문이다.

key의 lists를 만든다면 시간을 많이 줄일 수 있다.
그럼 그냥 $h(k)$ 의 값을 기반으로 해당 list에서 원하는 값을 찾을 수 있다.
array나 search tree로도 구현가능하지만, chain(linked list)을 사용하자.
chain의 first node를 가리키는 포인터는 ht[] 배열에서 유지한다.

uniform hash function으로 만들어졌다면,
평균 comparison 횟수는 약 $1+\alpha/2$ 이다. (linear probing보다 확실히 작음)

Analysis

즉 바로 위 문장과 연결해서 본다면, uniform hash function만 사용된다면 overflow 다루는 방식에 따라 performance가 결정된다고 해석할 수 있다.
하지만 key가 random하다면 그렇지만, 실제론 그렇지 않다.
hash 함수에 따라서도 performance가 결정된다.(당연히 overflow 다루는 방식도 performance 결정)
대게는 division hash function + chaining이 제일 낫다.

comparisons의 worst case는 어떤 방식을 쓰든 O(n)이다.
balanced search tree(Chapter 10)을 사용해 synonym을 저장하면, worst case를 O(log n)으로 줄일 수 있다.

8.2.4 Theoretical Evaluation of Overflow Techniques

위에 linear probing이나 chaining할때 loading density 이용해서 평균 비교횟수를 구했는데,
저 식이 어떻게 나왔는지 증명하는 과정이다.
굳이 정리할 필욘 없을 것 같아서... 필요하면 책보기.. p.407

8.3 DYNAMIC HASHING

8.3.1 Motivation for Dynamic Hashing

미리 정한 loading density 넘어서면 table size 증가시켜야 --> good performance

hash table size가 증가하면, function도 수정해야하고, 기존 저장된 값들의 home buckey도 달라질 수 있으니 이것도 수정해야한다.
이런 rebuilding 과정에선 다른 operation은 중지된다.
그래서 항상 접근해야하는 큰 dictionary를 처리하기 곤란..

Dynamic Hashing (Extendible hashing)은 1개의 bucket만 추가함으로써 이런 rebuilding 과정을 줄인다.
dictionary 크기가 큰 경우 doubling하는데 시간이 꽤 걸린다. 어떤 operation을 하든 빨리 끝나야하는데 doubling을 유발한 insertion operation은 늦게 끝날 수 있다. 그래서 dynamic hashing으로 그 과정을 짧게 끝낸다.

directory를 사용하는 dynamic hashing
directory를 사용하지 않는 dynamic hashing

두가지로 나눠서 보자.

정의 (이 section 사용할 기호, hash function 등)

$h(k,p)$ 는 $k(k)$ 의 $p$ 개의 significant digit을 나타냄

key는 두 characters로 나타내고, 각 character는 0~7까지 숫자를 가져 3 bits로 표현된다.(아래는 key랑 해시함수값 예시 몇개)

$k$	$h(k)$
`A0`	`100 000`
`B1`	`101 001`
`C3`	`110 011`

8.3.2 Dynamic Hashing Using Directories

hash table이 추가 directory $d$ 를 사용한다. directory의 각 element는 대응하는 bucket을 가리킨다. (즉, $d$ 와 $b$ 는 별개로 봐야한다.)
$h(k,p)$ 에서 $p$ 값에 따라 $d$ 의 size가 결정된다, $2^t$ . (이 $t$ 를 directory depth라고 함)
아래 (a)를 보면 우선 A0, B0, A1, B1, C2, C3를 삽입한 것이다.

bucket size는 실제 물리적 저장 공간 특성과 관련해 결정된다.(만약 disk에 dictionary pairs이 저장되면, bucket은 disk track이나 sector와 대응)

$k$ 를 찾고싶으면 $d[h(k,t)]$ bucket만 보면 된다.

Rebuilding (Resizing)

특정 pair를 insert했는데 overflow가 발생한다면, overflowed bucket에서 $h(k,u)$ 를 적용했을때 모든 key가 같지 않도록 하는 최솟값 $u$ 를 찾는다. (쉽게말해 bits 보는 범위를 늘려서 값들이 겹치지(몰리지) 않게 한다.)
$u$ 에 맞게 size를 증가시킨다.
size가 doubling된다면 $d$ 값들(포인터들)은 마찬가지로 대응되는 위치에 일단 복제된다.(위 그림 참고/ (b)로 늘어날때 절반이 나머지 늘어난 절반으로 복사된다.)
이렇게 doubling 후, overflowed bucket에서만 $h(k,u)$ 값을 정확히 따져서 다른 값을 가지는 값에 대해 bucket을 새로 만들어 올바른 곳에 연결해준다.
(위에도 보면 (c) 그림에서 0000은 B0가 아니다. doubling할때마다 00으로 끝나는 애들은 모두 저 bucket을 가리키도록 했기때문에 어차피 $d[h(k,t)]$ 로 값을 찾을땐 전혀 상관없다.)

$u$ 가 현재 directory depth보다 작거나 같다면, 일단 복제된 포인터때문에 그곳이 꽉 차있는거다. 따라서 해당 bucket의 값들을 전부 원위치 시켜주면 된다.(size 변경 X)
(b) 그림에 A4를 넣는다면, $d[100]$ 위치에 가득 차있어서 일단 안된다. 그 위치의 A0와 B0를 directory depth에 따라 원위치인 $d[000]$ 만 가리키도록 한다. 이제 $d[100]$ 은 비었으니, A4가 들어있는 new bucket을 가리키도록 한다.

static hashing보다 확실히 resizing 시간이 적다.
해봤자 rehash하는 data는 몇개없고, bucket이 존재하는 disk엔 접근도 딱히 하지않는다.

8.3.3 Directoryless Dynamic Hashing (linear dynamic hashing)

ht라는 array만 쓰인다. 충분히 크게 잡아서 중간에 크기가 더 커질일은 없다고 가정.

$q$ 와 $r$ 을 사용해 active bucket을 추적한다. $0\leq q < 2^r$
0~ $2^r+q-1$ buckets이 항상 active.
각 active bucket은 chain의 시작점이다. 각 chain에는 overflow bucket이 연결된다.

$r$ 은 $h(k)$ 가 hash table에서 index하는데 사용하는 bits 개수이고,
$q$ 는 다음에 split될 bucket이다.
$0$ ~ $q-1$ , $2^r$ ~ $2^r+q-1$ 에 있는 bucket은 $h(k,r+1)$ 을 사용하고,
나머지 active bucket은 $h(k,r)$ 을 사용한다.
(쉽게말해 r을 기본 directory depth로 쓰는데, 앞쪽 q개랑 뒷쪽 q개는 r+1을 dirctory depth로 본다.)

<img src=

Search
$k$ 를 찾고자 한다면, $h(k,r)$ 을 우선 계산하고, 그 값이 $q$ 보다 작다면, $h(k,r+1)$ 로 가서 찾아봐야한다. 작지않다면 거기서 찾으면 되고.
$h(k,r)$ 을 계산한 것이기 때문에 $2^r$ 보다 큰 값이 나올 수는 없다.

Insert
위 search 방법대로 삽입하고자 하는 값이 있는지 확인한다.
없다면 그냥 넣으면 되는데, 넣었을때 overflow가 발생한다면?
$2^r+q$ bucket을 activate 시킴 (==제일 끝 bucket 추가로 activate 시킴)
$q$ 위치에 있던 chain은 $q$ ~ $2^r+q$ 사이로 reallocate시킨다.
그리고 $q$ 를 1 증가시키는데, $q$ 가 $2^r$ 과 같아졌다면 $r$ 을 1 증가시키고 $q$ 는 0으로 reset

참고

8.4 BLOOM FILTERS

8.4.1 An Application - Differential Files

(뭔 말인지 이해하는데 좀 오래걸림.. 하 잘 정리해놔야지)

indexed file을 관리한다고 생각해보자. 즉 이 데이터는 index와 file로 이루어져있다.
원본 file의 index와 file을 master index, master file이라고 각각 칭한다.(책엔 working copy라고 나오긴하는데 일단 원본이라고 이해.. 뭐 여기선 좀 비슷해서.. differential file 적용할땐 다른 의미긴함.)
작업을 하다가 여러가지 이유로 내용물이 날아갈 수 있다. 그 경우를 대비해 back up을 해둬야한다.
근데 문제는, backup을 하더라도 backup하고 나서 작업을 어느정도 진행하다가 failure이 발생하면 그 사이의 데이터는 복구하지 못하게 된다. ("A"까지 backup하고 "ABC"까지 작업했을때 중단되면 "BC"는 backup 데이터를 불러와도 복구가 안된다.)
그래서 backup 데이터가 만들어진 이후로 변경된 사항들(updates)만 저장하는 log가 필요하다. 이를 transaction log라고 한다.
그럼 이제 중간에 날아가도 backup data와 날아간 시점 사이까지의 transaction log를 통해 복구할 수 있다.
recovery time을 줄이기 위해 backup을 자주 해야한다. backup 데이터가 최근 것일수록 transtaction log를 통한 복구가 당연히 빠르기 때문이다.
하지만 master index나 master file이 크다면 자주 backup을 할 수 없다.

그래서 자주 backup하기 위해,,,
1) master file만 큰 경우에는 (index는 작고)
원본 file을 master file + differential file 로 유지한다.
differential file이란, master file에서 수정된 부분들만 따로 파일에 저장해두는 것이다.
master file은 초기 상태 그대로 두고, differential file만 고쳐가며 진행하는 것이다.
그렇게하면, differential file은 크기가 상대적으로 작으니 잦은 backup이 가능하다.
index는 크기가 작으니 그냥 master index가 수정사항 따라가며 진행된다.

2) master index도 큰 경우에는
differential index도 만들어서 위처럼 관리해주면 된다.
여기서 differential index를 사용하면, disk 접근 횟수가 많아지게 된다는 문제가 있다.
왜냐하면 searching 같은 작업을 할때 differential index와 master index를 모두 확인해봐야하기 때문이다.

그래서 우리는 bloom filter를 통해 이 값이 해당 집합에 존재하는지 확인한다.(이렇게 disk 접근 횟수를 줄여서 단점을 보완하는 것이다.)

8.4.2 Bloom Filter Design 은 생략

지환

이전 포스트

Chpater 7. Sorting

다음 포스트