PowerPoint 프레젠테이션

Size: px

Start display at page:

Download "PowerPoint 프레젠테이션"

현진 가
5 years ago
Views:

1 제 6 장해시테이블

2 6.1 해시테이블 이진탐색트리의성능을개선한 AVL 트리와레드블랙트리의삽입과삭제연산의수행시간은각각 O(logN) 그렇다면 O(logN) 보다좋은성능을갖는자료구조는없을까?

4 [ 핵심아이디어 ] O(logN) 시간보다빠른연산을위해, 키와 1 차원리스트의인덱스의관계를이용하여키 ( 항목 ) 를저장한다. [ 그림 6-2] 키를그대로 1 차원리스트의인덱스로사용

5 그러나키를배열의인덱스로그대로사용하면메모리낭비가심해질수있음 [ 문제해결방안 ] 키를변환하여배열의인덱스로사용 키를간단한함수를사용해변환한값을배열의인덱스로이용하여항목을저장하는것을해싱 (Hashing) 이라고함 해싱에사용되는함수를해시함수 (Hash Function) 라하고, 해시함수가계산한값을해시값 (Hash value) 또는해시주소라고하며, 항목이해시값에따라저장되는배열을해시테이블 (Hash Table) 이라고함

6 해싱의전반적인개념 해시테이블 0 항목의키집합 k 해시함수 h(k) = i i 해시값 k M-1 M = 해시테이블크기

7 아무리우수한해시함수를사용하더라도 2 개이상의항목을해시테이블의동일한원소에저장하여야하는경우가발생 서로다른키들이동일한해시값을가질때충돌 (Collision) 발생 충돌

8 6.2 해시함수 가장이상적인해시함수는키들을균등하게 (Uniformly) 해시테이블의인덱스로변환하는함수 일반적으로키들은부여된의미나특성을가지므로키의가장앞부분또는뒤의몇자리등을취하여해시값으로사용하는방식의해시함수는많은충돌을야기시킴 균등하게변환한다는것은키들을해시테이블에랜덤하게흩어지도록저장하는것을뜻함 해시함수는키들을균등하게해시테이블의인덱스로변환하기위해의미가부여되어있는키를간단한계산을통해 뒤죽박죽 만든후해시테이블의크기에맞도록해시값을계산

9 아무리균등한결과를보장하는해시함수라도함수계산자체에긴시간이소요된다면해싱의장점인연산의신속성을상실하므로그가치를잃음

10 대표적인해시함수 중간제곱 (Mid-square) 함수 : 키를제곱한후, 적절한크기의중간부분을해시값으로사용 접기 (Folding) 함수 : 큰자릿수를갖는십진수를키로 사용하는경우, 몇자리씩일정하게끊어서만든숫자들의 합을이용해해시값을만든다. - 예를들어, 에대해서 = 를계산한후에해시테이블의크기가 3 이라면 에서 3 자리수만을해시값으로사용

11 곱셈 (Multiplicative) 함수 : 1보다작은실수 를키에곱하여얻은숫자의소수부분을테이블크기 M과곱한다. 이렇게나온값의정수부분을해시값으로사용 - h(key) = ((key* ) % 1) * M 이다. Knuth에의하면 = 이좋은성능을보인다. - 예를들면, 테이블크기 M = 127이고키가 인경우, x = , x 127 = 이므로 38을해시값으로사용

12 이러한해시함수들의공통점 : - 키의모든자리의숫자들이함수계산에참여함으로써계산결과에서는원래의키에부여된의미나특성을찾아볼수없게된다는점 - 계산결과에서해시테이블의크기에따라특정부분만을해시값으로활용한다는점 가장널리사용되는해시함수 : 나눗셈 (Division) 함수 - 나눗셈함수는키를소수 (Prime) M 으로나눈뒤, 그나머지를해시값으로사용 - h(key) = key % M 이고, 따라서해시테이블의인덱스는 0 에서 M-1 이됨 - 여기서제수로소수를사용하는이유는나눗셈연산을했을때, 소수가키들을균등하게인덱스로변환시키는성질을갖기때문

13 6.3 개방주소방식 개방주소방식 (Open Addressing) 은해시테이블전체를열린공간으로가정하고충돌된키를일정한방식에따라서찾아낸 empty 원소에저장 대표적인개방주소방식 : 선형조사 (Linear Probing) 이차조사 (Quadratic Probing) 랜덤조사 (Random Probing) 이중해싱 (Double Hashing)

