Bucketing builds ตารางแฮชเป็นอาร์เรย์ 2D แทนที่จะเป็นอาร์เรย์มิติเดียว ทุกรายการในอาร์เรย์มีขนาดใหญ่พอที่จะเก็บรายการ M ได้ (M ไม่ใช่ปริมาณข้อมูล แต่เป็นค่าคงที่)
ปัญหา
- สร้างพื้นที่ที่สูญเปล่าจำนวนมาก
- หากเกิน M จะต้องดำเนินการตามกลยุทธ์อื่น
- ประสิทธิภาพไม่ดีนักสำหรับการใช้งานตามหน่วยความจำ แต่ทำได้หากบัคเก็ตเป็นแบบดิสก์
สำหรับการฝากข้อมูลก็มี λ>1 ได้ อย่างไรก็ตาม ยิ่ง λ มากเท่าใด โอกาสเกิดการชนก็จะยิ่งสูงขึ้น λ>1 รับประกันว่าจะมีการชนกันอย่างน้อย 1 ครั้ง (หลักการรูนกพิราบ) ซึ่งจะช่วยเพิ่มทั้งเวลาทำงานและโอกาสที่ถังจะหมด
สำหรับตารางแฮชของตำแหน่ง M และที่เก็บข้อมูล Y ในแต่ละตำแหน่ง
- ค้นหาสำเร็จ - O(Y) กรณีที่เลวร้ายที่สุด
- ค้นหาไม่สำเร็จ - กรณีที่เลวร้ายที่สุด O(Y)
- การแทรก - O(Y) - สมมติว่าประสบความสำเร็จ การฝากข้อมูลไม่มีวิธีที่ดีในการจัดการกับการแทรกที่ไม่สำเร็จ
- การลบ - O(Y)
- ที่เก็บข้อมูล:O(M * Y)
