Блог

Главная - Вопросы по программированию - Максимальный размер HashSet, Vector, LinkedList

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

#java #collections

#java #Коллекции

Вопрос:

Каков максимальный размер HashSet , Vector , LinkedList ? Я знаю, что ArrayList может храниться более 3277000 номеров.

Однако размер списка зависит от размера памяти (кучи). Если он достигает максимума, JDK выдает OutOfMemoryError .

Но я не знаю предела для количества элементов в HashSet , Vector и LinkedList .

Ответ №1:

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

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

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

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

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

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

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

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

Комментарии:

1. HashMap использует массив для первого поиска. Но если произойдет столкновение ключей, они будут сохранены в связанном списке. Поэтому a HashMap может содержать больше Integer.MAX_VALUE элементов — непредсказуемым образом.

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

3. Пределом для HashMap является коэффициент загрузки * один миллиард. После этого он не сможет увеличить базовый массив. Вектор не будет расти до целого числа. MAX_VALUE, вам нужно будет создать вектор с этим размером в качестве начальной емкости. (маловероятно) size() документирует это целое число. MAX_VALUE возвращается для размеров, превышающих это, поэтому size() для LinkedList не является неправильным ИМХО.

4. Я не думаю, что вы правильно поняли для HashMap / HashSet. Это правда, что хэш-массив ограничен 2^30 . Однако вы можете продолжать добавлять элементы в таблицу до бесконечности , поскольку цепочки хэшей представляют собой простые связанные списки. (Производительность будет снижаться по мере роста хэш-цепочек, но это другая проблема.) См. docjar.com/html/api/java/util/HashMap.java.html строка 764

5. @StephenC, @A.H.: вы правы, он просто перестает изменять размер после достижения предела, поэтому HashMap / HashSet действует так же, как и a LinkedList после этого (растет неограниченно). Я обновлю свой ответ.

Ответ №2:

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

Ответ №3:

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

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

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

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

Кстати: используйте ArrayList, а не Vector, если можете.

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

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

Комментарии:

1. Примечание: в реализации OpenJDK LinkedList (и я предполагаю, что и в Oracle JDK) нет возможности корректного возврата Integer.MAX_VALUE после того, как размер превысит это значение.

Ответ №4:

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

Ответ №5:

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

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

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

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

Шестидесятичетырехразрядная система имеет шестьдесят четырехразрядных указателей, что делает все указатели в два раза больше, делая списки, отличные от массивов, более толстыми. Это также означает, что максимальная поддерживаемая емкость увеличивается ровно до 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)