버킷팅은 해시 테이블을 1차원 배열 대신 2D 배열로 빌드합니다. 배열의 모든 항목은 크기가 커서 M 항목을 담기에 충분합니다(M은 데이터 양이 아니라 상수임).
문제
- 많은 낭비되는 공간이 생성됩니다.
- M이 초과되면 다른 전략을 구현해야 합니다.
- 메모리 기반 구현에서는 그다지 좋은 성능을 발휘하지 못하지만 버킷이 디스크 기반이면 가능합니다.
버켓팅의 경우 λ>1이면 괜찮습니다. 그러나 λ가 클수록 충돌 가능성이 높아집니다. λ>1은 최소 1회의 충돌이 있음을 보장합니다(비둘기 구멍 원리). 그러면 실행 시간과 버킷 부족 가능성이 모두 향상됩니다.
M개의 위치와 각 위치의 Y 버킷의 해시 테이블의 경우
- 성공적인 검색 - O(Y) 최악의 경우
- 실패한 검색 - O(Y) 최악의 경우
- 삽입 - O(Y) - 성공을 가정하면 버켓팅은 실패한 삽입을 처리하는 좋은 방법이 없습니다.
- 삭제 - O(Y)
- 저장소:O(M * Y)