Максимальный размер HashSet, Vector, LinkedList

Ответ 1

Не указан максимальный размер этих структур.

Фактический размер практического размера, вероятно, находится где-то в области Integer.MAX_VALUE (т.е. 2147483647, примерно 2 миллиарда элементов), поскольку это максимальный размер массива в Java.

• A HashSet использует HashMap внутренне, поэтому он имеет тот же максимальный размер, что и
  • A HashMap использует массив, который всегда имеет размер, равный двум, поэтому он может составлять не более 2 ³⁰= 1073741824 элементов большой (поскольку следующая мощность двух больше чем Integer.MAX_VALUE).
  • Обычно количество элементов не превышает количество ковшей, умноженное на коэффициент загрузки (по умолчанию 0,75). Однако, когда HashMap перестает изменять размер, он все равно позволит вам добавлять элементы, используя тот факт, что каждое ведро управляется через связанный список. Поэтому единственным пределом для элементов в HashMap/HashSet является память.
• A Vector использует массив внутри, который имеет максимальный размер точно Integer.MAX_VALUE, поэтому он не может поддерживать больше, чем многие элементы
• A LinkedList не использует массив в качестве базового хранилища, поэтому он не ограничивает размер. Он использует классическую структуру с двойным связыванием, не имеющую ограничений по свойству, поэтому ее размер ограничивается доступной памятью. Обратите внимание, что LinkedList сообщит размер неправильно, если он больше, чем Integer.MAX_VALUE, потому что он использует поле int для хранения размера, а тип возврата size() - int.

Обратите внимание, что в то время как API Collection определяет, как должен вести себя Collection с более чем Integer.MAX_VALUE элементами. Самое главное, что это документация size():

Если этот набор содержит больше элементов Integer.MAX_VALUE, возвращает Integer.MAX_VALUE.

Обратите внимание, что в то время как HashMap, HashSet и LinkedList, похоже, поддерживают более чем Integer.MAX_VALUE элементы, ни один из них не реализует метод size() таким образом (то есть они просто позволяют внутреннему полю size переполнение).

Это заставляет меня думать, что другие операции также не определены в этом состоянии.

Поэтому я бы сказал, что безопасно использовать эти коллекции общего назначения с элементами Integer.MAX_VLAUE. Если вы знаете, что вам нужно хранить больше, чем это, вы должны перейти к выделенным реализациям коллекций, которые действительно поддерживают это.

Ответ 2

Во всех случаях вы, скорее всего, будете ограничены размером кучи JVM, а не чем-либо еще. В конце концов вы всегда будете обращаться к массивам, поэтому я очень сомневаюсь, что любой из них будет управлять более чем двумя элементами ³¹ - 1, но вы, скорее всего, исчерпаете кучу до этого в любом случае.

Ответ 3

Максимальный размер зависит от настроек памяти JVM и, конечно же, от доступной системной памяти. Конкретный размер потребления памяти для каждой записи списка также различается между платформами, поэтому самым простым способом может быть запуск простых тестов.

Ответ 4

Это очень зависит от деталей реализации.

HashSet использует массив в качестве основного хранилища, который по умолчанию пытается расти, когда сборник заполнен на 75%. Это означает, что он потерпит неудачу, если вы попытаетесь добавить более 750 000 000 записей. (Он не может вырастить массив от 2 ^ 30 до 2 ^ 31 записей)

Увеличение коэффициента загрузки увеличивает максимальный размер коллекции. например коэффициент нагрузки 10 позволяет 10 миллиардов элементов. (Стоит отметить, что HashSet относительно неэффективен за 100 миллионов элементов, поскольку распределение 32-битного хэш-кода начинает выглядеть менее случайным, а число столкновений увеличивается)

Вектор удваивает его емкость и начинается с 10. Это означает, что он не вырастет выше 1,34 миллиарда. Изменение начального размера до 2 ^ n-1 дает вам немного больше головной комнаты.

BTW: используйте ArrayList вместо Vector, если сможете.

LinkedList не имеет собственного предела и может превысить 2,1 миллиарда. В этот момент size() может возвращать Integer.MAX_VALUE, однако некоторые функции, такие как toArray, потерпят неудачу, поскольку не могут помещать все объекты в массив, вместо этого вместо этого вы получите первое Integer.MAX_VALUE, а не исключение.

Как отмечает @Joachim Sauer, текущий OpenJDK может вернуть неверный результат для размеров выше Integer.MAX_VALUE. например это может быть отрицательное число.

Ответ 5

Как указано в других ответах, массив не может достигать 2 ^ 31 записей. Другие типы данных ограничены либо этим, либо они, скорее всего, неверно отражают их размер(). Однако эти теоретические пределы не могут быть достигнуты в некоторых системах:

В 32-битной системе количество доступных байтов никогда не превышает 2 ^ 32 точно. И это предполагает, что у вас нет операционной системы, занимающей память. 32-битный указатель - 4 байта. Все, что не полагается на массивы, должно включать по крайней мере один указатель на запись: это означает, что максимальное количество записей равно 2 ^ 32/4 или 2 ^ 30 для вещей, которые не используют массивы.

Простой массив может достичь теоретического предела, но только байтовый массив, короткий массив длиной 2 ^ 31-1 будет использовать около 2 ^ 32 + 38 байт.

Некоторые java-виртуальные машины ввели новую модель памяти, которая использует сжатые указатели. При настройке выравнивания указателя чуть более 2 ^ 32 байта можно ссылаться на 32-байтовые указатели. Примерно в четыре раза больше. Этого достаточно, чтобы связать размер LinkedList(), чтобы он стал отрицательным, но недостаточно, чтобы он обернулся до нуля.

Система с шестью четырьмя битами имеет шестьдесят четыре битовых указателя, что делает все указатели в два раза большими, что делает список массивов не более толстым. Это также означает, что максимальная поддерживаемая емкость скачков точно равна 2 ^ 64 байтам. Этого достаточно для того, чтобы 2D-массив достиг своего теоретического максимума. byte [0x7fffffff] [0x7fffffff] использует память, приблизительно равную 40 + 40 * (2 ^ 31-1) + (2 ^ 31-1) (2 ^ 31-1) = 40 + 40 (2 ^ 31-1) + (2 ^ 62-2 ^ 32 + 1)