제 8 장 해싱

Transcription

1 제 8 장 해싱

2 개요 ADT 사전 (dictionary) 해싱 (Hashing) 정적해싱 (Static hashing) 동적해싱 (Dynamic hashing) 2

3 정적해싱 (1) 해시테이블 (1) 사전쌍들이해시테이블 ht 에저장 ht[0],, ht[b-1], 즉, b 개의버킷 (bucket) 으로분할됨 한버킷은 s 개의슬롯 (slot) 으로구성됨 한슬롯에는하나의사전쌍이저장됨 키값이 k 인한쌍의주소또는위치는해시함수 h 에의해결정됨 해시함수는키값을버킷으로사상시킴 h(k) : k 의해시또는홈주소 (home address) 사전쌍들은이상적인조건하에서는모두해당홈버킷 (home bucket) 에저장됨 3

4 정적해싱 (2) 해시테이블 (2) 정의 해시테이블의키밀도 (key density) 는 n/t 임 해시테이블의적재밀도 (loading density) 는 α = n/(sb) 임 n : 테이블에있는쌍의수 T : 가능한키의총개수 키밀도 n/t 는매우작고버킷수 b 도 T 보다작게됨 k 1 와 k 2 에대해 h(k 1 ) = h(k 2 ) 인경우 k 1 과 k 2 를 h 에대한동거자 (synonym) 라함 4

5 정적해싱 (3) 해시테이블 (3) 이상적인조건하에서, 사전쌍들은모두해당홈버킷에저장됨 오버플로 (overflow) 새로운사전쌍을삽입하려고할때, 홈버킷이차있는상태일경우 충돌 (collision) 새로운쌍의삽입시홈버킷에비어있는자리가없을경우 5

6 정적해싱 (4) 해시테이블 (4) b=26 개의버킷과 s=2 인해시테이블 n=10개, α =10/52 = 부터 25까지의숫자로사상시킴 GA와 G가같은버킷에있음 A와 A2가같은버킷에있음 A1을테이블어디에위치시켜야되는가? 6

7 정적해싱 (5) 해시테이블 (5) 오버플로가발생하지않을경우 삽입, 삭제, 탐색시간 사전의엔트리수인 n 에무관 해시함수의계산시간과한버킷을탐색하는데소요되는시간에만좌우됨 버킷크기 s 는작기때문에, 버킷내에서탐색을위해 순차탐색기법을사용할수있음 해싱기법 해시함수 h를사용하여키를해시테이블버킷에사상시킴 해시함수는충돌수최소화하도록선택해야함 오버플로처리하는기법이필요함 7

8 정적해싱 (6) 해시함수 (1) 키를해시테이블내의버킷으로사상시킴 계산이쉽고충돌이적어야함 균일해시함수 (uniform hash function) h(k) = i 가될확률은모든버킷 i 에대해 i/b 이됨 k = 키공간에서임의로선택된키 b 개의버킷각각에임의의 k 가대응될확률은모두같게됨 다양한종류의균일해시함수가사용됨 일부는산술적인연산을통해홈버킷을계산하지만, 많은응용에서산술적인연산을할수없는경우도있음 먼저키를정수와같이산술적인연산이가능한데이터타입으로변환한뒤에연산을수행함 8

9 정적해싱 (7) 해시함수 (2) 제산 (division) 함수 실제로가장많이쓰이는해시함수 키값이음이아닌정수라고가정 홈버킷은모드 (%) 연산자에의해결정 키 k 를정해진수 D 로나눈나머지를 k 의홈버킷으로사용 h(k) = k%d 버킷주소의범위 : 0 ~(D-1) 최소 b = D 개의버킷이있어야함 D 의선택이오보플로발생수에영향미침 D 의최소소인수의크기가증가하면편중정도는감수함 D 가홀수가되도록제한하고 b=d 배열의크기를두배로만들면버킷의수가 b 에서 2b+1 로증가됨 9

10 정적해싱 (8) 해시함수 (3) 중간제곱 (mid-square) 함수 키를제곱한후에버킷주소를얻기위해그결과의중간에있는적절한수의비트를취해서홈버킷을정함 키는정수라고가정함 제곱수의중간비트는그키의모든비트에의존하므로서로다른키들은서로다른해시주소를갖게될확률이높게됨 버킷주소를얻기위해사용되는비트의수는테이블크기에달려있음 r 개의비트가사용되면각값들의범위는 0 에서 2r-1 까지가됨 해시테이블의크기는 2 의제곱이되게선정 10

