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

Question

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

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

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

Answer 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.

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

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

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

Answer 4

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

Answer 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-массив достиг своего теоретического максимума. байт [0x7fffffff] [0x7fffffff] использует память, приблизительно равную 40 + 40 * (2 ^ 31-1) + (2 ^ 31-1) (2 ^ 31-1) = 40 + 40 (2 ^ 31-1) + (2 ^ 62-2 ^ 32 + 1)