HashMap 또는 HashSet 최대 용량에 도달하면 어떻게됩니까?

Question

잠깐만 내가 "가능한 최대 크기의 HashMap in Java"에 대한 질문에 대답했다. 항상 읽었던 것처럼 HashMap은 확장 가능한 데이터 구조입니다. 크기는 JVM 메모리 크기에 의해서만 제한됩니다. 따라서 크기에 대한 제한이없고 그에 따라 대답했다고 생각했습니다. (동일.뿐만 아니라 HashSet에 적용 가능하다)

그러나 누군가의 HashMap의 크기() 방법은 INT를 반환하기 때문에, 이은 크기에 제한이 말하는 저를 수정했습니다. 완벽하게 정확한 지점. 방금 내 로컬에서 테스트를 시도했지만 실패했습니다. HashMap에 2,147,483,647 개 이상의 정수를 삽입하려면 8GB 이상의 메모리가 필요합니다.

내 질문을했다 :

• 우리가 의 HashMap/HashSet의에 2,147,483,647 + 1의 요소를 삽입 할 때 어떻게됩니까?
• 오류가 발생 했습니까?
• 예인 경우 오류가 있습니까? HashMap/HashSet에 어떤 일이 발생하지 않았습니까? 이미 기존 요소 인 과 새 요소가 있습니까?

누군가가 16GB 메모리라고 말하는 컴퓨터에 대한 액세스 권한이 있다면 실제로 시도해 볼 수 있습니다. :)

Answer 1

배열의 기본 용량은 2의 제곱 수 (2^30으로 제한됨) 여야합니다.이 크기에 도달하면로드 요소가 효과적으로 무시되고 배열의 성장이 멈 춥니 다.

이 시점에서 충돌 속도가 증가합니다.

hashCode()가 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); 
}