11 정적해싱 (9) 해시함수 (4) 접지 (folding) 함수 숫자로된키 k 를몇부분으로나누는데, 마지막부분을제외하고는모두길이가같음 각부분들을서로더하여 k 에대한해시주소만듦 두가지덧셈방식 이동접지 (shift folding) 마지막을제외한모든부분들을이동시킴 최하위비트가마지막부분의자리와일치하도록맞춤 서로다른부분들을더하여 h(k) 를얻음 경계접지 (folding at the boundaries) 키의각부분들을경계에서겹치게함 같은자리에위치한수들을더하여 h(k) 를얻음 11

12 정적해싱 (10) 해시함수 (5) 접지함수예제 k = , 길이가세자리인부분들로나눈다. P1 = 123, P2 = 203, P3 = 241, P4 = 112, P5 = 20 이동접지방법사용 : h(k) = = = 699 경계접지방법사용 : 먼저 P2 와 P4 를역순으로하여 302 와 211 을각각구한후다섯개의부분을더하여 h(k) = = 897 을구함 12

13 정적해싱 (11) 해시함수 (6) 숫자분석함수 (digital analysis) 정적파일 (static file) 과같은경우에유용함 각키를어떤기수 (radix) r을이용해하나의숫자로바꿈 이기수를이용해각키의숫자들을검사함 가장편향된 (skewed) 분산을가진숫자생략 남은숫자만으로해시테이블주소를결정함 13

14 정적해싱 (12) 해시함수 (7) 키를정수로변환 키를음이아닌정수로변환함 유일한정수로변환시킬필요없음 스트링을정수로변환하기 16- 비트정수로사상시킴 14

15 정적해싱 (13) 해시함수 (8) 키를정수로변환 ( 계속 ) C++ STL 은 T 타입의어떤개체를음이아닌정수 size_t 로변환시키는 STL 템플릿클래스 hash<t> 를특별히제공 15

16 정적해싱 (14) - 안전해시함수 (1) 컴퓨터보안분야의여러응용에사용되는해시함수 (ex) 메시지인증 (message authentication) 메시지 M 이보안되어있지않은채널을통해 A 에서 B 로전송될때, B 에서받은메시지가위조된것이아니라 A 에서전송된원본메시지라고신뢰할수있는방법 해시함수 h 를이용해메시지 M 의해싱값 h(m) 을더안전한경로로보냄 약한충돌저항 (weak collision resistance) M 과 h 에대해잘숙지하고있는악의있는사용자가 M 의동거자를쉽게찾지못하게하는해시함수를사용해야하는특성 16

17 정적해싱 (15) - 안전해시함수 (2) 단방향특성 (one-way property) h(k) =c 를만족하는 c 가주어졌을때, k 를찾는것을계산적으로어렵게만드는것 강한충돌저항 (strong collision resistance) h(x) = h(y) 를만족시키는 (x,y) 쌍을계산적으로찾기어렵게만드는것 암호화해시함수의추가적인특징 보안외에도실용적으로사용될수있도록가지는특성들 (1) h 는데이타블록크기상관없이적용가능해야함 (2) h 는고정길이의해시코드를만들어야함 (3) h(k) 는어떤 k 가주어져도계산이비교적쉬워서하드웨어와소프트웨어의구현이실용적이어야함 17

18 정적해싱 (16) - 안전해시함수 (3) 보안해시알고리즘 (SHA : Secure Hash Algorithm) 미국국립표준기술연구소 (NIST) 에서처음개발함 입력 : 2 64 비트보다적은길이의메시지가능 출력 : 160 비트길이의코드 1단계 : 어떤정수 q에대해메시지의길이가 q*512 비트가되도록전처리 (preprocess) 한다. 이때메시지의뒤에 0으로채워넣을수있다. 2단계 : 160-비트의출력버퍼, OB를초기화한다. 이버퍼는 5개의 32-비트레지스터 A, B, C, D, E로구성되는데, 여기서 A= , B=efcdab89, C= 98bdcfe, D= , E=c3d2e1f0 이다 ( 이값들은 16진수이다 ). 3단계 : for(int i=1; i<=q; i++){ B i = 메시지의 512 비트로이루어진 i번째블록 OB = F(OB, B i ); } 4단계 : OB를출력한다. SHA 알고리즘 18

19 정적해싱 (17) - 안전해시함수 (4) 19

