क्यों नेट शब्दकोश प्राइम संख्याओं का आकार बदलते हैं?

Question

this question के अनुसार एक .Net शब्दकोश प्राइम संख्याओं को आवंटित स्थान का आकार देता है जो कम से कम वर्तमान आकार से दोगुना होता है। प्राइम संख्याओं का उपयोग करना क्यों महत्वपूर्ण है और वर्तमान आकार में केवल दो बार नहीं? (मैंने जवाब खोजने के लिए अपनी Google-fu शक्तियों का उपयोग करने की कोशिश की, लेकिन इसका कोई फायदा नहीं हुआ)

Answer 1

यह choosing a good hashing function से संबंधित एक एल्गोरिदम कार्यान्वयन विवरण है और जो समान वितरण प्रदान करता है। एक गैर-वर्दी वितरण टकराव की संख्या बढ़ता है, और उन्हें हल करने की लागत बढ़ जाती है।

Answer 2

प्राइम संख्याओं के गणित के कारण। उन्हें विभिन्न छोटी संख्याओं में फ़ैक्टर नहीं किया जा सकता है। जब आप संग्रहित वस्तुओं से हैश संख्या को विभाजित करते हैं तो आपको एक समान वितरण मिलता है। यदि आपके पास वस्तुओं के आधार पर कोई प्रमुख संख्या नहीं है, तो वितरण भी नहीं हो सकता है।

Answer 3

बाल्टी जिसमें एक तत्व रखा जाता है (hash & 0x7FFFFFF) % capacity द्वारा निर्धारित किया जाता है। इसे समान रूप से वितरित करने की आवश्यकता है। इससे यह चलता है कि यदि एकाधिक प्रविष्टियां जो एक निश्चित आधार (hash1 = x1 * base, hash2 = x2 * base, ...) पर हैं, जहां base और capacity coprime नहीं हैं (सबसे बड़ा आम divisor> 1) कुछ स्लॉट का उपयोग खत्म हो गया है, और कुछ कभी नहीं हैं उपयोग किया गया। चूंकि प्राइम नंबर खुद को छोड़कर किसी भी संख्या में कॉप्रिम हैं, इसलिए उनके पास एक अच्छा वितरण प्राप्त करने की अपेक्षाकृत अच्छी संभावनाएं हैं।

इसकी एक विशेष रूप से अच्छी संपत्ति यह है कि capacity > 30 हैशकोड में प्रत्येक बिट का योगदान अलग है। तो यदि हैश की भिन्नता केवल कुछ बिट्स में केंद्रित है तो यह अभी भी एक अच्छा वितरण का कारण बन जाएगी। यह बताता है कि क्यों क्षमताएं दो की शक्तियां खराब हैं: वे उच्च बिट्स को मुखौटा करते हैं। संख्याओं का एक समूह जहां केवल उच्च बिट अलग हैं, वह असंभव नहीं है।

व्यक्तिगत रूप से मुझे लगता है कि वे उस कार्य को बुरी तरह चुनते हैं। इसमें एक महंगा मॉड्यूलो ऑपरेशन होता है और यदि प्रविष्टियां प्राइम-क्षमता के गुणक हैं तो इसका प्रदर्शन टूट जाता है। लेकिन यह ज्यादातर अनुप्रयोगों के लिए काफी अच्छा लगता है।