CHAP 11: 해싱 2015. 11. 30 순천향대학교 하상호

해싱이란? 지금까지 배운 모든 탐색 방법들은 키값을 비교함으로써 탐색하고자 하는 항목에 접근 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)이라 부르며, 해시테이블을 이용한 탐색을 해싱(hashing) 해싱 용도: 심볼 테이블(컴파일러), 사전 등 해싱 알고리즘의 복잡도는?

해싱 개념 해시 함수(hash function)란 탐색키를 입력으로 받아 해시 주소(hash address)를 생성 해시 함수 매개변수는 키 값 해시 주소를 사용하여 해시 테이블(hash table)에 접근 해시 주소는 해시 테이블의 인덱스임 예를 들어 영어사전에서는 단어가 탐색키가 되고 이 단어를 해싱 함수를 이용하여 적절한 정수 i로 변환한 다음, 배열 요소 ht[i]에 단어의 정의를 저장하는 것이다. 

해시 테이블의 구조 해시테이블 ht는 M개의 버켓(bucket)으로 이루어지는 테이블로서 ht[0], ht[1], ...,ht[M-1]의 원소를 가진다. 하나의 버켓은 s개의 슬롯(slot)을 가질 수 있다. 충돌(collision) : 서로 다른 두 개의 탐색키 k1과 k2에 대하여 h(k1) = h(k2)인 경우 Key의 개수 >> 해시 테이블의 크기 이러한 충돌이 버켓에 할당된 슬롯 수보다 많이 발생하게 되면 버켓에 더 이상 항목을 저장할 수 없게 되는 오버플로우(overflow)가 발생 오버플로우를 해결하기 위한 방법이 반드시 필요

이상적인 해싱 탐색 키당 하나의 해시 테이블 공간이 할당 가능한 경우 (예) 학생들에 대한 정보를 해싱으로 저장, 탐색 학번을 탐색키로 생각하자. 학번은 5자리로 되어 있고 앞의 2개의 숫자가 학과를 나타내고 뒤의 3자리 숫자가 각 학과의 학생들의 번호 같은 학과 학생들만 저장된다고 가정하면 뒤의 3자리만 사용할 수 있다. 이 경우에는 어떤 학생의 학번이 01023이라면 이 학생의 인적사항은 해시테이블의 이름을 ht이라고 하면 ht[23]에 저장 학생 수 n, 해시 테이블 크기 m일 때, n < m인 경우 add(key, value) index ← hash_function(key) ht[index] = value search(key) index ←hash_function(key) return ht[index]

실제의 해싱 실제로는 해시 테이블의 크기가 제한되어 있으므로 하나의 탐색키당 해시테이블에서 하나의 공간을 할당할 수가 없다 학생 수 n, 해시 테이블 크기 m일 때, n >> m인 경우 해싱함수가 필요 h(k)= k mod M 충돌과 오버플로우 발생

실제의 해싱(cont.) 두 번째 예제: 탐색키는 알파벳으로 되어 있다고 가정 해시함수는 각 키의 첫 번째 문자를 숫자로 바꾼다. h("array")=1 h("binary")=2 … (입력데이터) (array, binary, bubble, file, digit, direct, zero, bucket)

해시함수 좋은 해시 함수의 조건 충돌이 적어야 한다. 해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포되어야 한다. 계산이 빨라야 한다.

해시함수 제산 함수(나머지 연산자 사용) 폴딩함수 h(k)=k mod M 해시 테이블의 크기 M은 주로 소수(prime number) 사용 폴딩함수 탐색 키가 해시 테이블보다 더 큰 정수일 경우 hash_index=(short)(key ^ (key>>16)) key: 32비트, 해시테이블 인덱스: 16비트 이동 폴딩(shift folding)과 경계 폴딩(boundary folding) 탐색 키를 여러 부분으로 나누어 더한다 탐색 키의 이웃한 부분을 거꾸로 더한다

