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

Transcription

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

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

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

4 저장 / 검색의복잡도 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 -

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

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

7 크기 13 인 Hash Table 에 5 개의원소가저장된예 입력 : 25, 13, 16, 15, Hash function h(x) = x mod

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

9 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 -

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

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

12 Collision 의예 입력 : 25, 13, 16, 15, h(29) = 29 mod 13 = 3 29 를삽입하려하자이미다른원소가차지하고있다! Hash function h(x) = x mod

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

14 Chaining 을이용한 Collision Resolution 의예

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

16 Linear Probing h i (x) = (h(x) + i) mod m 예 : 입력순서 25, 13, 16, 15, 7, 28, 31, 20, 1, h i (x) = (h(x) + i) mod

17 Linear Probing 은 Primary Clustering 에취약하다 Primary clustering: 특정영역에원소가몰리는현상 Primary clustering 의예

18 Quadratic Probing h i (x) = (h(x) + c 1 i 2 + c 2 i) mod m 예 : 입력순서 15, 18, 43, 37, 45, h i (x) = (h(x) + i 2 ) mod

19 Quadratic Probing 은 Secondary Clustering 에취약하다 Secondary clustering: 여러개의원소가동일한초기해시함수값을갖는현상 Secondary clustering 의예

20 Double Hashing h i (x) = (h(x) + if(x)) mod m 예 : 입력순서 15, 19, 28, 41, h 0 (15) = h 0 (28) = h 0 (41) = h 0 (67) = h 1 (67) = 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

21 삭제시조심할것 DELETED (a) 원소 1 삭제 (b) 38 검색, 문제발생 (c) 표식을해두면문제없다

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

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

24 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- α)) 이다

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

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

27 Thank you