[데이터베이스] 검색-해싱(Hashing)

해싱

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

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

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

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

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

 

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

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

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

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

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

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

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

 

해싱 함수(Hashing Function)

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

2) 제곱(Mid-square)법 : 레코드 키 값을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식이다.

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

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

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

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

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

 

Overflow 해결법

1) 개방 주소법(Open Addressing) : 선형 방법이라고도 하며 Collision이 발생했을 때 순차적으로 그 다음 빈 버킷을 찾아 저장하는 방법이다.

2) 폐쇄 주소법(Close Addressing) : Overflow된 레코드들을 별도의 Overflow 영역에 저장하고 Chain(Pointer)으로 홈 버킷에 연결한다.