해시 탐색 (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];

 

댓글