Điều gì sẽ xảy ra khi đạt được dung lượng tối đa HashMap hoặc HashSet?

Question

Chỉ cần một vài phút sau tôi đã trả lời một câu hỏi hỏi về "kích thước có thể tối đa của HashMap trong Java". Như tôi đã luôn đọc, HashMap là cấu trúc dữ liệu có thể phát triển. Kích thước của nó chỉ bị giới hạn bởi kích thước bộ nhớ JVM. Do đó tôi nghĩ rằng không có giới hạn cứng về kích thước của nó và được trả lời tương ứng. (Điều này cũng áp dụng đối với HashSet là tốt.)

Nhưng một người nào đó sửa lại cho tôi nói rằng kể từ khi kích thước () phương pháp HashMap trả về một int, có là một giới hạn về kích thước của nó. Một điểm hoàn toàn chính xác. Tôi chỉ cố gắng để thử nghiệm nó trên địa phương của tôi nhưng không thành công, tôi cần nhiều hơn 8GB bộ nhớ để chèn hơn 2.147.483.647 số nguyên trong HashMap, mà tôi không có.

Câu hỏi của tôi là:

• xảy ra khi chúng ta cố gắng chèn 2,147,483,647 + 1 phần tử trong HashMap/HashSet gì?
• Có lỗi xảy ra không?
• Nếu có, lỗi nào? Nếu không phải điều gì xảy ra với HashMap/HashSet, các thành phần đã có của nó là và phần tử mới?

Nếu ai đó được hưởng quyền truy cập vào máy có bộ nhớ 16GB, bạn có thể dùng thử thực tế. :)

Answer 1

Năng lực tiềm ẩn của mảng phải là một sức mạnh của 2 (được giới hạn đến 2^30) Khi kích thước này được đạt tới yếu tố tải trọng bị bỏ qua một cách hiệu quả và mảng ngừng phát triển.

Tại thời điểm này tỷ lệ va chạm tăng.

Với hashCode() chỉ có 32-bit nó sẽ không làm cho tinh thần để phát triển nhiều lớn này trong mọi trường hợp.

/** 
* 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); 
} 

Khi kích thước vượt quá Integer.MAX_VALUE nó tràn.

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); 
}