[컴공,자료구조2] 확장 해쉬의 구현

1. 확장 해쉬 개요

확장 해쉬는 동적 해쉬 기법의 하나로, 파일 시스템과 데이터베이스에서 대량의 데이터를 효율적으로 저장하고 검색하기 위해 개발된 자료구조이다. 기존의 해쉬 테이블은 고정된 크기를 가지기 때문에 충돌이 발생하거나 테이블의 크기를 미리 예측하기 어려운 경우 비효율적일 수 있다. 이러한 문제를 해결하기 위해 확장 해쉬는 테이블이 꽉 차거나 충돌이 많아질 때마다 구조를 확장하여 성능 저하를 최소화한다. 확장 해쉬는 기본적으로 디렉토리와 용량이 유연하게 조절되는 데이터 블록으로 구성되며, 해시 함수는 일반적으로 가변적인 비트 수를 활용한다. 확장 해쉬의 핵심 아이디어는 디렉토리 크기를 동적으로 조절하여, 데이터가 늘어나거나 충돌이 많아질 때마다 디렉토리 내 항목들을 재배열하고 필요한 만큼의 디스크 공간을 확대하는 것이다. 이를 통해 해시 테이블의 크기와 검색 속도를 자동적으로 조절할 수 있으며, 대용량 데이터 처리에 유리하다. 실질적인 구현에서는 디렉토리의 각 항목이 가리키는 데이터 블록이 해시값의 앞부분 일정 비트만을 이용하여 구분되며, 충돌 발생 시 디렉토리 크기(비트 수)를 늘리거나 줄임으로써…