हैश मैप की आवश्यकता क्यों है कि प्रारंभिक क्षमता दो की शक्ति हो?

Question

मैं जावा के HashMap स्रोत कोड के माध्यम से जा रहा था जब मैं निम्नलिखित

//The default initial capacity - MUST be a power of two. 
static final int DEFAULT_INITIAL_CAPACITY = 16; 

मेरा प्रश्न देखा क्यों इस आवश्यकता को पहली जगह में मौजूद है? मैं यह भी देखना है कि निर्माता जो एक कस्टम क्षमता के साथ एक HashMap बनाने की अनुमति देता है दो का एक बिजली में परिवर्तित कर:

int capacity = 1; 
while (capacity < initialCapacity) 
    capacity <<= 1; 

क्यों क्षमता हमेशा की तरह ही दोनों में से एक शक्ति होने के लिए करता है?

इसके अलावा, जब स्वचालित रीहैशिंग किया जाता है, तो वास्तव में क्या होता है? हैश फ़ंक्शन भी बदल गया है?

Answer 1

मानचित्र को किसी भी दिए गए कुंजी के लिए उपयोग करने के लिए कौन सी आंतरिक तालिका अनुक्रमणिका का उपयोग करना है, [0, table.length) श्रेणी में किसी भी int मान (नकारात्मक हो सकता है) मैप करना है। जब table.length दो की एक शक्ति है, कि वास्तव में किया जा सकता है सस्ते में है - और है, indexFor में:

static int indexFor(int h, int length) { 
    return h & (length-1); 
} 

एक अलग तालिका लंबाई के साथ

, आप एक शेष गणना और यकीन है कि यह गैर है बनाने के लिए आवश्यकता होगी नकारात्मक यह निश्चित रूप से एक माइक्रो-ऑप्टिमाइज़ेशन है, लेकिन शायद एक वैध एक :)

इसके अलावा, जब स्वचालित रीहैशिंग किया जाता है, तो वास्तव में क्या होता है? हैश फ़ंक्शन भी बदल गया है?

यह मेरे लिए बिल्कुल स्पष्ट नहीं है कि आपका क्या मतलब है। एक ही हैश कोड का उपयोग किया जाता है (क्योंकि वे प्रत्येक कुंजी पर hashCode पर कॉल करके गणना की जाती हैं) लेकिन तालिका की लंबाई बदलने के कारण उन्हें टेबल के भीतर अलग-अलग वितरित किया जाएगा। उदाहरण के लिए, जब तालिका की लंबाई 16 होती है, तो 5 और 21 के हैश कोड तालिका प्रविष्टि में संग्रहित होते हैं 5. जब तालिका की लंबाई 32 तक बढ़ जाती है, तो वे अलग-अलग प्रविष्टियों में होंगे।

Answer 2

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

इसके लिए आपको जावा के HashMap कार्यान्वयन में एक और बहुत ही महत्वपूर्ण विधि मिल जाएगी, जो hash(int) है, जो खराब हैशकोड की क्षतिपूर्ति करता है।