java - जावा: हैश मैप आकार के रूप में एक "प्राइम" नंबर या "दो की शक्ति"?




hash hashmap (4)

प्रदर्शन / गणना समय बिंदु से दृश्य के दो आकारों की गणना केवल बिट मास्किंग के साथ की जा सकती है जो पूर्णांक विभाजन से तेज़ है जिसे अन्यथा आवश्यक होगा।

कई किताबें और ट्यूटोरियल कहते हैं कि हैश तालिका का आकार सभी बाल्टी में चाबियाँ समान रूप से वितरित करने के लिए एक प्रमुख होना चाहिए। लेकिन जावा का HashMap हमेशा एक आकार का उपयोग करता है जो दो की शक्ति है। क्या यह एक प्राइम का उपयोग नहीं करना चाहिए? क्या बेहतर है, हैश टेबल आकार के रूप में "प्राइम" या "दो की शक्ति"?


मानक hash मैप कार्यान्वयन में hash विधि है जो उस गड़बड़ी से बचने के लिए आपके ऑब्जेक्ट के हैशकोड को रीहाश करती है। hash() विधि से पहले टिप्पणी पढ़ता है:

/**
 * Retrieve object hash code and applies a supplemental hash function to the
 * result hash, which defends against poor quality hash functions.  This is
 * critical because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */

यह जानने का एकमात्र तरीका है कि प्राइम और पावर-टू-दो के बीच कौन सा बेहतर है, इसे बेंचमार्क करना है।

कई साल पहले, जब एक असेंबलर लिखते थे जिसका प्रदर्शन प्रतीकात्मक तालबे लुकअप पर दृढ़ता से निर्भर करता था, तो मैंने जेनरेट किए गए पहचानकर्ताओं के एक बड़े ब्लॉक का उपयोग करके इसका परीक्षण किया। यहां तक ​​कि एक बेवकूफ मैपिंग के साथ, मैंने पाया कि अपेक्षाकृत कम से कम बिजली की बाल्टी के समान आकार की तुलना में कम से कम वितरण और लंबी श्रृंखलाएं थीं। बिट मास्किंग द्वारा बाल्टी चयन की गति की वजह से यह अभी भी तेजी से भाग गया है।

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

इसी कारण से, मुझे यकीन है कि रीहाश और पावर ऑफ-टू-साइज सामान्य जावा हैश मैप्स के लिए बाल्टी की एक बड़ी संख्या के मुकाबले बेहतर प्रदर्शन देता है।


हैश कोड के शीर्ष बिट्स से दो प्रभावशाली मास्क की शक्ति का उपयोग करना। इस प्रकार एक खराब गुणवत्ता वाले हैश फ़ंक्शन इस परिदृश्य में विशेष रूप से बुरी तरह प्रदर्शन कर सकता है।

जावा के हैश hashCode() ऑब्जेक्ट के hashCode() कार्यान्वयन को अविश्वासित करके और इसके परिणामस्वरूप हैशिंग के दूसरे स्तर को लागू करके इसे कम करता है :

किसी दिए गए हैशकोड पर एक पूरक हैश फ़ंक्शन लागू करता है, जो खराब गुणवत्ता वाले हैश फ़ंक्शन के खिलाफ बचाव करता है। यह महत्वपूर्ण है क्योंकि हैश मैप दो-लंबाई वाली हैश तालिकाओं का उपयोग करता है, जो अन्यथा हैशकोड के लिए टकराव का सामना करते हैं जो कम बिट्स में भिन्न नहीं होते हैं।

यदि आपके पास एक अच्छा हैश फ़ंक्शन है, या हैश HashMap समान कुछ करता है, तो इससे कोई फर्क नहीं पड़ता कि आप टेबल आकार के रूप में प्राइम नंबर आदि का उपयोग करते हैं या नहीं।

यदि, दूसरी तरफ, हैश फ़ंक्शन अज्ञात या खराब गुणवत्ता का है, तो एक प्राइम नंबर का उपयोग करना एक सुरक्षित शर्त होगा। हालांकि, यह गतिशील रूप से आकार देने वाली टेबल चालक को कार्यान्वित करने के लिए करेगा, क्योंकि अचानक आपको स्थिर कारक द्वारा आकार को गुणा करने के बजाय प्राइम नंबरों का उत्पादन करने में सक्षम होना चाहिए।







hashcode