बकेटिंग बनाता है, हैश तालिका एकल आयामी सरणी के बजाय 2D सरणी के रूप में। सरणी में प्रत्येक प्रविष्टि बड़ी है, एम आइटम रखने के लिए पर्याप्त है (एम डेटा की मात्रा नहीं है। बस स्थिर है)।
समस्याएं
- बहुत सारे व्यर्थ स्थान बनाए जाते हैं।
- यदि एम पार हो गया है, तो दूसरी रणनीति को लागू करने की आवश्यकता होगी।
- स्मृति आधारित कार्यान्वयन के लिए इतना अच्छा प्रदर्शन नहीं है, लेकिन यदि बकेट डिस्क-आधारित हैं तो संभव है।
बकेटिंग के लिए>1 का होना ठीक है। हालांकि, बड़ा λ टक्कर की संभावना अधिक है।>1 गारंटी देता है कि न्यूनतम 1 टक्कर (कबूतर छेद सिद्धांत) होगी। इससे रन टाइम और बाल्टी खत्म होने की संभावना दोनों बढ़ जाएगी।
M स्थानों की हैश तालिका और प्रत्येक स्थान पर Y बकेट के लिए
- सफल खोज - O(Y) सबसे खराब स्थिति
- असफल खोज - O(Y) सबसे खराब स्थिति
- प्रविष्टि - O(Y) - सफलता मानते हुए, बकेटिंग के पास गैर-सफल सम्मिलन को संभालने का अच्छा तरीका नहीं है।
- हटाना - O(Y)
- भंडारण:O(M * Y)