09_hash

Size: px

Start display at page:

Download "09_hash"

채홍 조
6 years ago
Views:

1 Hash Data Structures and Algorithms

2 목차 빠른탐색 : 해쉬테이블 예제 좋은해쉬함수 충돌의해결 구현 응용 : Bloom Filter Data Structures and Algorithms 2

3 빠른탐색 : 해쉬테이블 Data Structures and Algorithms 3

4 테이블 : Key-Value 의집합 사전구조또는맵 (map) 데이터는 key 와 value 가한쌍 key 가데이터의저장및탐색기준 테이블자료구조에서원하는데이터를단번에찾음 복잡도 : O(1) 테이블자료구조의예 Data Structures and Algorithms 4

5 배열기반테이블 ( 해시없는개념이해용 ) typedef struct _empinfo { int empnum; // Key: 직원의고유번호 int age; // value: 직원의나이 EmpInfo; int main(void) { EmpInfo empinfoarr[1000]; EmpInfo ei; int enum; printf(" 사번과나이입력 : "); scanf("%d %d", &(ei.empnum), &(ei.age)); empinfoarr[ei.empnum] = ei; // 단번에저장! printf(" 확인하고픈직원의사번입력 : "); scanf("%d", &enum); 직원고유번호 (key) 를배열의인덱스로활용 ei = empinfoarr[enum]; // 단번에탐색! printf(" 사번 %d, 나이 %d \n", ei.empnum, ei.age); return 0; Data Structures and Algorithms 5

6 해쉬함수와충돌 int main(void) { EmpInfo empinfoarr[100]; EmpInfo emp1={ , 42; EmpInfo emp2={ , 33; EmpInfo emp3={ , 27; // hash 함수 f(x) int GetHashValue(int empnum) { return empnum % 100; EmpInfo r1, r2, r3; empinfoarr[gethashvalue(emp1.empnum)] = emp1; // 키를인덱스로활용 empinfoarr[gethashvalue(emp2.empnum)] = emp2; empinfoarr[gethashvalue(emp3.empnum)] = emp3; r1 = empinfoarr[gethashvalue( )]; // 키를인덱스로탐색 r2 = empinfoarr[gethashvalue( )]; r3 = empinfoarr[gethashvalue( )]; printf(" 사번 %d, 나이 %d \n", r1.empnum, r1.age); // 탐색결과확인 printf(" 사번 %d, 나이 %d \n", r2.empnum, r2.age); printf(" 사번 %d, 나이 %d \n", r3.empnum, r3.age); return 0; Data Structures and Algorithms 6

해쉬함수와충돌 EmpInfo emp1={20120003, 42; EmpInfo emp2={20130012, 33; EmpInfo emp3={20170049,

= empinfoarr[gethashvalue(20170049)]; int GetHashValue(int empnum) { return empnum % 100;

7 해쉬함수와충돌 EmpInfo emp1={ , 42; EmpInfo emp2={ , 33; EmpInfo emp3={ , 27; r1 = empinfoarr[gethashvalue( )]; r2 = empinfoarr[gethashvalue( )]; r3 = empinfoarr[gethashvalue( )]; int GetHashValue(int empnum) { return empnum % 100; f(x) 는키를기준범위내에재배치함단, 기준범위가좁으면다른 key 이지만같은공간에저장될수있음 ( 충돌발생 ) Data Structures and Algorithms 7

8 예제 Data Structures and Algorithms 8

9 Ex: Person 테이블정의 키 : 주민등록번호 값 : 구조체변수의주소값 typedef struct _person { int ssn; // 주민등록번호 char name[str_len]; // 이름 char addr[str_len]; // 주소 Person; int GetSSN(Person * p); void ShowPerInfo(Person * p); Person * MakePersonData(int ssn, char * name, char * addr); int GetSSN(Person * p){ return p->ssn; void ShowPerInfo(Person * p){ printf(" 주민등록번호 : %d \n", p->ssn); printf(" 이름 : %s \n", p->name); printf(" 주소 : %s \n\n", p->addr); Person * MakePersonData(int ssn, char * name, char * addr){ Person * newp = \ (Person*)malloc(sizeof(Person)); newp->ssn = ssn; strcpy(newp->name, name); strcpy(newp->addr, addr); return newp; Data Structures and Algorithms 9

10 Ex: Person - Slot 슬롯상태 : EMPTY, DELETED, INUSE typedef int Key; typedef Person * Value; enum SlotStatus {EMPTY, DELETED, INUSE; typedef struct _slot { Key key; Value val; enum SlotStatus status; Slot; 슬롯 Data Structures and Algorithms 10

11 Ex: Person 해쉬함수와초기화 typedef int HashFunc(Key k); typedef struct _table { Slot tbl[max_tbl]; HashFunc * hf; Table; // 테이블의초기화 void TBLInit(Table * pt, HashFunc * f); // 테이블에키와값을저장 void TBLInsert(Table * pt, Key k, Value v); // 키를근거로테이블에서데이터삭제 Value TBLDelete(Table * pt, Key k); // 키를근거로테이블에서데이터탐색 Value TBLSearch(Table * pt, Key k); void TBLInit(Table * pt, HashFunc * f) { int i; // 슬롯초기화 for(i=0; i<max_tbl; i++) (pt->tbl[i]).status = EMPTY; pt->hf = f; // 해쉬함수등록 Data Structures and Algorithms 11

12 Ex: Person: 해쉬함수 void TBLInsert(Table * pt, Key k, Value v){ int hv = pt->hf(k); // 해쉬값을얻음 pt->tbl[hv].val = v; pt->tbl[hv].key = k; pt->tbl[hv].status = INUSE; Value TBLDelete(Table * pt, Key k){ int hv = pt->hf(k); // 해쉬값을얻음 if((pt->tbl[hv]).status!= INUSE){ return NULL; else { (pt->tbl[hv]).status = DELETED; return (pt->tbl[hv]).val; // 삭제된데이터리턴 Value TBLSearch(Table * pt, Key k){ int hv = pt->hf(k); // 해쉬값을얻음 if((pt->tbl[hv]).status!= INUSE) return NULL; else return (pt->tbl[hv]).val; // 탐색대상리턴 Data Structures and Algorithms 12

13 Ex: Person - Main int MyHashFunc(int k){ // 키를부분적으로만사용한 // 않은해쉬의예!!! return k % 100; int main(void) { Table mytbl; Person * np; Person * sp; Person * rp; TBLInit(&myTbl, MyHashFunc); // 데이터입력 np = MakePersonData( , "Lee", "Seoul"); TBLInsert(&myTbl, GetSSN(np), np); np = MakePersonData( , "KIM", "Jeju"); TBLInsert(&myTbl, GetSSN(np), np); // 데이터검색 sp = TBLSearch(&myTbl, ); if(sp!= NULL) ShowPerInfo(sp); sp = TBLSearch(&myTbl, ); if(sp!= NULL) ShowPerInfo(sp); sp = TBLSearch(&myTbl, ); if(sp!= NULL) ShowPerInfo(sp); // 데이터삭제 rp = TBLDelete(&myTbl, ); if(rp!= NULL) free(rp); rp = TBLDelete(&myTbl, ); if(rp!= NULL) free(rp); rp = TBLDelete(&myTbl, ); if(rp!= NULL) free(rp); return 0; np = MakePersonData( , "HAN", "Kangwon"); TBLInsert(&myTbl, GetSSN(np), np); Data Structures and Algorithms 13

14 좋은해쉬함수 Data Structures and Algorithms 14

15 좋은해쉬함수 키전체를참조하여해쉬값을생성 키스페이스를모두조합하여해쉬값생성시결과가고르게분포할것이다는기대 특정위치에몰림 Vs 분산된저장위치 Data Structures and Algorithms 15

16 자릿수선택방법 가정 키스페이스분석가능및완료 전략 중복비율이높거나공통인부분을제외 예 : 여덟자리의수로이뤄진키스페이스 해쉬값에영향을주는네자리수를뽑아생성 Data Structures and Algorithms 16

17 자릿수폴딩방법 키스페이스의연산을통해저장할위치지정 정해진규칙은없음 필요에따라다양한근거로생성 예 = 80 Data Structures and Algorithms 17

18 충돌의해결 Data Structures and Algorithms 18

19 선형조사법 (Linear Probing) 단순함 충돌의횟수증가에따라클러스터현상발생 클러스터현상 : 특정영역에데이터가몰리는현상 충돌없을때 : f(k) = k % 7 충돌있을때 : f(k) = k % 7 + n, 이때 n 은. 충돌횟수 K = 9 K%7 + 1 = 2 K = 2 K%7 + 1^2 = 3 Data Structures and Algorithms 19

20 2 차조사법 + DELETED 선형조사법보다멀리서빈자리찾음 K = 9 K%7 + 1 = 2 K = 2 K%7 + 1^2 = 3 K = 9 삭제 DELETED 상태 K%7 + 1 = 2 DELETED 표시해야동일한해쉬값의 데이터저장검사가능 Data Structures and Algorithms 20

21 이중해시 빈슬롯의위치가늘동일한문제 다른해쉬함수를활용하는방법 배열의길이가 15 인경우의예 15 보다작은소수로 c 를결정 예 1 을더하는이유 : 2 차해쉬값이 0 이안되도록 c 를 15 보다작은값으로하는이유 : 배열의길이가 15 이므로 c 를소수로결정하는이유 : 클러스터현상을낮춘다는통계를근거로! Data Structures and Algorithms 21

22 체이닝 ( 닫힌어드레싱모델 ) 한해쉬값에다수의데이터를저장할수있도록배열을 2 차원의형태로선언하는모델 한해쉬값에다수의데이터를저장할수있도록각해쉬값별로연결리스트를구성하는모델 2 차원배열모델 연결리스트모델 Data Structures and Algorithms 22

23 구현 Data Structures and Algorithms 23

24 구현 : 체이닝 슬롯에저장할데이터관련헤더및소스파일 Person.h, Person.c 테이블관련헤더및소스파일 Slot.h, Table.h, Table.c 확장대상 Slot.h, Table.[ch] 활용할개념 : 해쉬값별연결리스트구성용 이중연결리스트 (DLinkedList.[ch]) Data Structures and Algorithms 24

25 확장 : 슬롯 (Slot.h) 체이닝기반 : 슬롯상태비유지 typedef int Key; typedef Person * Value; enum SlotStatus {EMPTY, DELETED, INUSE; typedef struct _slot { Key key; Value val; enum SlotStatus status; Slot; Data Structures and Algorithms 25

26 확장 : 테이블 typedef int HashFunc(Key k); typedef struct _table { // 해쉬값별로리스트구성 Slot List tbl[max_tbl]; HashFunc * hf; Table; 노드의데이터가슬롯리스트의활용 // 테이블의초기화 void TBLInit(Table * pt, HashFunc * f); // 테이블에키와값을저장 void TBLInsert(Table * pt, Key k, Value v); // 키를근거로테이블에서데이터삭제 Value TBLDelete(Table * pt, Key k); // 키를근거로테이블에서데이터탐색 Value TBLSearch(Table * pt, Key k); Data Structures and Algorithms 26

27 확장 : 연결리스트 #include "Slot2.h" // 헤더파일추가 // typedef int LData; typedef Slot LData; // 변경된 LData 타입 typedef struct _node { LData data; struct _node * next; Node; typedef struct _linkedlist { Node * head; Node * cur; Node * before; int numofdata; int (*comp)(ldata d1, LData d2); LinkedList; Data Structures and Algorithms 27

28 확장 : 초기화와삽입연산 void TBLInit(Table * pt, HashFunc * f) { int i; for(i=0; i<max_tbl; i++) ListInit(&(pt->tbl[i])); // 연결리스트각각에대해서초기화 pt->hf = f; void TBLInsert(Table * pt, Key k, Value v) { int hv = pt->hf(k); Slot ns = {k, v; if(tblsearch(pt, k)!= NULL) { // 키가중복되었다면 printf(" 키중복오류발생 \n"); return; else { LInsert(&(pt->tbl[hv]), ns); // 해쉬값기반삽입 Data Structures and Algorithms 28

29 확장 : 삭제 Value TBLDelete(Table * pt, Key k) { int hv = pt->hf(k); Slot cslot; if(lfirst(&(pt->tbl[hv]), &cslot)){ if(cslot.key == k){ LRemove(&(pt->tbl[hv])); return cslot.val; else { while(lnext(&(pt->tbl[hv]), &cslot)){ if(cslot.key == k){ LRemove(&(pt->tbl[hv])); return cslot.val; return NULL; Data Structures and Algorithms 29

30 확장 : 탐색 Value TBLSearch(Table * pt, Key k) { int hv = pt->hf(k); Slot cslot; if(lfirst(&(pt->tbl[hv]), &cslot)){ if(cslot.key == k){ return cslot.val; else { while(lnext(&(pt->tbl[hv]), &cslot)){ if(cslot.key == k) return cslot.val; return NULL; Data Structures and Algorithms 30

31 응용 : Bloom Filter Data Structures and Algorithms 31

32 블룸필터란? 집합을표현한자료구조 집합에서찾는값의존재여부를알려줌 확률적자료구조 집합에속한원소를속하지않았다고하는일은절대없음 단, 속하지않은원소를가끔속했다고함 (False Positive) 실제결과 Positive Negative (False Negative) 예측결과 NEGATIVE POSITIVE True Positive False Negative False Positive True positive Data Structures and Algorithms 32

33 핵심 ADT AddKey: 집합에키 / 원소추가 IsMember: 집합에키가존재하는지검사 (with False Positives) DeleteKey: Not supported Data Structures and Algorithms 33

34 블룸필터의활용처 구글크롬 : 악성 URL 목록 Medium 뉴스사이트 : 사용자가이미읽은기사관리 그외에도응용처가많음 Data Structures and Algorithms 34

35 블룸필터에키삽입 가정 집합은최초에비었음 (0으로초기화 ) 해쉬함수는모두독립 집합의크기 : m 해쉬함수의갯수 : k AddKey(X) // h1(x), h2(x),, hx(x) 결과의위치를 set x y h1(x) h2(x) h3(x) h1(x) h2(x) h3(x) Data Structures and Algorithms 35

36 False Positive Rate N 번의 AddKey 연산후, 특정비트가 set 인확률 False positive 이려면, k 개의해쉬의결과가이미 set 이어야함 False positive 가최소가되려면 최소 false positive rate Data Structures and Algorithms 36

37 블룸필터의크기 Vs False Positive 확률 블룸필터의크기가커질수록오차확률은매우적어짐 Image Source: Data Structures and Algorithms 37

38 해쉬함수개수를줄이면서성능유지하기 두개의해쉬함수로 K 개의해쉬함수대신하기 해쉬함수 g1(x) 와 g2(x) 로전혀다른해쉬함수 h(x) 만들기 점근적오차확률에영향없음 그러나계산비용은매우줄어듬 Data Structures and Algorithms 38

39 해쉬함수의선택 결과는균등하게분포되어야함 해쉬의함수의결과크기는전체비트의길이보다커야함 연산복잡도는가능한적어야함 암호용해쉬함수를쓰는것은과함 사용예, murmur3, cityhash, fnv 등 Data Structures and Algorithms 39

40 Addkey 코드 #define FILTER_SIZE 20 #define NUM_HASHES 7 #define FILTER_BITMASK ((1 << FILTER_SIZE) - 1) unsigned char filter[filter_size_bytes]; void AddKey(unsigned char filter[], char *str) { unsigned int hash[num_hashes]; int i; get_hashes(hash, str); // 주어진 str 의해쉬결과를배열 hash 에저장 for (i = 0; i < NUM_HASHES; i++) { /* 해쉬결과를필터의크기만큼변환 (xor 활용 ) */ hash[i] = (hash[i] >> FILTER_SIZE) ^ (hash[i] & FILTER_BITMASK); /* 필터에해쉬결과저장 */ filter[hash[i] >> 3] = 1 << (hash[i] & 7); Data Structures and Algorithms 40

41 블룸필터의문제 한번삽입된키는필터에서삭제되지않음 (DeleteKey 없음 ) 더이상존재하지않는키로인해 false positive rate 증가함 이문제를해결하는것은응용프로그램이담당해야함 방법 1: 오차를허용할수있는한아무것도하지않음 방법 2: 현재사용중인키로새로운필터를생성함 방법 3: 접근된시간을정보를캐쉬로두어 1차, 2차필터를생성함 Data Structures and Algorithms 41

03_queue

03_queue Queue Data Structures and Algorithms 목차 큐의이해와 ADT 정의 큐의배열기반구현 큐의연결리스트기반구현 큐의활용 덱 (Deque) 의이해와구현 Data Structures and Algorithms 2 큐의이해와 ADT 정의 Data Structures and Algorithms 3 큐 (Stack) 의이해와 ADT 정의 큐는 LIFO(Last-in,