Bucketing বিল্ড, হ্যাশ টেবিল একটি একক মাত্রিক অ্যারের পরিবর্তে 2D অ্যারে হিসাবে। অ্যারের প্রতিটি এন্ট্রি বড়, এম আইটেম রাখার জন্য যথেষ্ট (M ডেটার পরিমাণ নয়। শুধু একটি ধ্রুবক)।
সমস্যা
- অনেক নষ্ট জায়গা তৈরি হয়।
- যদি M ছাড়িয়ে যায়, অন্য কৌশল প্রয়োগ করতে হবে।
- মেমরি ভিত্তিক বাস্তবায়নের জন্য এত ভাল পারফর্মার নয় তবে বালতিগুলি ডিস্ক-ভিত্তিক হলে তা সম্ভব৷
বাকেটিংয়ের জন্য λ>1 থাকা ঠিক। যাইহোক, যত বড় λ সংঘর্ষের সম্ভাবনা তত বেশি। λ>1 গ্যারান্টি দেয় যে ন্যূনতম 1টি সংঘর্ষ হবে (কবুতরের গর্ত নীতি)। এটি রান টাইম এবং বালতি ফুরিয়ে যাওয়ার সম্ভাবনা উভয়ই বাড়িয়ে তুলবে।
প্রতিটি অবস্থানে M অবস্থান এবং Y বালতিগুলির একটি হ্যাশ টেবিলের জন্য
- সফল অনুসন্ধান - O(Y) সবচেয়ে খারাপ ক্ষেত্রে
- অসফল অনুসন্ধান - O(Y) সবচেয়ে খারাপ ক্ষেত্রে
- সফল সন্নিবেশ - O(Y) - সাফল্য ধরে নিলে, অ-সফল সন্নিবেশগুলি পরিচালনা করার জন্য বাকেটিংয়ের ভাল উপায় নেই৷
- মোছা - O(Y)
- স্টোরেজ:O(M * Y)
