Максимальный размер HashSet, Vector, LinkedList
Каков максимальный размер HashSet , Vector , LinkedList ? я знаю это ArrayList может хранить более 3277000 номеров.
Однако размер списка зависит от размера памяти (кучи). Если он достигает максимума, JDK бросает OutOfMemoryError ,
Но я не знаю ограничения на количество элементов в HashSet , Vector а также LinkedList ,
5 ответов
Не существует определенного максимального размера этих структур.
Фактический практический предел размера, вероятно, где-то в области Integer.MAX_VALUE (т.е. 2147483647, примерно 2 миллиарда элементов), так как это максимальный размер массива в Java.
- HashSet использует HashMap внутренне, поэтому он имеет такой же максимальный размер, как
- HashMap использует массив, который всегда имеет размер, равный степени двойки, поэтому он может быть не более 2 30 = 1073741824 элементов большим (поскольку следующая степень двойки больше, чем Integer.MAX_VALUE ).
- Обычно количество элементов — это самое большее количество сегментов, умноженное на коэффициент нагрузки (по умолчанию 0,75). Тем не менее, когда HashMap прекратит изменение размера, тогда он все еще позволит вам добавлять элементы, используя тот факт, что каждое ведение управляется через связанный список. Поэтому единственным ограничением для элементов в HashMap / HashSet это память.
Обратите внимание, что в то время как Collection API определяет, как Collection с более чем Integer.MAX_VALUE элементы должны вести себя Самое главное, что это size() документация:
Если эта коллекция содержит более Integer.MAX_VALUE элементы, возврат Integer.MAX_VALUE ,
Обратите внимание, что в то время как HashMap , HashSet а также LinkedList кажется, поддерживают больше, чем Integer.MAX_VALUE элементы, ни один из которых не реализует size() метод таким образом (т.е. они просто позволяют внутреннему size переполнение поля).
Это заставляет меня верить, что другие операции также не определены в этом состоянии.
Так что я бы сказал, что эти коллекции общего назначения безопасно использовать до Integer.MAX_VLAUE элементы. Если вы знаете, что вам нужно хранить больше, чем это, то вам следует переключиться на специальные реализации коллекций, которые фактически поддерживают это.
Во всех случаях вы, скорее всего, будете ограничены размером кучи JVM, а не чем-либо еще. В конце концов, вы всегда будете обращаться к массивам, поэтому я очень сомневаюсь, что любой из них будет управлять более чем 2 31 — 1 элементом, но у вас, скорее всего, все равно останется куча к тому времени.
Это очень сильно зависит от деталей реализации.
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. например, это может быть отрицательное число.
Максимальный размер зависит от настроек памяти JVM и, конечно, доступной системной памяти. Конкретный размер потребления памяти для каждой записи в списке также различается для разных платформ, поэтому самым простым способом может быть запуск простых тестов.
Как указано в других ответах, массив не может достигать 2^31 записей. Другие типы данных либо ограничены этим, либо они, вероятно, будут со временем искажать свой размер (). Однако эти теоретические пределы не могут быть достигнуты в некоторых системах:
В 32-битной системе количество доступных байтов никогда точно не превышает 2 ^ 32. И это при условии, что у вас нет операционной системы, занимающей память. 32-битный указатель составляет 4 байта. Все, что не зависит от массивов, должно содержать как минимум один указатель на запись: это означает, что максимальное количество записей составляет 2^32/4 или 2^30 для вещей, которые не используют массивы.
Простой массив может достичь своего теоретического предела, но только байтовый массив, короткий массив длиной 2^31-1, будет занимать около 2 ^ 32 + 38 байтов.
Некоторые виртуальные машины Java представили новую модель памяти, которая использует сжатые указатели. Регулируя выравнивание указателя, на 32-байтовые указатели можно ссылаться чуть более чем на 2 ^ 32 байта. Примерно в четыре раза больше. Этого достаточно, чтобы размер LinkedList size() стал отрицательным, но этого недостаточно, чтобы обернуть его до нуля.
Шестьдесят четыре битная система имеет шестьдесят четыре битных указателя, что делает все указатели в два раза больше, делая списки без массивов толще. Это также означает, что максимальная поддерживаемая емкость точно возрастает до 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)
Максимальный размер HashSet, Vector, LinkedList
Каков максимальный размер HashSet , Vector , LinkedList ? Я знаю, что ArrayList может хранить более 3277000 номеров.
Однако размер списка зависит от размера памяти (кучи). Если он достигает максимума, JDK выдает OutOfMemoryError .
Но я не знаю предела количества элементов в HashSet , Vector и LinkedList .
5 ответов
Максимальный размер этих структур не указан.
Фактический практический предел размера, вероятно, находится где-то в районе Integer.MAX_VALUE (т. Е. 2147483647, примерно 2 миллиарда элементов), поскольку это максимальный размер массива в Java.
- HashSet использует HashMap внутри, поэтому он имеет тот же максимальный размер, что и
- A HashMap использует массив, размер которого всегда является степенью двойки, поэтому он может быть не более 2 30 = 1073741824 элементов (поскольку следующая степень двойки больше, чем Integer.MAX_VALUE ).
- Обычно количество элементов не превышает количества сегментов, умноженного на коэффициент загрузки (по умолчанию 0,75). Однако , когда HashMap перестанет изменять размер, он по-прежнему позволит вам добавлять элементы, используя тот факт, что каждая корзина управляется через связанный список. Поэтому единственным ограничением для элементов в HashMap / HashSet является память.
Обратите внимание, что хотя Collection API действительно определяет, как должен вести себя Collection с более чем Integer.MAX_VALUE элементами. Что наиболее важно, в нем говорится об этом size() документация:
Если эта коллекция содержит более Integer.MAX_VALUE элементов, возвращает Integer.MAX_VALUE .
Обратите внимание, что хотя HashMap , HashSet и LinkedList кажется , чтобы поддерживать более Integer.MAX_VALUE элементов, ни один из них не реализуют метод size() таким образом (т.е. они просто допускают переполнение внутреннего поля size ).
Это наводит меня на мысль, что другие операции также недостаточно четко определены в этом состоянии.
Поэтому я бы сказал, что безопасно использовать эти универсальные коллекции с элементами до Integer.MAX_VLAUE . Если вы знаете , что вам нужно хранить больше, тогда вам следует переключиться на специальные реализации коллекций, которые действительно поддерживают это.
HashMap использует массив для первого поиска. Но если произойдет столкновение клавиш, они будут сохранены в связанном списке. Поэтому HashMap может содержать более Integer.MAX_VALUE элементов — непредсказуемым образом.
Для LinkedList (на самом деле это касается всех списков) функция get(int) также принимает целое число, что означает, что вы не можете использовать это для извлечения элементов. В любом случае я бы не стал делать ставку на то, что LinkedList ведет себя так, как ожидалось выше Integer.MAX_VALUE.
Ограничение для HashMap — коэффициент загрузки * один миллиард. После этого он не сможет увеличить базовый массив. Вектор не будет расти до Integer.MAX_VALUE, вам придется создать вектор с этим размером в качестве начальной емкости. (маловероятно) size() документирует, что Integer.MAX_VALUE возвращается для размеров больше этого, поэтому size() для LinkedList не является неправильным ИМХО.
Я не думаю, что вы правильно поняли HashMap/HashSet. Это правда, что хэш-массив ограничен 2^30 . Однако вы можете продолжать добавлять элементы в таблицу до бесконечности, поскольку цепочки хэшей представляют собой простые связанные списки. (Производительность будет снижаться по мере роста цепочки хеширования, но это другой вопрос.) См. docjar.com/html/api/java/util/HashMap.java.html строка 764
@StephenC, @AH: вы правы, он просто перестает изменяться после достижения предела, поэтому HashMap / HashSet после этого действует так же, как LinkedList (неограниченно растет) . Я обновлю свой ответ.
Это очень сильно зависит от деталей реализации.
HashSet использует массив в качестве базового хранилища, которое по умолчанию пытается расти, когда коллекция заполнена на 75%. Это означает, что он потерпит неудачу, если вы попытаетесь добавить более 750 000 000 записей. (Он не может увеличить массив с 2 ^ 30 до 2 ^ 31 записей)
Увеличение коэффициента загрузки увеличивает максимальный размер коллекции. например коэффициент нагрузки 10 позволяет использовать 10 миллиардов элементов. (Стоит отметить, что HashSet относительно неэффективен после 100 миллионов элементов, поскольку распределение 32-битного хэш-кода начинает выглядеть менее случайным, а количество коллизий увеличивается)
Vector удваивает свою емкость и начинается с 10. Это означает, что он не сможет вырасти выше примерно 1,34 миллиарда. Изменение начального размера на 2 ^ n-1 дает немного больше места для головы.
Кстати: используйте ArrayList, а не Vector, если можете.
LinkedList не имеет ограничений и может превышать 2,1 миллиарда. На этом этапе size () может вернуть Integer.MAX_VALUE, однако некоторые функции, такие как toArray, завершатся ошибкой, поскольку он не может поместить все объекты в массив, вместо этого вместо исключения будет выдано первое Integer.MAX_VALUE.
Как отмечает @Joachim Sauer, текущий OpenJDK может возвращать неверный результат для размеров выше Integer.MAX_VALUE. например это могло быть отрицательное число.
Примечание: в реализации OpenJDK LinkedList (и я полагаю, что и в Oracle JDK) нет возможности для правильного возврата Integer.MAX_VALUE , когда размер превышает это значение.
Максимальный размер зависит от настроек памяти JVM и, конечно же, доступной системной памяти. Конкретный размер потребления памяти для каждой записи в списке также различается на разных платформах, поэтому проще всего выполнить простые тесты.
Как указано в других ответах, массив не может достигать 2 ^ 31 записей. Другие типы данных либо ограничены этим, либо они, вероятно, в конечном итоге неверно сообщат свой размер (). Однако эти теоретические пределы не могут быть достигнуты в некоторых системах:
В 32-битной системе количество доступных байтов никогда не превышает 2 ^ 32 точно. И это при условии, что у вас нет операционной системы, занимающей память. 32-битный указатель составляет 4 байта. Все, что не полагается на массивы, должно включать по крайней мере один указатель на запись: это означает, что максимальное количество записей составляет 2 ^ 32/4 или 2 ^ 30 для вещей, которые не используют массивы.
Простой массив может достичь своего теоретического предела, но только массив байтов, короткий массив длиной 2 ^ 31-1 будет использовать около 2 ^ 32 + 38 байтов.
Некоторые виртуальные машины Java представили новую модель памяти, которая использует сжатые указатели. Регулируя выравнивание указателя, 32-байтовые указатели могут ссылаться на чуть более 2 ^ 32 байтов. Примерно в четыре раза больше. Этого достаточно, чтобы значение LinkedList size () стало отрицательным, но недостаточно, чтобы позволить ему обнуляться.
Шестидесятичетырехразрядная система имеет шестьдесят четыре битных указателя, что делает все указатели вдвое больше, а списки без массивов становятся толще. Это также означает, что максимальная поддерживаемая емкость увеличивается ровно до 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)