자료구조 - 해시의동작 Chapter 5. HASH

목차

1. General Idea
2. Hash Function
3. Separate Chaining
4. Open Addressing
5. Extendible Hashing

본문내용

5.1 General Idea
일반적인 자료구조들은 자료수 N이 커짐에 따라 평균검색길이도 길어졌다. 하지만 해쉬검색법은 자료수 N에 관계없이 상수의 검색길이를 가지는 매우 빠른 검색 방법이다. 해쉬검색법은 메모리 내부에서 검색하는 내부검색에도 사용되지만 디스크상에서도 아주 빠른 속도로 검색해 주는 외부검색에도 사용되는 중요한 알고리즘이다.

 용어 정리
 해쉬 테이블 (hash table)
 원소값으로부터 저장된 위치를 계산할 수 있는 테이블 구조
 식별자(원소)는 고정된 크기(m)의 해쉬 테이블 ht[m]에 저장
 해슁 (hashing)
 해쉬 테이블을 이용한 탐색, 삽입, 제거 기법
 해쉬 함수 (hash function)
 식별자 x의 테이블 내 위치 결정을 위한 수학 함수
 0<=h(x)<=m-1
 해쉬 주소
 해쉬 함수에 의해 결정된 식별자의 저장 주소
 버켓 (bucket)
 해쉬 테이블의 각 엔트리 ht[i], 0<= i<=m-1
 슬롯 (slot)
 식별자가 저장되는 버켓의 단위 (하나의 버켓은 여러 슬롯으로 구성)
 충돌 (collision)
 해쉬 함수 h가 서로 다른 식별자를 동일한 버켓으로 사상했을 때,
 즉, h(x1)=h(x2), x1!=x2일 때 충돌이 발생했다고 함
 동의 식별자 (synomym)
 충돌을 일으킨 서로 다른 x1, x2
 오버플로우 (overflow)
 식별자가 모든 슬롯이 찬 버켓에 사상될 경우
 버켓당 슬롯 수 s=1이면 충돌과 오버플로우는 동시에 발생

 탐색 시간
 오버플로우가 없다고 가정
 h(x)계산 후, 하나의 버켓 내에서 x를 탐색
 버켓당 슬롯수는 작으므로 선형 탐색
 버켓의 슬롯수는 전체 식별자 수 n과는 무관

5.2 Hash Function
 식별자를 해쉬 테이블의 주소로 변환
 해슁의 효율성은 사용한 해쉬 함수와 밀접
 충돌을 최소화 해야 함
 쉽게 계산할 수 있어야 함

참고 자료

없음