[Information]/[Algorithm]

[Algorithm] 해시 탐색 (Hash Search)

starterr 2024. 7. 24. 17:10

개 념

해시 함수를 이용하여 키 값을 버킷의 슬롯에 배열시켜 빠르게 탐색하는 알고리즘

 

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] 백트래킹 알고리즘

 

[Algorithm] 백트래킹 알고리즘

개념깊이우선탐색(DFS)기법에 Pruning 기법을 적용하여 Promising 검토와 Back Tracking 을 활용하여 탐색 성능을 개선한 알고리즘  I. 백트래킹(Back Tracking) 알고리즘의 개요   가.  백트래킹 알고리즘

infoofit.tistory.com

 

[Algorithm] 위상 정렬 (Topological Sort)

 

[Algorithm] 위상 정렬 (Topological Sort)

Topological Sort (위상 정렬)Topological sort는 Direct Acyclic Graph 의 경우에서 문제를 해결하는 방법이다. 방향이 존재하는 그래프에서 각 vertex의 선행 순서 정보를 유지하면서 모든 vertex를 탐색하는 알고

infoofit.tistory.com

 

 

반응형