동적 해싱

1. 동적 해싱의 개념

동적 해싱은 데이터베이스 또는 자료 구조에서 저장된 데이터가 증가하거나 삭제됨에 따라 해시 테이블의 크기와 구조를 실시간으로 조정하는 방법이다. 전통적인 해시 테이블은 정적 크기를 갖기 때문에 데이터가 늘어나면 충돌이 빈번히 발생하거나 저장 공간이 낭비되는 문제가 발생한다. 이에 반해 동적 해싱은 이러한 문제를 해결하기 위해 설계된 기법이다. 동적 해싱은 주로 확장 가능성과 효율성을 높이기 위해 해시 테이블이 일정 수준 이상 충돌하거나 저장 용량이 다 찼을 때 크기를 자동으로 늘리거나 줄인다. 이는 데이터의 양이 유동적으로 변화하는 상황에서 해시 충돌 발생률을 낮추고 검색 성능을 유지하는데 유리하다. 실질적으로 동적 해싱은 예를 들어 16개의 데이터를 저장하는 해시 테이블이 있을 때, 충돌이 빈번히 발생하여 검색 시간이 길어질 경우, 32개 또는 그 이상으로 크기를 확장하여 충돌을 최소화하는 방식으로 작동한다. 동적 해싱은 체인 해싱과 다이내믹 해싱 기법을 포함하는데, 특히 다이내믹 해싱은 해시 테이블을 여러 개의 작은 파일 또는 디스크 블록으로 나누어 관리한다. 대표적인 알고리즘으로는 선형 …