समझाइए कि HashMap अंदर से कैसे काम करता है, और भरने के साथ उसमें क्या होता है।

HashMap के पास buckets की एक array होती है। key का hash उसके ऊपरी bits मिलाकर फैलाया जाता है, फिर index उस hash को table की लंबाई से mask करके निकलता है, और वह लंबाई हमेशा दो की घात होती है। टकराव एक bucket में linked list बनाते हैं, और कम से कम चौंसठ के table में जिस bin में आठ या ज्यादा entries हों वह red black tree में बदल जाता है। 0.75 के load factor के बाद table दोगुना होता है और entries दोबारा hash होती हैं।

अंदर से यह bins की एक array है। key का hashCode ऊपरी bits को नीचे exclusive or करके फैलाया जाता है, और यह इसलिए मायने रखता है क्योंकि index बस hash को table length माइनस एक से mask करके निकलता है, तो बिना उस mixing के सिर्फ निचले bits ही काम आते। टकराने वाली entries उसी bin में chain बनाती हैं, और Java 8 से जो bin आठ entries से आगे बढ़ जाए, बशर्ते table कम से कम चौंसठ का हो, वह red black tree बन जाता है ताकि worst case lookup linear की जगह logarithmic रहे। यह hash collision denial of service हमलों का जवाब था। बढ़त load factor से चलती है, तो 0.75 भरने पर table दोगुना होता है और सब कुछ फिर से बंटता है, इसीलिए अगर मुझे पता है कि इसमें दस लाख entries आएंगी तो पहले से size देना मायने रखता है। व्यावहारिक नतीजे जिनकी मुझे परवाह है: keys immutable होनी चाहिए, खराब hashCode सब कुछ एक ही bin में गिरा देता है, और कनकरेंट writes table को खराब कर सकती हैं, इसलिए साझा maps के लिए बाहरी locking नहीं, ConcurrentHashMap लेता हूं।