Bucketing xây dựng bảng băm (hash table) như một mảng 2 chiều thay vì mảng 1 chiều. Mỗi mục trong mảng đủ lớn để chứa M mục (M không phải lượng dữ liệu, chỉ là hằng số).
Vấn đề:
- Tạo ra nhiều không gian lãng phí.
- Nếu vượt quá M, cần chiến lược khác.
- Không phải performer tốt cho cài đặt dựa trên bộ nhớ nhưng khả thi nếu bucket dựa trên đĩa (disk-based).
Đối với bucketing, λ > 1 là được chấp nhận. Tuy nhiên, λ càng lớn thì cơ hội va chạm càng cao. λ > 1 đảm bảo có ít nhất 1 va chạm (nguyên lý cái hộp bồ câu). Điều đó làm tăng cả thời gian chạy và khả năng hết bucket.
Đối với bảng băm M vị trí và Y bucket tại mỗi vị trí:
- Tìm kiếm thành công (Successful Search) - O(Y) trường hợp xấu nhất.
- Tìm kiếm thất bại (Unsuccessful Search) - O(Y) trường hợp xấu nhất.
- Chèn (Insertion) - O(Y) - giả định thành công, bucketing không có cách tốt xử lý chèn thất bại.
- Xóa (Deletion) - O(Y).
- Lưu trữ (Storage): O(M * Y).