버킷팅(Bucketing)이란 무엇인가?
버킷팅은 해시 테이블(hash table)을 단일 1차원 배열이 아닌 2차원 배열 형태로 구성하는 기법입니다. 이때 배열의 각 항목(entry)은 M개의 데이터를 담을 수 있을 만큼 충분히 크게 설계됩니다. 여기서 M은 전체 데이터의 양이 아니라, 하나의 버킷에 저장할 수 있는 최대 항목 수를 나타내는 상수입니다.
버킷팅의 주요 문제점
- 공간 낭비: 각 버킷이 고정된 크기(M개의 슬롯)를 가지므로, 실제로 사용되지 않는 빈 공간이 많아져 메모리가 비효율적으로 소모됩니다.
- 오버플로우 처리: 한 버킷에 M개를 초과하는 데이터가 유입되면, 이를 처리하기 위한 별도의 전략(예: 체이닝 확장, 재해싱 등)을 추가로 구현해야 합니다.
- 메모리 기반 구현에 부적합: 메인 메모리 기반 구현에서는 성능이 좋지 않지만, 버킷을 디스크 기반으로 운영한다면 충분히 실현 가능한 방식입니다.
부하율(Load Factor, λ)과 충돌
일반적인 해시 테이블에서는 부하율 λ가 1을 초과하면 안 되지만, 버킷팅에서는 λ > 1이 허용됩니다. 다만 λ가 커질수록 충돌(collision)이 발생할 확률 역시 함께 높아집니다.
특히 λ > 1인 경우, 비둘기집 원리(pigeonhole principle)에 따라 최소 1회 이상의 충돌이 반드시 발생합니다. 이는 실행 시간 증가와 버킷 공간 부족 가능성을 동시에 높이는 요인이 됩니다.
버킷팅의 시간 복잡도
M개의 위치(location)와 각 위치당 Y개의 버킷을 가지는 해시 테이블을 가정할 때, 주요 연산의 시간 복잡도는 다음과 같습니다.
- 성공적인 탐색(Successful Search): 최악의 경우 O(Y)
- 실패한 탐색(Unsuccessful Search): 최악의 경우 O(Y)
- 삽입(Insertion): O(Y) — 삽입이 성공한다고 가정하며, 실패한 삽입을 효과적으로 처리하는 방법이 마련되어 있지 않음
- 삭제(Deletion): O(Y)
- 저장 공간(Storage): O(M × Y)
정리
버킷팅은 구조가 단순하고 디스크 기반 시스템에는 적합한 해시 테이블 구성 방식입니다. 그러나 고정된 버킷 크기로 인한 공간 낭비와 오버플로우 처리 문제라는 트레이드오프를 감수해야 하며, 부하율 관리를 통해 충돌 발생 가능성을 신중하게 제어하는 것이 중요합니다.