쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table

쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table http://academy.hanb.co.kr

6장. 해시테이블 테이블 Hash Table 사실을많이아는것보다는이론적틀이중요하고, 기억력보다는생각하는법이더중요하다. - 제임스왓슨 - 2 -

학습목표 해시테이블의발생동기를이해한다. 해시테이블의원리를이해한다. 해시함수설계원리를이해한다. 충돌해결방법들과이들의장단점을이해한다. 해시테이블의검색성능을분석할수있도록한다. - 3 -

저장 / 검색의복잡도 Array O(n) Binary search tree 최악의경우 Θ(n) 평균 Θ(logn) Balanced binary search tree(e.g. red-black tree) 최악의경우 Θ(logn) B-tree 최악의경우 Θ(logn) Balanced binary search tree 보다상수인자가작다 Hash table 평균 Θ(1) - 4 -

Hash Table 원소가저장될자리가원소의값에의해결정되는자료구조 평균상수시간에삽입, 삭제, 검색 매우빠른응답을요하는응용에유용 예 : 119 긴급구조호출과호출번호관련정보검색 주민등록시스템 Hash table 은최소원소를찾는것과같은작업은지원하지않는다 - 5 -

주소계산 검색키 주소계산 배열모양의테이블 - 6 -

크기 13 인 Hash Table 에 5 개의원소가저장된예 입력 : 25, 13, 16, 15, 7 0 13 1 2 15 3 16 4 5 6 7 7 8 9 10 11 12 25 Hash function h(x) = x mod 13-7 -

Hash Function 입력원소가 hash table 에고루저장되어야한다 계산이간단해야한다 여러가지방법이있으나가장대표적인것은 division method 와 multiplication method 이다 - 8 -

Division Method h(x) = x mod m m: table 사이즈. 대개 prime number 임. Multiplication Method h(x) = (xa mod 1) * m A: 0 < A < 1 인상수 m 은굳이소수일필요없다. 따라서보통 2 p 으로잡는다 (p 는정수 ) - 9 -

x 0 1 xa mod 1 0 1 m (xa mod 1) Multiplication method 의작동원리 - 10 - m-1

Collision Hash table 의한주소를놓고두개이상의원소가자리를다투는것 Hashing 을해서삽입하려하니이미다른원소가자리를차지하고있는상황 Collision resolution 방법은크게두가지가있다 Chaining Open Addressing - 11 -

Collision 의예 입력 : 25, 13, 16, 15, 7 0 13 1 2 15 3 16 4 5 6 7 7 8 9 10 11 h(29) = 29 mod 13 = 3 29 를삽입하려하자이미다른원소가차지하고있다! 12 25 Hash function h(x) = x mod 13-12 -

Collision Resolution Chaining 같은주소로 hashing 되는원소를모두하나의 linked list 로관리한다 추가적인 linked list 필요 Open addressing Collision 이일어나더라도어떻게든주어진테이블공간에서해결한다 추가적인공간이필요하지않다 - 13 -

Chaining 을이용한 Collision Resolution 의예 0 39 13 1 40 2 3 4 5 6 7 8 9 10 11 12 94 3 42 43 44 70 86 47 74 76 55-14 -

Open Addressing 빈자리가생길때까지해시값을계속만들어낸다 h 0 (x), h 1 (x), h 2 (x), h 3 (x), 중요한세가지방법 Linear probing Quadratic probing Double hashing - 15 -

Linear Probing h i (x) = (h(x) + i) mod m 예 : 입력순서 25, 13, 16, 15, 7, 28, 31, 20, 1, 38 0 13 0 13 0 13 1 1 1 1 2 15 2 15 2 15 3 16 3 16 3 16 4 28 4 28 4 28 5 5 31 5 31 6 6 6 38 7 7 7 7 7 7 8 8 20 8 20 9 9 9 10 10 10 11 11 11 h i (x) = (h(x) + i) mod 13 12 25 12 25 12 25-16 -

Linear Probing 은 Primary Clustering 에취약하다 Primary clustering: 특정영역에원소가몰리는현상 0 1 2 15 3 16 4 28 5 31 6 44 7 8 9 10 11 37 12 Primary clustering 의예 - 17 -

Quadratic Probing h i (x) = (h(x) + c 1 i 2 + c 2 i) mod m 예 : 입력순서 15, 18, 43, 37, 45, 30 0 1 2 15 3 4 43 5 18 6 45 7 8 30 9 10 11 37 12 h i (x) = (h(x) + i 2 ) mod 13-18 -

Quadratic Probing 은 Secondary Clustering 에취약하다 0 1 2 15 3 28 4 5 54 6 41 7 8 21 9 10 Secondary clustering: 여러개의원소가동일한초기해시함수값을갖는현상 Secondary clustering 의예 11 67 12-19 -

Double Hashing h i (x) = (h(x) + if(x)) mod m 예 : 입력순서 15, 19, 28, 41, 67 0 1 2 15 h 0 (15) = h 0 (28) = h 0 (41) = h 0 (67) = 2 3 4 67 h 1 (67) = 3 5 6 19 7 8 9 28 10 11 41 12 h 1 (28) = 8 h 1 (41) = 10 h(x) = x mod 13 f(x) = (x mod 11) + 1 h i (x) = (h(x)+if(x)) mod 13-20 -

삭제시조심할것 0 13 1 1 2 15 3 16 4 28 5 31 6 38 7 7 8 20 9 10 11 12 25 0 13 1 2 15 3 16 4 28 5 31 6 38 7 7 8 20 9 10 11 12 25 0 13 1 DELETED 2 15 3 16 4 28 5 31 6 38 7 7 8 20 9 10 11 12 25 (a) 원소 1 삭제 (b) 38 검색, 문제발생 (c) 표식을해두면문제없다 - 21 -

Hash Table 에서의검색시간 Load factor α Hash table 전체에서얼마나원소가차있는지를나타내는수치 Hash table 에 n 개의원소가저장되어있다면 α = n/m 이다 Hash table 에서의검색효율은 load factor 와밀접한관련이있다 - 22 -

Chaning 에서의검색시간 정리 1 Chaining 을이용하는 hashing 에서 load factor 가 α 일때, 실패하는검색에서 probe 횟수의기대치는 α 이다 정리 2 Chaining 을이용하는 hashing 에서 load factor 가 α 일때, 성공하는검색에서 probe 횟수의기대치는 1 + α/2 + α/2n 이다 - 23 -

Open Addressing 에서의검색시간 Assumption (uniform hashing) Probe 순서 h 0 (x), h 1 (x),, h m-1 (x) 가 0 부터 m-1 사이의수로이루어진 permutation 을이루고, 모든 permutation 은같은확률로일어난다 정리 3 Load factor α=n/m 인 open addressing hashing 에서실패하는검색에서 probe 횟수의기대치는최대 1/(1- α ) 이다 정리 4 Load factor α=n/m 인 open addressing hashing 에서성공하는검색에서 probe 횟수의기대치는최대 (1/ α) log(1/(1- α)) 이다 - 24 -

Load Factor 가우려스럽게높아지면 Load factor 가높아지면일반적으로 hash table 의효율이떨어진다 일반적으로, threshold 을미리설정해놓고 load factor 가이에이르면 Hash table 의크기를두배로늘인다음 hash table 에저장되어있는모든원소를다시 hashing 하여저장한다 - 25 -

생각해볼것 Load factor 가아주낮으면각조사방법들이차이가많이나는가? 성공적인검색과삽입의관계는? [ 정리 4] 의증명과도관계있음 - 26 -

Thank you - 27 -