HashSet, Vector, LinkedList의 최대 크기

Question

HashSet, Vector, LinkedList의 최대 크기는 얼마입니까? ArrayList은 3277000 이상의 숫자를 저장할 수 있다는 것을 알고 있습니다.

그러나 목록의 크기는 메모리 (힙) 크기에 따라 다릅니다. 최대치에이를 경우, JDK는 OutOfMemoryError을 슬로우합니다.

그러나 HashSet, Vector 및 LinkedList의 요소 개수 제한은 알지 못합니다.

Answer 1

이러한 구조에는 지정된 최대 크기가 없습니다.

실질적인 실제 크기 제한은 Integer.MAX_VALUE (즉, 2147483647, 약 20 억 개 요소)의 어딘가에 있습니다. 자바의 배열 최대 크기입니다.

• 는 HashSet 내부적 HashMap 사용하므로 그
  • HashMap 동일한 최대 크기는 항상 2의 거듭 제곱 인 크기를 갖는 배열을 사용하므로 이하 여야 할 2 = 1073741824 요소가 크다. (다음 2의 거듭 제곱이 Integer.MAX_VALUE보다 크기 때문에).
  • 일반적으로 요소 수에는 최대로드 인수 배수 (기본적으로 0.75)가 포함됩니다. 그러나 일 때 HashMap이 크기 조정을 중지하면 은 여전히 ​​이되어 각 버킷이 연결된 목록을 통해 관리된다는 사실을 악용하여 요소를 추가 할 수 있습니다. 따라서 HashMap/HashSet에있는 요소의 유일한 제한은 메모리입니다.
• Vector 정확히 Integer.MAX_VALUE의 최대 크기를 갖는 내부 배열을 사용하기 때문에 그 많은 요소
• LinkedList는는 기본 스토리지와 같은 배열을 사용하지 않는 이상을 지원할 수없는, 그래서 그 크기를 제한하지 않습니다. 고유 한 제한이없는 클래식 이중 링크 된 목록 구조를 사용하므로 크기는 만 사용 가능한 메모리로 제한됩니다. 크기가 int 인 필드를 사용하여 size()의 반환 유형이 int이기 때문에 은 Integer.MAX_VALUE보다 큰 경우 잘못보고합니다.Collection API 가하는 동안 이상 Integer.MAX_VALUE 요소가 Collection 작동 방법을 정의하는 것이
는

참고. 이 컬렉션 이상 Integer.MAX_VALUE 요소를 포함 Integer.MAX_VALUE을 반환하는 경우

: 가장 중요한 것은이 the size() documentation을 말한다. HashMap, HashSet 및 LinkedList이상 Integer.MAX_VALUE 요소 없음을 지원하기 위해를 보이는 동안 사람들의이 (즉, 그들은 단순히 내부 size 필드 오버 플로우를하자) 이런 식으로 size() 방법을 구현하는 것이

는

참고.

이렇게하면 다른 작업 도이이 조건에서 잘 정의되어 있지 않습니다.

그래서 나는 Integer.MAX_VLAUE 요소까지 있는 사람 범용 컬렉션을 사용하는 안전 말하고 싶지만. 이 그 이상을 저장해야하는을 알고 있다면 실제로이를 지원하는 전용 컬렉션 구현으로 전환해야합니다.

Answer 2

최대 크기는 JVM의 메모리 설정과 물론 사용 가능한 시스템 메모리에 따라 다릅니다. 목록 항목 당 특정 메모리 사용량은 플랫폼마다 다르므로 가장 간단한 방법은 간단한 테스트를 실행하는 것입니다.

Answer 3

모든 경우에 JVM 힙 크기에 의해 제한 될 가능성이 큽니다. 궁극적으로 항상 배열로 넘어 가서 두 개 이상을 관리 할 것이므로 - 1 개의 요소를 관리하지만, 어쨌든 그 전에는 힙이 부족할 가능성이 매우 큽니다.

Answer 4

대단히 구현 세부 사항에 따라 다릅니다.

HashSet은 컬렉션이 75 % 찼을 때 기본적으로 확장을 시도하는 기본 저장소로 배열을 사용합니다. 즉, 약 750,000,000 개 이상의 항목을 추가하려고하면 오류가 발생합니다. (배열을 2^30에서 2^31까지 증가시킬 수 없음)

로드 계수를 늘리면 컬렉션의 최대 크기가 증가합니다. 예 : 로드 계수 10은 100 억 개의 요소를 허용합니다. (HashSet은 32 비트 해시 코드의 배포가 덜 무작위로 보이고 충돌 횟수가 증가하기 때문에 1 억 개 요소가 상대적으로 비효율적이지 않음을 알리는 것이 중요합니다.

벡터는 용량을 두 배로하고 10에서 시작합니다. 이는 약 13 억 4 천만을 초과하여 성장하지 못한다는 것을 의미합니다. 초기 크기를 2^n-1로 변경하면 헤드 룸이 약간 더 넓어집니다.

BTW : 가능한 경우 Vector 대신 ArrayList를 사용하십시오.

LinkedList에는 상속 제한이 없으며 21 억을 초과하여 커질 수 있습니다. 이 시점에서 size()는 Integer.MAX_VALUE를 반환 할 수 있지만 toArray와 같은 일부 함수는 모든 객체를 배열에 넣을 수 없으므로 실패합니다. 대신 예외를 throw하는 대신 Integer.MAX_VALUE를 처음 제공합니다.

@Joachim Sauer가 지적했듯이 현재 OpenJDK는 Integer.MAX_VALUE 이상의 크기에 대해 잘못된 결과를 반환 할 수 있습니다. 예 : 음수 일 수 있습니다.

Answer 5

다른 답변에서 설명한 것처럼 배열은 2^31 개 항목에 도달 할 수 없습니다. 다른 데이터 유형은 이것에 의해 제한되거나 결국 크기를 잘못보고합니다(). 그러나 일부 시스템에서는 이러한 이론적 인 한계에 도달 할 수 없습니다.

32 비트 시스템에서 사용 가능한 바이트 수는 정확하게 2^32를 초과하지 않습니다. 그리고 그것은 당신이 운영 체제가 메모리를 차지하지 않는다고 가정합니다.32 비트 포인터는 4 바이트입니다. 배열에 의존하지 않는 항목은 항목 당 적어도 하나의 포인터를 포함해야합니다. 즉, 배열을 사용하지 않는 항목의 최대 항목 수는 2^32/4 또는 2^30입니다.

일반 배열은 이론적으로 한계가 있지만 바이트 배열 만 가능하며 길이가 2^31-1 인 짧은 배열은 약 2^32 + 38 바이트를 사용합니다.

일부 Java VM은 압축 포인터를 사용하는 새로운 메모리 모델을 도입했습니다. 포인터 정렬을 조정하면 32 바이트 포인터로 2^32 바이트보다 약간 더 많이 참조 할 수 있습니다. 4 배 정도. 이것은 LinkedList 크기()가 음수가되도록하기에 충분하지만 0으로 감싸기에는 충분하지 않습니다.

64 비트 시스템은 64 비트 포인터를 가지고있어 모든 포인터를 두 배로 크게 만들어 비 배열 목록을 훨씬 더 넓게 만듭니다. 이것은 또한 지원되는 최대 용량이 정확하게 2^64 바이트로 점프한다는 것을 의미합니다. 2D 배열이 이론적 인 최대 값에 도달하기에 충분합니다. 바이트 [0x7fffffff] [0x7fffffff]는 40 + 40 * (2^31-1) + (2^31-1) (2^31-1) = 40 + 40 (2^31-1) + (2^62-2^32 + 1)