14 6.3.1 선형조사 선형조사는충돌이일어난원소에서부터순차적으로검색하여처음발견한 empty 원소에충돌이일어난키를저장 h(key) = i라면, 해시테이블 a[i], a[i+1], a[i+2],, a[i+j] 를차례로검색하여처음으로찾아낸 empty 원소에 key를저장 해시테이블은 1차원리스트이므로, i + j가 M이되면 a[0] 을검색 (h(key) + j) % M, j = 0, 1, 2, 3,

15 선형조사방식의키저장과정

16 선형조사는순차탐색으로 empty 원소를찾아충돌된키를저장하므로해시테이블의키들이빈틈없이뭉쳐지는현상이발생 [1 차군집화 (Primary Clustering)] 이러한군집화는탐색, 삽입, 삭제연산시군집된키들을순차적으로방문해야하는문제점을야기 군집화는해시테이블에 empty 원소수가적을수록더심화되며해시성능을극단적으로저하시킴

19 [ 프로그램 6-1] linear_prob.py

20 [ 프로그램 6-2] main.py

21 6.3.2 이차조사 이차조사 (Quadratic Probing) 는선형조사와근본적으로동일한충돌해결방법 충돌후배열 a 에서 (h(key) + j 2 ) % M, j = 0, 1, 2, 3, 으로선형조사보다더멀리떨어진곳에서 empty 원소를찾음

22 이차조사방식의키저장과정

23 이차조사는이웃하는빈곳이채워져만들어지는 1차군집화문제를해결하지만, 같은해시값을갖는서로다른키들인동의어 (Synonym) 들이똑같은점프시퀀스 (Jump Sequence) 를따라 empty 원소를찾아저장하므로결국또다른형태의군집화인 2차군집화 (Secondary Clustering) 를야기 점프크기가제곱만큼씩커지므로배열에 empty 원소가있는데도 empty 원소를건너뛰어탐색에실패하는경우도피할수없음

26 [ 프로그램 6-3] quad_prob.py

27 [ 프로그램 6-4] main.py

28 6.3.3 랜덤조사 랜덤조사 (Random Probing) 는선형조사와이차조사의규칙적인점프시퀀스와는달리점프시퀀스를무작위화하여 empty 원소를찾는충돌해결방법 랜덤조사는의사난수생성기를사용하여다음위치를찾음 랜덤조사방식도동의어들이똑같은점프시퀀스에따라 empty 원소를찾아키를저장하게되고, 이때문 3차군집화 (Tertiary Clustering) 가발생

30 random.seed(1000) 에서초기값 1000 은임의로정한것 random.randint(1, 99) 는 1 에서 99 사이에서난수를생성

31 6.3.4 이중해싱 이중해싱 (Double Hashing) 은 2 개의해시함수를사용 하나는기본적인해시함수h(key) 로키를해시테이블의인덱스로변환하고, 제2의함수 d(key) 는충돌발생시다음위치를위한점프크기를다음의규칙에따라정함 (h(key) + j d (key)) mod M, j = 0, 1, 2, 이중해싱은동의어들이저마다제 2 해시함수를갖기 때문에점프시퀀스가일정하지않음 따라서이중해싱은모든군집화문제를해결

32 제 2 의함수 d(key) 는점프크기를정하는함수이므로 0 을리턴해선안됨 그외의조건으로 d(key) 의값과해시테이블의크기 M 과서로소 (Relatively Prime) 관계일때좋은성능을보임 하지만해시테이블크기 M 을소수로선택하면, 이제약조건을만족

33 h(key) = key % 13 과 d(key) = 7-(key % 7) 에따라, 25, 37, 18, 55, 22, 35, 50, 63 을해시테이블에차례로저장하는과정

37 이중해싱의장점 이중해싱은빈곳을찾기위한점프시퀀스가일정하지않으며, 모든군집화현상을발생시키지않는다. 또한해시성능을저하시키지않는동시에해시테이블에많은키들을저장할수있다는장점을가지고있다.

38 6.4 폐쇄주소방식 폐쇄주소방식 (Closed Addressing) 의충돌해결방법은키에대한해시값에대응되는곳에만키를저장 충돌이발생한키들은한위치에모여저장 이를구현하는가장대표적인방법 : 체이닝 (Chaining)

43 63 을삽입하기전 63 을삽입한후

44 완성된프로그램에서 25, 37, 18, 55, 22, 35, 50, 63 을차례로삽입한후, 50, 63 의 data 와 a 의내용출력결과

45 6.5 기타해싱 2- 방향체이닝 (Two-Way Chaining) 뻐꾸기해싱 (Cickoo Hashing)

