[Algorithm] 해시테이블과 해싱함수에 대해서

 해싱이란? 

해싱은 Hash Table이라는 기억공간을 할당하고, 해시 함수(Hash Table)이라는 기억공간을 할당하고, 해시함수(Hash Function)을 이용하여 레코드 키에 대한 Hash Table내의 Home Address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식이다.

 

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

2. 다른 방식에 비해 검색 속도가 가장 빠르다.

3. 삽입 삭제 작업의 빈도가 많을 때 유리한 방식이다.

4. 키-주소 변환 방법이라고도 한다.

 

 해시테이블(HashTable) 

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

 

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

슬롯(Slot) : 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성한다.

Collision(충돌현상) : 서로 다른 두개이상의 레코드가 같은 주소를 갖는 현상이다.

Synonym : 충돌로 인해 같은 Home Address를 갖는 레코드들의 집합이다.

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

 

 

 해싱함수(Hasing Function) 

제산법

제산(Division)법은 레코드키로 해시표의 크기보다 큰 수 중에서 가장 작은소수로 나눈 나머지를 홈 주소로 삼는 방식이다.

 

제곱법

제곱법은 레코드키 값을 제곱한 후 그 중간 부분의 값을 홈주소로 삼는 방식이다.

 

폴딩법

폴딩(Folding)법은 레코드키값을 여러부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 홈주소로 삼는 방식이다.

 

기수변환법

기수변환법은 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수를 절단하고, 이를 다시 주소 범위에 맞게 조정하는 방법이다.

 

대수적 코딩법

대수적코딩법은 키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주하고, 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식이다.

 

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

계수 분석법은 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식이다.

 

무작위법

무작위(Random)법은 난수(Random Number)를 발생시켜 나온 값을 홈 주소로 삼는 방식이다.