해시 탐색 (Hash Search)

구분

내용

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