46 2- 방향체이닝 체이닝과동일하나 2 개의해시함수를이용하여연결리스트의길이가짧은쪽에새키를저장 해시테이블의원소는 Node 를가리키는래퍼런스이외에도연결리스트의길이 (length) 를가짐 다음슬라이드의그림은 2 개의해시함수 h(key) 와 d(key) 가이미계산되어있다고가정한후, 25, 37, 18, 55, 22, 35, 50, 63 을차례로저장한결과

47 2- 방향체이닝

48 25, 37, 18, 55, 22 까지는충돌없이저장되나, 35 를저장할때에는 h(35) = 9, d(35) = 5 이고 a[9] 와 a[5] 의연결리스트의길이가같으므로, 임의로 a[5] 의연결리스트에 35 를저장 50 을저장할때는 h(50) = 11, d(50) = 5 이므로 a[11] 과 a[5] 의리스트의길이를비교하여 a[11] 의리스트가더짧으므로 a[11] 의리스트에 50 을저장 63 을저장할때는 a[11] 와 a[7] 의리스트의길이를비교하여 a[7] 의리스트가짧으므로 a[7] 의리스트에 63 을저장 새로운키가삽입되면해당리스트의길이를 1 증가

49 2- 방향체이닝은두개의해시함수를계산해야하고, 연결리스트의길이를비교해야하며, 추후에탐색을 위해선두연결리스트를탐색해야하는경우도발생 연구결과에따르면, 연결리스트의평균길이는 O(loglog N) 으로매우짧아서실제로매우좋은성능을보임

50 뻐꾸기해싱 뻐꾸기해싱 (Cuckoo Hashing) 은뻐꾸기가다른새의둥지에알을낳고, 부화된뻐꾸기새끼가다른새의알이나새끼들을둥지에서밀어내는습성을모방한해싱방법 뻐꾸기해싱은 2 개의해시함수와 2 개의해시테이블을가지고키들을다음의알고리즘에따라저장 해시함수 h(key) 는 htable 을위한것이고, 해시함수 d(key) 는 dtable 을위한것

51 새키저장알고리즘 [1] key = new_key [2] h(key) = i를계산하여, htable[i] 에 key를저장 [3] if key가저장된원소가비어있으면 : 삽입을종료 [4] else: // key가저장되면서그자리에있던키를쫓아낸경우 key 때문에쫓겨난키를 old_key라고하자. [5] if old_key가있었던테이블이 htable이면 : d(old_key)=j를계산하여, dtable[j] 에 old_key를저장 [6] else: // old_key가있었던테이블이dtable이면 h(old_key)=j 를계산하여, htable[j] 에 old_key 를저장 [7] key = old_key, go to step [3]

52 뻐꾸기해싱으로 10, 32, 45, 61 을차례로삽입하는과정

53 뻐꾸기해싱의삽입과정중발생한싸이클 삽입과정에서싸이클이발생할경우, 뻐꾸기해싱은삽입에실패한것으로간주하여재해싱을수행

54 뻐꾸기해싱의장점은탐색과삭제를 O(1) 시간에보장한다는것인데, 이런장점을갖는해시함수는아직존재하지않음 즉, 최대 2 회의해시함수계산으로각각의테이블원소를찾아각연산을처리 단, 삽입은높은확률로 O(1) 시간에수행이가능

55 재해시 (Rehash) 어떤해싱방법도해시테이블에비어있는원소가적으면, 삽입에실패하거나해시성능이급격히저하되는현상을피할수없음 이러한경우, 해시테이블을확장시키고새로운해시함수를사용하여모든키들을새로운해시테이블에다시저장하는재해시가필요 재해시는오프라인 (Off-line) 에서이루어지고모든키들을다시저장해야하므로 O(N) 시간이소요

56 재해시수행여부는적재율 (Load Factor) 에따라결정 적재율 = ( 테이블에저장된키의수 N)/ ( 테이블크기 M) 일반적으로 > 0.75 가되면해시테이블크기를 2 배로 늘리고, < 0.25 가되면해시테이블을 1/2 로줄임

57 동적해싱 (Dynamic Hashing) 대용량의데이터베이스를위한해시방법으로재해싱을수행하지않고동적으로해시테이블의크기를조절 대표적인동적해싱 확장해싱 (Extendible Hashing) 선형해싱 (Linear Hashing)

58 확장해싱 디렉터리 (Directory) 를메인메모리 (Main Memory) 에저장하고, 데이터는디스크블록 (Disk Block) 크기의버킷 (Bucket) 단위로저장 버킷이란키를저장하는곳 확장해싱에서는버킷에 overflow가발생하면새버킷을만들어나누어저장하며이때이버킷들을가리키던디렉터리는 2 배로확장