20 정적해싱 (18) 오버플로처리 (1) 오버플로를처리하는방법 개방주소법 (open addressing) 선형조사법 (linear probing) 이차조사법 (quadratic probing) 재해싱 (rehashing) 임의조사법 (random probing) 체인법 (chaining) 20

21 정적해싱 (19) 오버플로처리 (2) 선형조사법 (1) 키값이 k 인새로운쌍하나를삽입할때 ht[h(k)+i]%b 의순서에따라해시테이블버킷검색 h : 해시함수, b : 버킷의수, 0<= i <= b 1 다채워지지않은버킷을만나면검색이끝나고새로운쌍이그버킷으로삽입됨 빈자리가있는버킷이없다면해시테이블이만원인것 테이블크기를늘려야함 적재밀도 = 0.75 와같은경계값을넘을때테이블크기늘림 해시테이블의크기를다시정할때 해시함수바꿔야함 모든사전엔트리들은새로커진테이블에다시사상되어야함 A A2 A1 D A3 A4 GA G ZA E L. Z 선형조사법에의한해시테이블 (26 개의버킷, 버킷당하나의슬롯 ) 21

22 정적해싱 (20) 오버플로처리 (3) 선형조사법 (2) S=1, 선형조사법으로오버플로처리하는경우, 키 k 를해시테이블에서탐색하는과정 (1) h(x) 계산 (2) 다음과같은경우중하나가발생할때까지 ht[h(k)], ht[(h(k)+1)%b],, ht[(h(k)j)%b] 순서로해시테이블버킷을조사 버킷 ht[(h(k)+j)%b] 에값이 k 인키쌍이있는경우 원하는쌍이발견되었음 ht[h(k)+j] 가비어있는경우 K 는테이블에없음 시작위치 ht[h(k)] 로돌아온경우 테이블은만원이고 k 는테이블에없음 22

