검색-해싱(Hashing)

해싱의 개요

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

 

• 해싱은 DMA(직접 접근) 파일을 구성할 때 사용되며, 접근 속도는 빠르나 기억공간이 많이 요구됨
• 다른 방식에 비해 검색 속도가 가장 빠르다
• 삽입, 삭제 작업의 빈도가 많을때 유리한 방식
• 키-주소 변환 방법

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

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

• 버킷 : 하나의 주소를 갖는 파일의 한 구역이며 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미
• 슬롯 : 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성
• Collision(충돌 현상) : 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상
• Synonym : 충돌로 인해 같은 Home Address를 갖는 레코드들의 집합
• Overflow : 계산된 Home Address의 Bucket 내에 저장할 기억공간이 없는 상태이며, 버킷을 구성하는 슬롯이 여러개라면 충돌현상은 발생해도 Overflow는 발생하지 않을 수 있음

---

해심 함수(Hashing Function)

 

제산법

레코드 키를 해시표의 크기보다 큰 수 중에서 가장 작은 소수로 나눈 나머지를 홈 주소로 삼는 방식입니다.

h(K) = K mod Q입니다.

---

제곱법

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

 

폴딩법

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

Shift Folding : 각 부분의 값들을 왼쪽 또는 오른쪽 끝자리에 맞춰서 계산

Fold Boundary : 경계 지점을 접었을 때 마주치는 자리 그대로 계산

 

기수(Radix)변환법

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

 

대수적 코딩법

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

 

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

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

 

무작위법

난수를 발생시켜 나온 값을 홈 주소로 삼는 방식

---

Overflow 해결 방법

Collision이 발생했을 때 그 버킷에 저장할 Slot이 없으면 Overflow가 되는데, 이것을 해결하기 위해서는 다음과 같은 방법이 피료함

 

개방 주소법(Open Addressing)

선형 방법이라고도 하는데 Collision이 발생했을 때 순차적으로 그 다음 빈 버킷을 찾아 저장합니다.

 

폐쇄 주소법(Close Addressing)

Overflow된 레코드들을 별도의 Overflow 영역에 저장하고 Chain(Pointer)으로 홈버킷에 연결

• Direct Chaining : 해시표 내의 빈자리에 Overflow 레코드를 보관
• Indirect Chaining : 해시표와는 별도의 기억공간에 Overflow 레코드를 보관

재해싱(Rehashing)

Collision이 발생하면  새로운 해싱 함수로 새로운 홈 주소를 구함