Есть ли список Java длиннее, чем int?

Кажется, я не могу найти Java List, максимальная длина которого равна максимальному значению long.

Существует ли такой List?

Если да, то где?


java arraylist maxlength long-integer
person Community    schedule 27.01.2014    source источник
comment
Вам действительно нужно хранить такой объем данных в памяти?   -  person Reimeus    schedule 27.01.2014
comment
Вы ожидаете, что список будет содержать более 2 миллиардов элементов? Учитывая, что заголовки объекта составляют 8 байтов плюс 4 байта на ссылку, вы смотрите на (8 байтов + 4 байта) * 2 миллиарда = 24 ГБ памяти в самом нижнем конце полного списка длины int. И это, вероятно, хуже для 64-битной машины.   -  person sigpwned    schedule 27.01.2014
comment
@Reimeus List - это просто интерфейс, реализация может не хранить все данные в памяти.   -  person Basilevs    schedule 27.01.2014
comment
Рассмотрите возможность использования LinkedList   -  person MadProgrammer    schedule 27.01.2014
comment
Хм. Требуется только одна ссылка — файл, например.   -  person Basilevs    schedule 27.01.2014
comment
@sigpwned Да, в долгосрочной перспективе следует ожидать, что это приложение будет быстро управлять этими величинами, и позже реализовать лучшее решение будет непросто.   -  person    schedule 27.01.2014
comment
@Basilevs Спасибо, Basilevs! Означает ли этот комментарий, что весь List не нужно хранить в памяти?   -  person    schedule 27.01.2014
comment
@Gracchus Не существует стандартной реализации, которая не хранила бы свои данные в памяти. Однако пользовательская реализация интерфейса List вполне способна хранить свои данные во внешнем хранилище.   -  person Basilevs    schedule 27.01.2014
comment
Списки часто злоупотребляют, когда следует использовать более потоковый подход, такой как итератор или писатель. Попробуйте вместо этого использовать эти интерфейсы в своей библиотеке/приложении.   -  person Adam Gent    schedule 27.01.2014

Ответы (3)


arrow_upward
7
arrow_downward

Как говорит @afsantos, класс ArrayList по своей сути ограничен Integer.MAX_VALUE записями из-за ограничений массивов Java.

LinkedList не имеет этого ограничения, но (тем не менее) дорого:

  • Каждая запись влечет за собой накладные расходы памяти на 2 ссылки плюс размер заголовка объекта... по сравнению с одной ссылкой для представления на основе массива.

  • Индексирование — это операция O(N) по сравнению с O(1) для списка на основе массива.

Вот ссылка на библиотеку Java, которая поддерживает огромные коллекции в памяти с использованием памяти с прямым отображением и/или кодирования элементов:

Там могут быть и другие альтернативы.

Можно также предусмотреть «большой» вариант обычных списков массивов, в котором используется массив массивов, а не один массив. Но если вы разрешите вставку в середину списка, становится сложно/дорого добиться поиска O(1). (Возможно, поэтому я не смог найти пример с Google...)

person Stephen C    schedule 27.01.2014

arrow_upward
6
arrow_downward

Из документации List:

int size()

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

Таким образом, даже если конкретная реализация List содержит Long.MAX_VALUE элементов, вы не узнаете об этом, используя стандартный интерфейс List.

Я не уверен, существует ли он, но я бы сделал ставку на LinkedList, поскольку ArrayList основан на массивах, а они не могут содержать более Integer.MAX_VALUE элементов.

person afsantos    schedule 27.01.2014
comment
Спасибо, афсантос! Да, LinkedList похоже ограничен только памятью. - person ; 27.01.2014

arrow_upward
4
arrow_downward

Поскольку List.get(int) принимает int в качестве аргумента, невозможно адресовать записи с индексами больше Integer.MAX_VALUE.

Однако обратите внимание, что Iterable<?> или Map<Long, ?> могут обращаться к гораздо большему количеству данных. Поскольку List реализует Iterable, он может содержать любое количество данных (эта часть не отображается с помощью API List на основе int).

person Basilevs    schedule 27.01.2014