확장 가능 해싱(Extensible Hashing)은 데이터베이스와 같은 데이터 저장 시스템에서 사용되는 해시 테이블 구조이다. 이 기술은 데이터를 효율적으로 저장하고 검색하는 데 도움이 된다.
확장 가능 해싱은 일반적인 해시 테이블과는 달리 고정된 크기의 버킷 배열을 사용하지 않는다. 대신, 해시 테이블은 초기에 작은 크기로 시작하고 필요에 따라 동적으로 확장된다. 각 버킷은 고유한 주소를 가지고 있으며, 주소의 일부는 해시 함수를 사용하여 계산된다.
기본적으로 해시 테이블은 인덱스 버킷과 데이터 버킷으로 구성된다. 인덱스 버킷에는 주소의 일부에 따라 데이터 버킷으로 연결되는 포인터가 저장된다. 데이터 버킷에는 실제 데이터가 저장된다. 처음에는 모든 인덱스 버킷이 가리키는 데이터 버킷이 비어있다.
데이터가 추가되면 해시 함수를 사용하여 주소를 계산하고, 해당 인덱스 버킷을 확인한다. 인덱스 버킷이 가리키는 데이터 버킷이 비어있으면 데이터를 해당 버킷에 저장한다. 그렇지 않은 경우, 인덱스 버킷을 확장하여 더 많은 데이터 버킷을 수용할 수 있도록 한다. 확장된 인덱스 버킷은 새로운 주소 범위를 가리키는 포인터를 추가로 저장한다.
확장 가능 해싱은 데이터베이스의 크기가 커져도 상수 시간 내에 데이터를 찾을 수 있도록 한다. 또한, 확장 가능 해싱은 동적으로 크기를 조정하므로 공간 효율적이다. 그러나 확장 가능 해싱은 충돌을 처리하기 위해 추가적인 메모리 오버헤드를 가지고 있을 수 있다.