59 확장해싱의디렉터리확장 (b) 디렉터리확장전 (c) 디렉터리확장후 (a) 키코드

60 (a) 의키코드의마지막두자리를가지고키들을버킷에저장한다. 이때의버킷크기는 4이다. 즉, (b) 에서버킷 [E3, N7, Q3, Z7] 은꽉차있는상태 K3을삽입하면 K3의코드의마지막 2자리가 11 이므로 [E3, N7, Q3, Z7] 버킷에저장되어야하지만꽉차있으므로, (c) 와같이디렉터리를 2배로확장한다. 이때코드의마지막세자리를가지고키들을탐색, 삽입, 삭제연산을수행

61 선형해싱 디렉터리없이삽입할때버킷을순서대로추가하는방식 추가되는버킷은삽입되는키가저장되는버킷과무관하게순차적으로추가 만일삽입되는버킷에저장공간이없으면 overflow 체인에새키를삽입 체인은단순연결리스트로서 overflow 된키들을임시로저장하고, 나중에버킷이추가되면 overflow 체인의키들을버킷으로이동

62 (a) 키코드 (b) K1 삽입전 (c) K1 삽입후 (d) C4 삽입후 버킷크기가 2 이다. (b) 는 (a) 의키코드에따라마지막두자리를이용하여키들을저장한상태 (c) 는 K1 을삽입하려는데버킷 001 에저장할공간이없어 overflow 체인에임시로 K1 을저장한경우

63 다음으로추가되는버킷은인덱스가 100 이며, 이때버킷 000 에저장되었던 P4 는버킷 100 으로이동 - 왜냐하면 P4 코드의마지막 3 bit 가 100 이기때문 (d) 는 C4 를 100 버킷에삽입한경우이며, 새롭게 101 버킷이추가되었다. 001 버킷의코드가 101 로끝나는키인 J5 가버킷 101 로이동하고, overflow 체인의 K1 은버킷 001 로이동 다음키가삽입될때에는버킷 110 이추가 선형해싱은디렉터리를사용하지않는다는장점을가지며, 인터렉티브 (Interactive) 응용에적합

64 6.6 해시방법의성능비교및응용 해시방법의성능은탐색이나삽입연산을수행할때성공과실패한경우를각각분석하여측정 선형조사는적재율 가너무작으면해시테이블에 empty 원소가너무많고, 값이 1.0에근접할수록군집화가심화됨 개방주소방식의해싱은 0.5, 즉, M 2N일때상수시간성능보임

65 체이닝은 가너무작으면대부분의연결리스트들이 empty 가되고, 가너무크면연결리스트들의길이가 너무길어져해시성능이매우저하됨 일반적으로 M 이소수이고, 10 정도이면 O(1) 시간 성능을보임

66 평균탐색횟수 적재율 대표적인해싱방법의성능비교

67 대표적인해싱방법의성능비교

68 요약 해싱이란키를간단한함수로계산한값을배열의인덱스로이용하여항목을저장하고, 탐색, 삽입, 삭제연산을평균 O(1) 시간에지원하는자료구조 해시함수는키들을균등하게해시테이블의인덱스로변환, 대표적인해시함수는나눗셈함수 충돌해결방법들은크게두가지로분류 : 개방주소방식, 폐쇄주소방식 개방주소방식 : 선형조사, 이차조사, 랜덤조사, 이중해싱

69 폐쇄주소방식은키에대한해시값에대응되는곳에만 키를저장 체이닝은해시테이블크기만큼의연결리스트를가지며, 키를해시값에대응되는연결리스트에저장 - 군집화현상이발생하지않으며, 구현이간결하여실제로가장 많이활용되는해시방법 2- 방향체이닝은 2 개의해시함수를이용하여연결리스트의길이가짧은쪽에새키를저장

70 뻐꾸기해싱은탐색과삭제를 O(1) 시간에보장하는매우효율적인해싱방법 재해시는삽입에실패하거나해시성능이급격히저하되었을때, 해시테이블의크기를확장하고새로운해시함수를사용해모든키들을새로운해시테이블에저장 동적해싱은대용량의데이터베이스를위한해시방법으로재해시를수행하지않고동적으로해시테이블의크기를조절 : 확장해싱과선형해싱

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

쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table http://academy.hanb.co.kr 6장. 해시테이블 테이블 Hash Table 사실을많이아는것보다는이론적틀이중요하고, 기억력보다는생각하는법이더중요하다. - 제임스왓슨 - 2 - 학습목표 해시테이블의발생동기를이해한다. 해시테이블의원리를이해한다. 해시함수설계원리를이해한다. 충돌해결방법들과이들의장단점을이해한다.