23 정적해싱 (21) 오버플로처리 (4) 선형조사법 (3) template <class K, class E> pair<k,e>* LinearProbing <K,E>::Get(const K&k) {// 선형조사법해싱테이블 ht( 각버킷은한슬롯만가짐 ) 에서 k를탐색. // 이키를가진쌍을발견하면, 그쌍을가리키는포인터를반환. // 그렇지않으면 0을반환. int i = h(k); // 홈버킷 int j; for(j = i; ht[k] && ht[j] first!= k;) { j = (j+1) % b; // 테이블을원형으로간주 if(j == i) return 0; // 시작점으로복귀 } if (ht[j] first == k) return ht[j]; return 0; } 선형조사법 23

24 정적해싱 (22) 오버플로처리 (5) 선형조사법 (4) 선형조사법으로오버플로를해결하는경우 키들이클러스터 (cluster) 되는경향이있어탐색시간증가 균등해시함수와함께선형조사법을사용할경우 α 가적재밀도일때키를찾기위한평균키비교횟수의기대값 (2-α)/(2-2α) 이차조사법 (quadratic probing) 클러스터의크기를줄이기위해서이용 선형조사법에서는 b 가테이블에있는버킷의수라고할때 (h(k)+i)%b, 1 i b-1 인버킷을찾는반면이차조사법에서는 i 의이차함수가증분으로사용됨 0 i (b-1)/2 에대해 h(k), (h(k)+i2) % b, (h(k)-i2) % b 를검사하는방법으로탐색을수행 b 가 4j+3(j 는정수 ) 인형태의소수라면이차조사법에서는테이블의모든버킷을조사하면됨 24

25 정적해싱 (23) 오버플로처리 (6) 선형조사법 (5) 클러스터확대를줄이기위한다른방법 재해싱 (rehashing) 여러개의해시함수 h 1, h 2,..., h m 을사용하는방법버킷 h i (k) (0 i m) 를순서대로검사 임의조사법 (random probing) 형태가 4j+3 인몇가지소수들 25

26 정적해싱 (24) 오버플로처리 (7) 선형조사법과같은방법들이효율이좋지않은이유 키를탐색할때서로다른해시값을가진키와비교를해야하기때문 체인법 체인을사용할때 ChainNode <pair <K, E>>* 타입의배열 ht[0:b-1] 을이용 ht[i] 는버킷 i 에연결된체인중첫번째노드를가리킴 template <class K, class E> pair<k,e>* Chaining <K,E>::Get(const K&k) {// 체인으로연결된해시테이블 ht 에서 k 를탐색 // 이키를가진쌍을발견하면, 그쌍을가리키는포인터를반환 // 그렇지않으면 0 을반환 int i = h(k); // 홈버킷 // ht[j] 에서시작하는체인을탐색 for(chainnode <pair <K, E>>* current = ht[i]; current; current = current -> link) if(current->data.first == k) return &current->data; return 0; } 체인검색 26

27 정적해싱 (25) 오버플로처리 (8) 27

28 정적해싱 (26) 오버플로처리 (9) 체인법 ( 계속 ) 체인법을균일해시함수와함께사용할경우 검색이성공했을경우키의비교횟수기대치는 α 가적재밀도이고 n/b(b 는버킷의수 ) 일때평균적으로약 1 + α/2 임 해시테이블의성능은오버플로를처리하는방식에만좌우됨 키가편중적으로선택되어지는경향이있음 해시함수에따라해시테이블의성능도달라짐 체인법과함께제산함수를사용하면가장좋은성능가짐 성공적인탐색을위해필요한최악의경우에비교횟수 O(n) 체인이아니라균형탐색트리에저장하면 O(log n) 28

29 정적해싱 (27) 오버플로처리 (10) 오버플로기법의이론적평가 (1) 균형트리와같은상용기법보다성능이우수 최악의경우에는해싱의성능좋지않음 n 개의키를가진해시테이블에서의삽입, 탐색에 O(n) 시간이걸릴수도있음 체인방법의예상성능에대한확률적분석 ht[0:b-1] : 한개의슬롯으로된버킷 b 개를가진해시테이블 h : 치역이 [0,b-1] 인균일해시함수 n 개의키 k 1, k 2,..., k n 이해시테이블에저장 h(k 1 ), h(k 2 ),..., h(k n ) 과같은 b n 가지의서로다른해시순서가있을것 이들이균등한발생확률을가진다고가정 S n : 임의로선택된 k i (1 i n) 의주소확인에필요한예상키비교횟수 j 번째키인 k j 를찾는데필요한평균비교횟수 균등한확률로선택되는 j(1 i n) 와 b n 가지해시순서에따른비교횟수를평균한값 U n : 해시테이블에없는키를찾는데필요한예상비교횟수 29

30 정적해싱 (28) 오버플로처리 (11) 오버플로기법의이론적평가 (2) 체인방법의예상성능에대한확률적분석 ( 계속 ) ( 정리 8.1) a = n/b 가균일해시함수를사용한해시테이블의적재밀도라하자. (1) 선형개발주소법에대해 U n = ½ [1 + 1/(1-a) 2 ] S n = ½ [1 + 1/(1-a)] (2) 재해싱및임의조사법과이차조사법에대해 U n 1/(1-a) S n [1/a]log e (1-a) (3) 체인법에대해 U n a S n 1 + a/2 30

31 정적해싱 (29) 오버플로처리 (12) 오버플로기법의이론적평가 (3) 체인방법의예상성능에대한확률적분석 ( 계속 ) ( 증명 ) 검색하고자하는키 k 가 h(k)=i 이고체인 i 가 q 개의노드를가졌을경우 k 가체인에없으면 q 번의비교가필요 k 가그체인에서 j 번째노드에있다면 (1 j q), j 번의비교가필요 n 개의키가 b 개의체인에일정하게분산되어있을경우 각체인에있는키개수의기대값은 n/b=α Un 은체인에서의예상키수이므로 U n =α i 번째의키 ki 가테이블에들어갈때체인에서의예상키수 : (i-1)/b 결과 n 개의모든키가저장된후에 ki 를탐색하는데필요한예상비교횟수 : 1 + (i 1)/b 31

32 동적해싱 동적해싱 (dynamic hashing) 의배경 확장성해싱 (extendible hashing) 이라고도불림 재조정을한번할때마다오직하나의버킷안에있는엔트리들에대해서만홈버킷을변경하게하여재조정시간을줄임 하나의연산에대해좋은성능을유지할수있게함 해시함수의예 32

33 디렉터리를이용한동적해싱 (1) 디렉터리 (directory) 를이용한동적해싱 버킷들에대한포인터를저장하고있는디렉터리 d를이용 디렉터리의크기 : h(k) 의비트수에좌우됨 디렉터리깊이 (directory depth) 디렉터리를인덱싱하는 h(k) 의비트수 t : 디렉터리깊이, 2 t : 디렉터리크기 (ex) h(k,2) 를사용하여인덱싱 디렉터리의크기 = 2 2 =4 h(k,5) 를사용하여인덱싱 디렉터리의크기 = 2 5 =32 버킷수 < 디렉터리크기 33

34 디렉터리를이용한동적해싱 (2) 키 A0, B0, A1, B1, C2, C3 을포함하고있는동적해시테이블 (1) 깊이가 2 인디렉터리를사용 각버킷에는두개의슬롯 ( 색칠된것 디렉터리나머지 버킷들 ) 34

35 디렉터리를이용한동적해싱 (3) 키 A0, B0, A1, B1, C2, C3 을포함하고있는동적해시테이블 ( 계속 ) 키 k 를탐색하려면, t 가디렉터리깊이일때 d[h(k,t)] 가가리키는버킷을탐색해보기만하면됨 오버플로발생시해결방법 오버플로가된버킷의모든키에대해 h(k,u) 가같지않게하는 최하위비트 u 를정함 디렉터리크기는증가, 버킷개수는그대로임 디렉터리크기재조정후 h(k,u) 를사용하여오버플로가된버킷을분할 현재디렉터리깊이가 u 와같거나클때분할된버킷을가리키는다른 포인터들역시새로운버킷을가리키도록갱신되어야함 동적해싱은배열을두배로만드는방법을사용하지만정적해싱에서배열을두배로만드는것보다시간이적게걸림 오버플로가된버킷에있는엔트리들만재해싱하면되므로 35

36 디렉터리없는동적해싱 (1) 버킷포인터의디렉터리 d 대신버킷의배열인 ht 를사용 배열의크기는매우커서동적으로늘릴필요가없다고가정 q 와 r 이라는변수 (0 q<2 r ) 를두어활성화된버킷 (active bucket) 에대한정보를얻어냄 항상 0 부터 2r+q-1 까지의버킷만활성화됨 각활성버킷은버킷체인의시작이됨 오버플로버킷 (overflow bucket) : 체인의나머지버킷들 2r 부터 2r+q-1 까지의활성버킷뿐만아니라 0 부터 q-1 까지의활성버킷은 h(k, r+1) 을이용하여인덱싱 나머지활성버킷들은 h(k,r) 을이용하여인덱싱 각사전쌍들은활성버킷이거나오버플로버킷 36

37 디렉터리없는동적해싱 (2) r=2 이고 q=0 일때디렉터리가없는해시테이블 ht 그림 8.6의해시함수사용, 활성버킷개수 = 4 각활성버킷에는두개의슬롯 37

38 블룸필터 (1) 응용 차등파일 (1) 인덱싱된화일 (indexed file) 을관리하는응용 하나의인덱스와하나의키가있을때 밀집인덱스 (dense index) 이고, 화일의갱신이허용된다고가정 인덱스화일의백업사본을유지하는것이필요 마스터인덱스 (master index), 마스터화일 (master file) 인덱스파일의작업사본 트랜잭션로그 (transaction log) 장애회복을위해필요 백업사본과백업사본생성이후에만들어지는모든갱신로그 장애회복을위해백업사본과트랜잭션로그를처리하여장애당시작업사본의인덱스화일을재생해야함 회복시간 백업인덱스와화일크기, 트랜잭션로그크기의함수가됨 차등화일 (differential file) 인덱스가아니라화일만클경우 별도의화일에갱신된레코드를저장함으로써복구시간줄일수있음 38

39 블룸필터 (2) 응용 차등파일 (2) 39

40 블룸필터 (3) 응용 차등파일 (3) 차등화일을사용할때, 백업파일은마스터화일의복사본 인덱스, 화일, 트랜잭션로그상대적으로작음 빈번한백업가능함 한화일연산을수행할때필요한디스크접근횟수에는영향을주지않음 인덱스, 화일클경우 차등화일, 차등인덱스 (differential index) 로문제해결함 40

41 블룸필터 (4) 블룸필터설계 블룸필터 (Bloom filter) 내부메모리에상주하여 차등인덱스에키가있는가? 와같은유형의질의를허용하는장치 차등인덱스안에모든키의리스트를유지함 위와같은유형의질의에정확하게응답하지않음 no maybe 와 no 중에하나로응답 탐색키가차등인덱스에있지않다는것을보장 maybe 차등인덱스를탐색 41

42 블룸필터 (5) 필터오류가될확률 P(u) = (1-1/n) u (1-(1-1/m) uh ) h 근사값을사용하면 (1-1/x) q ~ e -q/x 큰값 x 에대해 P(u) ~ e -u/n (1-e -uh/m ) h h 에대해서 P(u) 를미분하고결과를 0 으로지정하면 h = (log e 2)m/u ~ 0.693m/u 42