বাকেটিং বিল্ড করে, হ্যাশ টেবিলকে একটি ২ডি অ্যারে হিসেবে বদলে সিংগল ডাইমেনশনাল অ্যারে বদলে। অ্যারেতে প্রতিটি এন্ট্রি বড়, যথেষ্ট M আইটেম ধারণ করার জন্য (M ডেটার পরিমাণ নয়। শুধু একটি কনস্ট্যান্ট)।
সমস্যা:
- অনেক 웨이স্টেড স্পেস তৈরি হয়।
- যদি M এক্সিড করা হয়, অন্য স্ট্র্যাটেজি বাস্তবায়ন করা লাগবে।
- মেমরি-বেসড বাস্তবায়নের জন্য সবটে ভালো পারফরমার নয় কিন্তু ডুয়েবল যদি বাকেট ডিস্ক-বেসড হয়।
বাকেটিং-এর জন্য λ>1 থাকতে দেয়া হয়। যাইহোক, যত বড় λ তত বেশি কলিশনের চান্স। λ>1 গ্যারান্টি দেয় কমপক্ষে ১টি কলিশন থাকবে (পিজন হোল প্রিন্সিপল)। এতে রান টাইম এবং বাকেট শেষ হওয়ার সম্ভাবনা দুটোই বাড়ে।
একটি হ্যাশ টেবিল M লোকেশন এবং প্রতিটি লোকেশনে Y বাকেটের জন্য:
- সফল সার্চ - O(Y) ওয়ার্স্ট কেস
- ব্যর্থ সার্চ - O(Y) ওয়ার্স্ট কেস
- ইনসার্শন - O(Y) - সাকসেস ধরে, বাকেটিং-এ নন-সাকসেসফুল ইনসার্শন হ্যান্ডেল করার ভালো উপায় নেই।
- ডিলিশন - O(Y)
- স্টোরেজ: O(M * Y)
