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




hash hashmap (4)

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

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

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

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

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

कई किताबें और ट्यूटोरियल कहते हैं कि हैश तालिका का आकार सभी बाल्टी में चाबियाँ समान रूप से वितरित करने के लिए एक प्रमुख होना चाहिए। लेकिन जावा का 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