[Database] 해싱 기법 (hashing techniques)과 충돌 해결 기법(collision resolution)

해싱(hashing): 해시키가 주어지면 해시 함수를 사용하여 디스크 블록의 주소를 표현한다.

 

Internal hashing : 해시 테이블이 메인 메모리 주소를 찾아준다.

 

충돌(collision)

아무리 해시 함수를 잘 만든다고 해서 충돌 문제에서 자유로워질 수 있는 것은 아니다.

 

이러한 충돌을 피하기 위한 기법이 충돌 해결 기법이다.(collision resolution)

 

충돌 해결 기법은 대표적으로 3가지가 존재한다.

 

해싱 함수가 100으로 나눈 나머지 값이라고 가정한다.

 

1. 개방 주소법(open addressing)

 

충돌이 일어나게 되면 인접한 주소로 저장한다.

 

102와 202가 있다면 둘 다 해시 함수를 거친 결과가 2로 동일하다.

 

이런 경우 102는 2에 202는 3에 보관한다. 

 

이후에 103이 들어온다면 3에는 202가 존재하므로 그 다음인 4로 이동한다.

 

2. 체이닝(chaining)

 

별도의 블록을 만들어서 연결 리스트 방식으로 연결한다.

 

overflow pointer를 만들고 만약 충돌이 일어나면 포인터로 연결한다.

 

연결 리스트를 떠올리면 된다.

 

3. 다중 해싱 (multiple hashing)

 

해시 함수를 추가로 사용한다.

 

원래 해시 함수를 쓰다 충돌이 일어나면 다른 해시 함수를 한 번 더 적용한다.

 

좋은 해시 함수

좋은 해시 함수는 충돌이 일어나는 빈도를 최대한 줄이는 함수이다.

 

수학적으로 증명한 바에 따르면 다음과 같은 2가지 특성이 있다.

1. 해시 테이블의 70% 에서 90% 정도만 사용한다.
2. m으로 나눈 나머지 값을 해시 함수로 사용할 때 m은 소수인 편이 좋다.

---

external hashing : 디스크 파일에 대한 해싱을 external hashing이라고 부른다.

 

주소 공간을 버킷이라고 하며 버킷은 하나의 디스크 블록 혹은 연속된 블록(클러스터)이다.

 

해싱으로 상대적인 버킷 주소를 만든다. 상대 버킷 주소를 상응하는 디스크 블록 주소로 바꾼다.

 

여기서의 충돌은 체이닝을 변형한 방식을 사용하여 해결한다.

 

해시 함수는 100으로 나눈 나머지 값이라고 가정한다.

 

다음과 같은 버킷이 존재한다.

 

현재 101과 201은 충돌이 일어났었고 버킷에 공간이 있기에 같은 버킷에 저장되어 있다.

 

버킷이 꽉 찬 상황이고 별도로 overflow buckets을 만들어서 관리한다

 

여기서 301이 들어온다면 overflow bucket에 넣고 원래 버킷1의 pointer를 이용하여 연결한다.

여기서 401이 또 들어온다면? overflow 버킷에 넣고 다시 연결한다.

검색

여기서 레코드를 검색할 때는 먼저 버킷을 전부 뒤져본다.

 

버킷에서 나오지 않으면 pointer를 따라가서 overflow 버킷에 찾는 레코드가 있는지 확인한다.

 

pointer null이 나올때까지 pointer를 따라가는 작업을 반복하고 poiter가 null이 나온다면 존재하지 않는 것을 알 수 있다.

 

삭제

여기서 레코드를 삭제하는 것은 연결 리스트에서 값을 삭제하는 방법과 유사하다.

 

먼저 레코드를 찾은 다음 삭제한다. 그리고 삭제한 레코드의 앞에 존재하는 레코드의 pointer를 삭제한 레코드의 뒤에 연결되어 있던 레코드로 연결한다.

 

위에서 301을 삭제한다면 다음과 같은 모습이 된다.

301이 없어지고 버킷1의 pointer는 401을 가리키게 된다.

 

수정

먼저 수정할 레코드를 찾는다.

 

수정할 필드가 nonhash 필드라면 그냥 바꾼다.

 

hash 필드라면 그 레코드를 삭제하고 새로운 레코드를 삽입한다.

 

지금까지 알아본 해싱은 static hashing이다.

 

그리고 해싱을 효율적으로 하려면 해시 테이블의 70%에서 90%정도 사용해야 한다고 배웠다.

 

그런데 어느 정도의 값이 들어가는지 모른다면 이러한 static hashing은 문제가 될 수 있다.

 

계속 재구성(reorganize)하는 방법 또한 해결책이 될 수 있지만 동적으로 파일을 확장하고 싶다면 dynamic hashing을 사용해야한다.

 

다음 포스팅에서는 dynamic hashing을 공부해보려 한다.