बकेटिंग (Bucketing) हैश टेबल को एक 2D एरे के रूप में बनाता है बजाय एकल आयामी एरे (Single Dimensional Array) के। एरे में प्रत्येक एंट्री बड़ी होती है, M आइटम रखने के लिए पर्याप्त (M डेटा की मात्रा नहीं है। बस एक कॉन्स्टेंट)।
समस्याएं (Problems)
- बहुत सारी बर्बाद स्पेस (Wasted Space) बनती है।
- यदि M पार हो जाता है, तो दूसरी रणनीति लागू करने की आवश्यकता होगी।
- मेमोरी-आधारित कार्यान्वयन के लिए इतना अच्छा प्रदर्शन नहीं करता लेकिन अगर बकेट डिस्क-आधारित हैं तो संभव है।
बकेटिंग के लिए λ > 1 होना ठीक है। हालांकि, λ जितना बड़ा होगा टकराव (Collision) की संभावना उतनी अधिक होगी। λ > 1 न्यूनतम 1 टकराव की गारंटी देता है (पीजन होल सिद्धांत - Pigeon Hole Principle)। यह रन टाइम और बकेट खत्म होने की संभावना दोनों को बढ़ाएगा।
M लोकेशन और प्रत्येक लोकेशन पर Y बकेट के हैश टेबल के लिए
- सफल खोज (Successful Search) - O(Y) सबसे खराब स्थिति
- असफल खोज (Unsuccessful Search) - O(Y) सबसे खराब स्थिति
- सम्मिलन (Insertion) - O(Y) - सफलता मानकर, बकेटिंग के पास असफल सम्मिलन को संभालने का अच्छा तरीका नहीं है।
- विलोपन (Deletion) - O(Y)
- स्टोरेज: O(M * Y)
