[Algorithm] 해시 탐색 (Hash Search)

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];