해시함수(cont.) 중간제곱함수 비트추출함수 숫자 분석 방법 중간 제곱 함수는 탐색키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성한다. 비트추출함수 탐색키를 이진수로 표현하고, 임의의 위치의 k개의 비트를 해시 주소로 사용하는 것이다. 해시 테이블의 크기 M = 2k 탐색키의 일부 정보만을 이용하여 해시 주소 집중 현상 가능 숫자 분석 방법 키의 각각의 위치에 있는 숫자 중에서 편중되지 않는 수들을 해시 테이블의 크기에 적합한 만큼 조합하여 해시 주소로 사용 숫자로 구성된 키에서 각각의 위치 수의 특성을 미리 알고 있을 때 유용 Ex) 200212345에서, 입학년도를 의미하는 앞 4자리 수는 사용하지 않는다.

해시함수(cont.) int hash_function(char a[]) { int hash_val = 0; int i = 0;   int hash_function(char a[]) { int hash_val = 0; int i = 0; while (a[i] != ‘\0’) do hash_val = g*hash_val + a[i++]; // 보통 g=31 end while return hash_val; }

충돌해결책 충돌이란? 충돌해결책 2가지 방법 서로 다른 탐색 키를 갖는 항목들이 같은 해시 주소로 사상되는 경우 선형조사법(linear probing): 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장한다. 체이닝(chaining): 해시테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블의 구조를 변경한다.

선형조사법 충돌이 ht[k]에서 충돌이 발생했다면 ht[k+1]이 비어 있는지를 조사 이런 식으로 비어있는 공간이 나올 때까지 계속하는 조사하는 방법이다. 만약 테이블의 끝에 도달하게 되면 다시 테이블의 처음으로 간다. 만약 조사를 시작했던 곳으로 다시 되돌아오게 되면 테이블이 가득찬 것이 된다. 조사되는 위치 h(k), h(k)+1, h(k)+2,… (예) h(k)=k mod 7, 입력 파일: (8, 1, 9, 6, 13) 1단계 (8) : h(8) = 8 mod 7 = 1(저장) 2단계 (1) : h(1) = 1 mod 7 = 1(충돌발생)             (h(1)+1) mod 7 = 2(저장) 3단계 (9) : h(9) = 9 mod 7 = 2(충돌발생)             (h(9)+1) mod 7 = 3(저장) 4단계 (6) : h(6) = 6 mod 7 = 6(저장) 5단계 (13) : h(13) = 13 mod 7 = 6(충돌 발생)   1단계 2단계 3단계 4단계 5단계 [0] 13 [1] 8 [2] 1 [3] 9 [4] [5] [6] 6

알고리즘: 선형조사법 linearAdd(key: integer, ht: array of integers) { i, hval: integer hval <- h(key); i <- hval; while (ht[i] != null ) { // 충돌 발생되면 if (ht[i] = key) then print(“탐색키 중복”); return; i <- (i+1) mod sizeofHashTable; if (i = hval) then print(“테이블 꽉 참”); return; } ht[i] <- key; // 빈 버켓 발견 linearFind(key: integer, ht: array of integers) i, hval: integer; while (ht[i] != null) {

선형조사법: 평가 단순 키들이 집중/결합되어 저장되는 경향으로 탐색시간이 길어진다.

이차조사법 이차 조사법(quadratic probing)은 선형 조사법과 유사하지만, 다음 조사할 위치를 다음 식에 의하여 결정한다. (h(k)+i*i) mod M I = 0, 1, 2, …. M-1 M은 소수 따라서 조사되는 위치는 다음과 같이 된다. h(k), h(k)+1, h(k)+4,… 평가 선형 조사법에서의 문제점인 집중과 결합을 크게 완화 2차 집중문제 가능성 (동일한 위치로 사상될 경우, 같은 순서로 빈 버킷을 조사하기 때문)

이중해싱법 이중 해싱법(double hashing) 또는 재해싱(rehashing)은 오버플로우가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법이다. step=C-(k mod C), C는 M보다 약간 작은 소수, k는 키 값 h(k), h(k)+step, h(k)+2*step, … (예) 크기가 7인 해시테이블에서 첫 번째 해시 함수가 k mod M이고 오버플로우 발생시의 해시 함수 step=5-(k mod 5) 입력 파일 (8, 1, 9, 6, 13 )   1단계 2단계 3단계 4단계 5단계 [0] [1] 8 [2] 9 [3] 13 [4] [5] 1 [6] 6 1단계 (8) : h(8) = 8 mod 7 = 1(저장) 2단계 (1) : h(1) = 1 mod 7 = 1(충돌발생) (h(1)+h‘(1)) mod 7 = (1+5-(1 mod 5)) mod 7 = 5(저장) 3단계 (9) : h(9) = 9 mod 7 = 2(저장) 4단계 (6) : h(6) = 6 mod 7 = 6(저장) 5단계 (13) : h(13) = 13 mod 7 = 6(충돌 발생) (h(13)+h‘(13)) mod 7 = (6+5-(13 mod 5)) mod 7= 1(충돌발생) (h(13)+2*h‘(13)) mod 7 = (6+2*2) mod 7= 3(저장)

체이닝 체이닝(chaining)은 각 버켓이 한 개 이상의 값을 저장 가능하게 각 버켓에 고정된 슬롯을 할당하는 것이 아니라 각 버켓에, 삽입과 삭제가 용이한 연결 리스트를 할당한다. 버켓 내에서는 원하는 항목을 찾을 때는 연결 리스트를 순차 탐색한다. (예) 크기가 7인 해시테이블에 해시 함수: h(k)=k mod 7 입력 파일: (8, 1, 9, 6, 13) 1단계 (8) : ∙h(8) = 8 mod 7 = 1(저장) 2단계 (1) : ∙h(1) = 1 mod 7 = 1 (충돌발생->새로운 노드 생성 저장) 3단계 (9) : ∙h(9) = 9 mod 7 = 2(저장) 4단계 (6) : ∙h(6) = 6 mod 7 = 6(저장) 5단계 (13) :∙h(13) = 13 mod 7 = 6( 충돌 발생->새로운 노드 생성 저장)

알고리즘: 체이닝 (1) key: integer; link: nodeptr; nodeptr chainAdd(key: integer, ht: array of nodeptr) { nodeptr ptr, node, prev = null; int hval; // hash value hval = h(key); ptr = ht[hval]; while (ptr != null) { // 리스트의 끝을 찾는다 } node <- getNode(); // 한 개의 리스트 노드 생성 node.key <- key; node.link <- null; if (prev != null) prev.link <- node; else ht[hval] <- node;

알고리즘: 체이닝 (2) key: integer; link: nodeptr; nodeptr chainFind(key: integer, ht: array of nodeptr) { nodeptr ptr; int hval; // hash value hval = h(key); ptr = ht[hval]; while (ptr != null) { // 리스트로부터 key를 찾는다. } print(“Not found”);

해싱의 성능분석 적재 밀도(loading density) 또는 적재 비율(loading factor) 은 저장되는 항목의 개수 n과 해시 테이블의 크기 M의 비율이다. 탐색을 위한 비교 연산의 개수 선형 조사법 그림 11-18 참고 α>0.5이면 급격하게 탐색 시간 증가 체이닝 그림 11-19 참고 α가 증가하더라도 성능이 급격하게 떨어지지 않으나, 효율성을 위해서 낮게 유지하는 것이 필요

해싱의 성능분석(cont.) 평균 버켓 접근 수(Lum, Yuen, Dodd의 실험적 연구결과) 제산 해시 함수와 체이닝을 사용하는 것이 가장 효율적         적재밀도 해싱함수 .50 .70 .90 .95 해싱 함수 체인 선형조사 중간 제곱 1.26  1.73 1.40  9.75 1.45 37.14 1.47  37.53 제산 1.19  4.52 1.31  7.20 1.38 22.42 1.41  25.79 이동 폴딩 1.33 21.75 1.48 65.10 77.01 1.51 118.57 경계 폴딩 1.39 22.97 1.57 48.70 1.55 69.63  97.56 숫자 분석 1.35  4.55 1.49 30.62 1.52 89.20 125.59 이론적 1.25  1.50 1.37  2.50  5.50  10.50

해싱과 다른 탐색 방법의 비교