Google द्वारा प्राप्त विकिपीडिया और विभिन्न .edu वेबसाइटों जैसे विभिन्न स्रोतों के अनुसार, टकराव को हल करने के लिए हैश तालिका के लिए सबसे आम तरीके रैखिक या वर्गिक जांच और चेनिंग हैं। यादृच्छिक जांच का संक्षेप में उल्लेख किया गया है लेकिन अधिक ध्यान नहीं दिया गया है। मैंने एक हैश तालिका लागू की है जो टकराव को हल करने के लिए यादृच्छिक जांच का उपयोग करती है। वहाँ मान लिया जाये कि एक टक्कर है, संकल्प इस प्रकार काम करता है:हैश टेबल कार्यान्वयन में अधिक लोकप्रिय यादृच्छिक जांच क्यों नहीं है?
- पूर्ण (32-बिट) एक वस्तु का हैश एक रैखिक congruential यादृच्छिक संख्या जनरेटर बीज के प्रयोग किया जाता है।
- जनरेटर 32-बिट संख्या उत्पन्न करता है और मॉड्यूलस को यह निर्धारित करने के लिए लिया जाता है कि हैश तालिका में आगे की जांच करने के लिए कहां है।
यह बहुत अच्छा संपत्ति है कि, कितने हैश टकराव वहाँ मापांक स्थान में हैं की परवाह किए बिना, देखने और सम्मिलन बार हे होने की उम्मीद कर रहे हैं (1) जब तक पूर्ण 32-बिट में कुछ टकराव हैं हैश स्पेस चूंकि जांच अनुक्रम छद्म-यादृच्छिक है, रेखीय जांच के विपरीत, मॉड्यूलस स्पेस टकराव से कोई क्लस्टरिंग व्यवहार परिणाम नहीं होता है। चूंकि पूरी प्रणाली खुले पते पर है और कहीं भी लिंक्ड सूचियों का उपयोग नहीं करती है, इसलिए आपको चेनिंग के विपरीत, प्रत्येक प्रविष्टि पर स्मृति आवंटन करने की आवश्यकता नहीं है।
इसके अलावा, क्योंकि हैश का आकार आमतौर पर पता स्थान (32-बिट मशीनों पर 32 बिट्स) का आकार होता है, इसलिए पता स्थान में पर्याप्त वस्तुओं को फिट करना असंभव है ताकि बड़ी संख्या में हैश टकराव पूरी हो सके एक अच्छी हैशिंग योजना के तहत 32-बिट हैश स्पेस।
फिर, इस तरह के एक अलोकप्रिय टकराव समाधान रणनीति की यादृच्छिक क्यों है?
दिलचस्प। मेरा कार्यान्वयन बस गारंटी नहीं देता है कि यह कभी भी एक ही स्लॉट को एक से अधिक बार नहीं देखेगा। मैंने कुछ मोंटे कार्लो सिमुलेशन किया और निष्कर्ष निकाला कि, व्यावहारिक रूप से, यह चिंता करने के लिए बहुत बार होता है। यहां तक कि यदि आप एक ही स्लॉट को एक से अधिक बार देखने की अनुमति देते हैं, तो भी आपको ** अपेक्षित ** ओ (1) लुकअप टाइम मिल जाएगा। – dsimcha