쉽게배우는알고리즘 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) 최악의경우 Θ(log n) B-tree 최악의경우 Θ(log n) Balanced binary search tree 보다상수인자가작다 Hash table: 검색효율의극단 평균 Θ() - 4-2
Hash Table 원소가저장될자리가원소의값에의해결정되는자료구조 평균상수시간에삽입, 삭제, 검색 매우빠른응답을요하는응용에유용 예 : 긴급구조호출과호출번호관련정보검색 주민등록시스템 Hash table 은최소원소를찾는것과같은작업은지원하지않는다 - 5 - 주소계산 검색키 주소계산 배열모양의테이블 - 6-3
크기 3 인 Hash Table 에 5 개의원소가저장된예 입력 : 25, 3, 6, 5, 7 0 3 2 5 3 6 4 5 6 8 0 2 25 Hash function h(x) = x mod 3 적재율 (load factor) = 5/3-7 - Hash Function 해시함수의요구조건 입력원소가 hash table 에고루저장되어야한다. 서로다른원소가한주소에충돌할확률이작아지기때문 계산이간단해야한다. 여러가지방법이있으나가장대표적인것은 division method 와 multiplication method 이다 - 8-4
해시함수 Division Method h(x) = x mod m m: table 사이즈 대개 2 의멱수에가깝지않은소수가바람직 m = 2 p 라면입력원소의하위 p 비트에의해해시값이결정되는문제가있음 해시값은입력원소의모든비트를이용하는것이바람직 - - 해시함수 2 Multiplication Method 원리 먼저입력값을 0 과 사이의수로대응시키고 해시테이블크기 m 을곱하여 0 ~ m- 사이로팽창시킨다. 구현 x 에 A 를곱한다음소수부만취한다. 방금취한소수부에 m 을곱하여그정수부를취함 h(x) = m(xa mod ) A: 0 < A < 인상수 m 은굳이소수일필요없다. 따라서보통 2 p 으로잡는다 (p 는정수 ) 크누스는잘작동하는 A 값으로 ( 5-)/2 를제안 - 0-5
x 0 xa mod 0 Multiplication method 의작동예 - m: 65,536, A=0.68033887 - 원소,025,30 의해시값을구해보자. xa =,025,30 * 0.68033887 = 633,725.8767303 여기서소수부는.8767303 이고, 해시테이블크기 m 을곱하면 57,25.67 결국, 원소,025,30 의해시주소는 57,25 로결정됨. m (xa mod ) m- - - Collision Hash table 의한주소를놓고두개이상의원소가자리를다투는것 Hashing 을해서삽입하려했으나이미다른원소가자리를차지하고있는상황 Collision resolution 방법은크게두가지가있음 Chaining Open Addressing - 2-6
Collision 의예 입력 : 25, 3, 6, 5, 7 0 3 2 5 3 6 4 5 6 8 0 h(2) = 2 mod 3 = 3 2 를삽입하려하자이미다른원소가차지하고있다! 2 25 Hash function h(x) = x mod 3-3 - Collision Resolution Chaining 같은주소로 hashing 되는원소를모두하나의 linked list 로관리한다 해시테이블외에추가적인 linked list 필요 Open addressing Collision 이일어나더라도어떻게든주어진테이블공간에서해결한다 추가적인공간이필요하지않다 - 4-7
Chaining 을이용한 Collision Resolution 의예 0 3 3 40 2 3 4 5 6 7 8 0 2 4 3 42 43 44 70 86 47 74 76 55 효율을위해리스트에삽입시리스트맨앞에삽입함. 리스트순서는삽입역순임 원소삭제시에는리스트에서삭제하면됨 교재 203p. 알고리즘 6- 장점 : 적재율이 을넘어도사용할수있음 - 5 - Open Addressing 빈자리가생길때까지해시값을계속만들어냄 충돌이일어나도어떻게든주어진테이블공간에서해결한다. h 0 (x), h (x), h 2 (x), h 3 (x), 단점 : 모든원소가반드시자신의해시값과일치하는주소에저장된다는보장이없음 충돌시다음주소를결정하는세가지방법 선형조사 (Linear probing) 이차방정식조사 (Quadratic probing) 더블해싱 (Double hashing ) - 6-8
선형조사 (Linear Probing) h i (x) = (h(x) + i) mod m // 충돌이일어난바로뒷자리를본다는의미 예 : 입력순서 25, 3, 6, 5, 7, 28, 3, 20,, 38 0 3 0 3 0 3 2 5 2 5 2 5 3 6 3 6 3 6 4 28 4 28 4 28 5 5 3 5 3 6 6 6 38 8 8 20 8 20 0 0 0 h i (x) = (h(x) + i) mod 3 2 25 2 25 2 25-7 - Linear Probing 은 Primary Clustering 에취약하다 일차군집 (Primary clustering): 특정영역에원소가몰리는현상 0 2 5 3 6 4 28 5 3 6 44 7 8 0 37 2 Primary clustering의예 군집영역이커질수록해당군집영역으로해싱될가능성이커짐 군집이심하지않은영역에비해영역의크기가빨리커짐 그러다두개의군집된영역이붙으면영역이갑자기커지기도함. - 8 -
이차방정식조사 (Quadratic Probing) h i (x) = (h(x) + c i 2 + c 2 i) mod m 예 : 입력순서 5, 8, 43, 37, 45, 30 0 2 5 3 4 43 5 8 6 45 7 8 30 0 37 2 h(x), h(x)+, h(x)+4, h(x)+, 선형조사에서처럼특정영역에원소가몰려도그영역을빨리벗어날수있기를기대함. 단점 : 여러개의원소가같은초기해시값을갖게되면모두같은순서로조사할수밖에없음. h i (x) = (h(x) + i 2 ) mod 3 - - Quadratic Probing 은 Secondary Clustering 에취약하다 0 2 5 3 28 4 5 54 6 4 7 8 2 0 67 2 Secondary clustering: 여러개의원소가동일한초기해시함수값을갖는현상 Secondary clustering의예 h i (x) = (h(x) + i 2 ) mod 3 이라면 원소 28: 두번만에빈자리찾음 원소 4: 세번만에 원소 67: 네번만에 원소 54: 다섯번만에빈자리를찾음. 보폭은넓어지지만최초의해시값이같은원소들은이로인해이득을보지못함. - 20-0
더블해싱 (Double Hashing) h i (x) = (h(x) + if(x)) mod m 예 : 입력순서 5,, 28, 4, 67 h(x) = x mod 3 f(x) = (x mod ) + h i (x) = (h(x)+if(x)) mod 3 m : m 보다조금작은소수로잡는것이바람직 0 2 5 3 4 67 5 6 7 8 28 0 4 2 h 0 (5) = h 0 (28) = h 0 (4) = h 0 (67) = 2 // 첫해시함수값은모두 2 h (67) = (2 + *((67 mod )+)) mod 3 = 4 h (28) = (2 + *((28 mod )+)) mod 3 = h (4) = (2 + *((4 mod )+)) mod 3 = - 첫해시값이같더라도두번째해시값이같을확률은매우작아서로다른보폭으로점프 - 2 차군집문제발생안함 - 2 - 더블해싱에서두번째해시함수 f(x) f(x) 의특징 해시테이블크기 m 과서로소인값이어야바람직 만약 f(x) 와 m 이 보다큰최소공약수 d 를가진다면? x 의자리를찾기위해해시테이블전체중기껏해야 m/d 밖에보지못함. 권고 해시테이블크기 m 을소수로잡고, f(x) 의값이항상 m 보다작은자연수가되게하면이들이항상서로소가될수있음. - 22 -
선형조사를예를들면 : 삭제시조심할것 0 3 2 5 3 6 4 28 5 3 6 38 8 20 0 2 25 0 3 2 5 3 6 4 28 5 3 6 38 8 20 0 2 25 0 3 DELETED 2 5 3 6 4 28 5 3 6 38 8 20 0 2 25 (a) 원소 삭제 (b) 38 검색, 문제발생 (c) 표식을해두면문제없다 - 23 - Hash Table 에서의검색시간 적재율 (Load factor) α Hash table 전체에서얼마나원소가채워져있는지를나타내는수치 Hash table 에 n 개의원소가저장되어있다면 α = n/m 이다 Hash table 에서의검색효율은적재율과밀접한관련이있다. - 24-2
Chaning 에서의검색시간 정리 Chaining 을이용하는 hashing 에서 load factor 가 α 일때, 실패하는검색에서 probe 횟수의기대치는 α 이다 정리 2 Chaining 을이용하는 hashing 에서 load factor 가 α 일때, 성공하는검색에서 probe 횟수의기대치는 + α/2 + α/2n 이다. 증명 : 교재 23p 참조. - 25 - Open Addressing 에서의검색시간 Assumption (uniform hashing) Probe 순서 h 0 (x), h (x),, h m- (x) 가 0 부터 m- 사이의수로이루어진 permutation 을이루고, 모든 permutation 은같은확률로일어난다 정리 3 Load factor α=n/m 인 open addressing hashing 에서실패하는검색에서 probe 횟수의기대치는최대 /(- α ) 이다 정리 4 Load factor α=n/m 인 open addressing hashing 에서성공하는검색에서 probe 횟수의기대치는최대 (/ α) log(/(- α)) 이다 - 26-3
Load Factor 가우려스럽게높아지면 Load factor 가높아지면일반적으로 hash table 의효율이떨어짐 과도한적재율방지알고리즘 일반적으로, threshold 을미리설정해놓고적재율이이에이르면, Hash table 의크기를두배로늘인다음, hash table 에저장되어있는모든원소를다시 hashing 하여저장한다. - 27 - 생각해볼것 Load factor 가아주낮으면각 probing 방법들이차이가많이나는가? 성공적인검색과삽입의관계는? [ 정리 4] 의증명과도관계있음 - 28-4
Thank you - 2 - 한빛미디어 5