क्या होता है जब हैश मैप या हैशसेट अधिकतम क्षमता तक पहुंच जाती है?

Question

बस कुछ ही मिनट पहले मैंने "जावा में हैश मैप का अधिकतम संभव आकार" के बारे में पूछने के एक प्रश्न का उत्तर दिया। जैसा कि मैंने हमेशा पढ़ा है, हैश मैप एक बढ़ती डेटा-संरचना है। इसका आकार केवल जेवीएम मेमोरी आकार से ही सीमित है। इसलिए मैंने सोचा कि इसके आकार की कोई कठोर सीमा नहीं है और तदनुसार उत्तर दिया गया है। (समान रूप में अच्छी तरह HashSet लिए लागू है।)

लेकिन कोई मुझे कह रही है कि के बाद से आकार() HashMap की विधि देता है एक पूर्णांक, वहाँ अपने आकार की सीमा है ठीक कर दिया। एक बिल्कुल सही बिंदु। मैंने बस इसे अपने स्थानीय पर परीक्षण करने की कोशिश की लेकिन असफल रहा, मुझे हैश मैप में 2,147,483,647 से अधिक पूर्णांक डालने के लिए 8 जीबी से अधिक मेमोरी की आवश्यकता है, जो मेरे पास नहीं है।

मेरे सवाल थे:

• क्या होता है जब हम HashMap/HashSet में 2,147,483,647 +1 तत्व सम्मिलित करने का प्रयास करें?
• क्या कोई त्रुटि फेंक दी गई है?
• यदि हां, तो कौन सी त्रुटि? यदि हैश मैप/हैशसेट के साथ क्या नहीं होता है, तो यह पहले से ही मौजूदा तत्व और नया तत्व है?

अगर किसी को 16 जीबी मेमोरी के साथ मशीन तक पहुंच के साथ आशीर्वाद दिया जाता है, तो आप इसे व्यावहारिक रूप से आजमा सकते हैं। :)

Answer 1

सरणी की अंतर्निहित क्षमता 2 की शक्ति होनी चाहिए (जो 2^30 तक सीमित है) जब यह आकार पहुंच जाता है तो लोड फैक्टर प्रभावी रूप से अनदेखा होता है और सरणी बढ़ती रहती है।

इस बिंदु पर टकराव की दर बढ़ जाती है।

हैशकोड() में केवल 32-बिट्स को देखते हुए यह किसी भी मामले में बहुत बड़ा होने का अर्थ नहीं होगा।

/** 
* Rehashes the contents of this map into a new array with a 
* larger capacity. This method is called automatically when the 
* number of keys in this map reaches its threshold. 
* 
* If current capacity is MAXIMUM_CAPACITY, this method does not 
* resize the map, but sets threshold to Integer.MAX_VALUE. 
* This has the effect of preventing future calls. 
* 
* @param newCapacity the new capacity, MUST be a power of two; 
*  must be greater than current capacity unless current 
*  capacity is MAXIMUM_CAPACITY (in which case value 
*  is irrelevant). 
*/ 
void resize(int newCapacity) { 
    Entry[] oldTable = table; 
    int oldCapacity = oldTable.length; 
    if (oldCapacity == MAXIMUM_CAPACITY) { 
     threshold = Integer.MAX_VALUE; 
     return; 
    } 

    Entry[] newTable = new Entry[newCapacity]; 
    transfer(newTable); 
    table = newTable; 
    threshold = (int)(newCapacity * loadFactor); 
} 

जब आकार Integer.MAX_VALUE से अधिक हो जाता है तो यह बहती है।

void addEntry(int hash, K key, V value, int bucketIndex) { 
Entry<K,V> e = table[bucketIndex]; 
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
    if (size++ >= threshold) 
     resize(2 * table.length); 
}