개 념
해시 함수를 이용하여 키 값을 버킷의 슬롯에 배열시켜 빠르게 탐색하는 알고리즘
I. 해시 탐색 (Hash Search)의 개요
가. 해시 탐색 (Hash Search)의 정의
- 해시 함수를 이용하여 키 값을 버킷의 슬롯에 배열시켜 빠르게 탐색하는 알고리즘
※ 해시테이블(hash table) : 키 값을 저장하는 테이블
버킷(bucket) : 해시될 키 값의 범위, 테이블의 크기
슬롯(slot) : 한 개의 버킷에 저장될 키 값의 개수
나. 해시 탐색 (Hash Search)의 특징
- 고정길이, One Way
- O(1)의 탐색 속도
- 충돌처리 매커니즘 필요
반응형
Ⅱ. 해시 함수의 기법
가. 해시 함수의 기법
구 분 | 내 용 | |
mid-square | 식별자의 제곱 값의 가운데 값을 취함. | |
division | 나머지 연산자(modulus, %)을 이용함. - 버킷 주소의 범위 : 0 ~ m-1 - m값의 선택이 중요함. m을 소수(prime number)로 정함. |
|
digit analysis | 키 값의 자리 수를 분석하여 분포가 고른 자리 수를 해시 값으로 사용 | |
folding | 키 값을 접어서 조작하는 방법 | |
이동 접지법 |
||
경계 접지법 |
Ⅲ. 해시 탐색의 오버플로우 문제해결
가. 개방 주소법
- 해시 함수가 아닌 다른 주소를 사용하도록 허용
구 분 | 내 용 |
선형조사법 | 해시테이블을 1차원 배열로 보고 충돌이 일어나면 다음 위치에 저장 |
2차 조사법 | 해시테이블의 버킷을 조사하여 1의 제곱, 2의 제곱, 3의 제곱 순으로 새로운 위치를 찾는 방법 ht[(f(x) + i2) % b] and ht[(f(x) - i2) % b], where 0 ≤ i ≤ (b-1)/2 b: 테이블의 버킷의 수 |
재해싱 | 오버플로우 상태에서 다른 해시 함수를 사용하는 방법 |
나. 폐쇄 주소법
- 해시 함수에 의해 얻어진 주소 만을 사용
구 분 | 내 용 |
chaining | 식별자 저장 버킷의 기억장소 공간을 늘려서 해결함 /* 해시테이블(chaining)을 위한 연결리스트의 선언 */ #define MAX_CHAR 10 #define TABLE_SIZE 13 #define IS_FULL(ptr) (!(ptr)) typedef struct { char key[MAX_CHAR]; /* other fields */ } element; typedef struct list *list_ptr; typedef struct list { element item; list_ptr link; } list_ptr hash_table[TABLE_SIZE]; |
[Algorithm] 위상 정렬 (Topological Sort)
반응형