Hashing(해싱)

해싱은 파일의 접근을 O(1)로 보장해주는 자료구조입니다.

 

Hash Function을 통해 받은 해시값으로 매핑하여 사용하게됩니다. 이때, 해시함수 값이 같은 두 개 이상을 동의어(Synonyms) 라고 합니다.

 

동의어가 아예 나오지 않게끔 완벽한 해싱 알고리즘은 극히 어려워서 사실상 충돌이 일어날 수 밖에 없습니다.

 

그렇다면 충돌을 줄이는 방법밖에 없는데 이를 위해선 다음 3가지 방법을 고려할 수 있습니다.

• 레코드 분산 저장
• 추가 메모리 공간 사용
• 각 주소 공간에 하나 이상의 레코드 저장 (버킷 방식)

우선 해시 알고리즘에 대해서 서술하겠습니다.

 

해시 알고리즘은 다음과 같은 방법들이 존재합니다.

• 키 패턴 분석
• 키 일부를 포갬
• 나누기 (주로 소수로 나눗셈)
• 키를 제곱 후 중간 부분을 주소로 취함
• 진법 변환

해시 함수를 통해 레코드들이 매핑될 때, 레코드들이 주소 공간에 얼마나 분산되는지 예측을 위해 포아송 함수를 해싱에 적용합니다.

 

포아송 함수는 다음과 같습니다.

 

p(x) = ((r|N)^x * e^-(r|N)) / x!

 

포아송 함수에서 p(x)는 모든 레코드에 해시 함수가 적용된 후, 주어진 주소에 x개의 레코드가 할당될 확률을 의미하며, N은 주소의 수, r은 저장할 레코드의 수, x는 주어진 주소에 해싱을 통해 할당될 레코드의 수를 의미합니다.

 

N개의 주소 공간에 대해서 x개의 레코드가 할당되는 주소의 기대 수는 Np(x)로 정리할 수 있습니다.

 

충돌 현상을 줄이는 다른 방법으로 추가 메모리 공간을 사용하는 방법이 있는데 이를 계산하기위해 패킹 밀도(Packing Density)를 사용합니다. 패킹 밀도는 저장될 레코드의 수(r)와 주소의 수(N)에 대한 비율로 낮을수록 overflow가 적게 발생합니다.

 

충돌 해결 기법으로는 먼저 선형조사법 (Progressive Overflow Linear Probing)이 있습니다. O(N)을 보장하지만, N의 시간은 탐색에 있어 시간이 오래걸립니다. 대신 단순하다는 강점을 가지고 있습니다.

 

다음으로 버킷 기법입니다. 버킷은 같은 주소를 가지는 레코드들의 집합체로, 한번의 Disk I/O로 접근을 가능하게 해줍니다. 버킷을 사용하면, 버킷을 사용하지 않을때랑 비교해서 같은 패킹 밀도를 가지지만, overflow 레코드가 더 적게 나오는 결과를 보여줍니다.

 

구현할 때 관리해야할 점은 다음과 같습니다.

• 해쉬 파일은 RRN으로 접근 가능하도록 고정길이의 레코드로 저장합니다.
• 해쉬 파일을 초기화 해둡니다.

첫번째 내용은 해시 공간의 크기를 미리 고정하고, 레코드의 삽입, 삭제, 수정 등으로 레코드 주소와 홈주소 사이의 빈공간이 발생하지 않게끔 하는 것입니다.

 

두번째 내용은 해시 파일의 모든 주소 공간을 미리 확보하고, 레코드 삽입 시 주소 공간에 저장하는 것으로, 물리적 연속성을 극대화합니다. 이렇게 관리하면 선형주소법에서 유리하나, 물리적 연속성을 구현해내기는 다소 어렵습니다.

 

레코드가 삭제될때는 다음 내용을 고려해야합니다.

• 삭제된 빈 공간은 레코드 검색에 방해가 되면 안됩니다.
• 삭제된 공간은 다른 레코드 삽입 시 재사용이 가능해야합니다.

따라서, 삭제된 공간에 tombstone을 삽입합니다. 탐색 시 tombstone을 만나면, 멈추지 않고 진행하며 삽입시에는 tombstone 자리에 삽입합니다.

 

삭제가 많이 일어나면서 tombstone이 많아지면 탐색시간이 늘어나는 문제점이 생기게 되는데, 이를 해결하기 위해서는 삭제 시마다 재분배를 수행하거나 해시 파일의 재구성 혹은 다른 충돌 처리 방법을 구상하는 정도가 있습니다.

 

다른 해싱 방법으로는 먼저 이중 해싱이 있습니다. 이중 해싱은 해시 함수1의 결과를 해시 함수2로 다시 해싱하거나 해시 함수1의 결과에 상수 C를 더하는 방법입니다. 이때 상수 C는 주로 소수를 사용합니다.

 

그리고 체인법 (Chained Progressive Overflow)이 있습니다. 이 방법은 선형조사법보다 평균검색길이가 짧은 장점이 있습니다. 하지만, 홈주소가 다른 레코드를 가리키는 문제점이 존재합니다. 이를 해결하기 위해 overflow된 내용을 체인할 때 별도의 추가공간으로 연결합니다. 이방법은 별도의 추가 공간이 다른 실린더에 있을 경우 탐색 시간이 오래걸리는 문제점을 가지고 있습니다.