44. 동적 해싱

지금까지의 해싱은 정적 해싱으로 해시 테이블의 크기가 고정되어 있는 방식이었다.

하지만 동적해싱은 해시 테이블의 크기를 변경하면서 데이터의 분포를 최적화하는 방식이다.

 

디렉터리가 있는 동적 해싱

동적해싱의 한 형태로, 해시 테이블의 버킷에 여러 개의 슬롯을 가지고 있는 방식이다.

각 버킷은 고정된 개수의 슬롯을 가지며, 버킷의 크기는 변경되지 않는다.

따라서 버킷의 크기조정을 위한 재해싱을 수행할 필요가 없어 동적해싱의 장점을 유지하면서 일정한 메모리 공간을 유지할 수 있다.

 

데이터 삽입 및 검색은 다음과 같은 절차를 따른다.

 1. 해시 함수를 이용하여 데이터의 해시 값을 계산한다.

 2. 디렉토리에서 해시 값에 해당하는 버킷의 포인터를 가져옵니다.

 3. 버킷에 데이터 슬롯이 비어있는지 확인한다. 비어있다면 해당 슬롯에 저장, 비어있지 않다면 충돌

 4. 모든 슬롯이 사용 중이거나 적정 슬롯을 찾지 못한 경우, 버킷을 분할하고 디렉터리를 업데이트한다.

---

디렉터리가 없는 동적 해싱

동적 해싱의 다른 형태로 디렉터리가 없는 동적 해싱은 해시 테이블의 버킷을 동적으로 조정하면서 데이터를 저장하는 방식이다.

따라서 디렉토리를 관리하는 추가적인 오버헤드가 없으며, 버킷의 크기를 조정하는 것만으로 충분하다.

디렉토리가디렉터리가 없는 동적 해싱도 디렉터리가 있는 해싱과 유사한 절차로 동작한다.