검색-해싱(Hashing)

해싱의 개요

해싱은 Hash Table이라는 기억공간을 할당하고, 해시함수(Hash Function)를 이용하여 레코드 키에 대한 Hash Table

내의 Home address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색작업을 수행하는 방식

- 해싱은 DAM(직접접근)파일을 구성할 때 사용되며, 접근 속도는 빠르나 기억공간이 많이 요구

- 다른 방식에 비해 검색 속도가 가장 빠름

- 삽입, 삭제 작업의 빈도가 많을 경우 유리

- 키-주소 변환 방법이라고도 함

해시테이블(Hash Table, 해시표)

-해시테이블은 레코드를 한 개 이상 보관할 수 있는 bucket들로 구성된 기억공간으로, 보조기억장치에 구성할 수 도 있고 주기억장치에 구성할 수 도 있다.

버킷(Bucket)

- 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미한다.

슬롯(Slot)

- 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 완성한다

Collision(충돌현상)

서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상

Synonym 

충돌로 인해 같은 Home Address를 갖는 레코드들의 집합

Overflow 

계산된 Home Address의 Bucket 내에 저장할 기억공간이 없는 상태로, Bucket을 구성하는 Slot이 여러 개일 때 Collision은 발생해도 Overflow는 발생하지 않을 수도 있다.

해싱함수(Hashing Function)

제산법(Division)

제곱법(Mid-Square)

폴딩법(Folding)

대수적코딩법(Algebraic Coding)

기수 변환법(Radix)

계수 분석법(숫자 분석법) (Digit Analsys)

무작위법(Random)