Какой лучший способ иметь гигантский ArrayList в Java?

Мне нужен ArrayList на Java, который может иметь до миллиона записей (я не делаю правила, я просто их реализую). ArrayList явно умрет задолго до 1 миллиона (он может попасть туда, но он будет длиться недолго). LinkedList не будет работать, потому что есть места, где мне нужно получить к нему доступ с помощью get (index).

Какой лучший подход для этого? Лучшее, о чем я думал, это двухэтапный массив, в котором основные элементы массива указывают на подмножество массива. Таким образом, каждый массив содержит 1000 объектов, а основной массив может указывать на 1000 из этих подматриц.

Массив не разрежен и построен по порядку. И в основном после этого обращались по порядку.

Обновление для некоторых из нижеперечисленных вопросов:

  1. Мне нужна ArrayList (или эквивалент) для необходимой мне функциональности.
  2. Мне нужно все это в памяти сразу.
  3. Я не знаю, насколько велика будет заблаговременно. Обычно это будет 4 - 20 элементов. Но в редкие времена это может быть миллион.
  4. Я нахожу, что как только массив получает более 120 тыс. Записей, он останавливается примерно каждые 30 или около того. Поэтому я предполагаю, что ArrayList требует много времени, поскольку он становится большим.

Обновление 2:

С некоторыми ответами на это высказывание ArrayList должно быть достаточно быстрым, я написал небольшую тестовую процедуру, чтобы создать миллион строк массива one add() за раз. И это (нужно копать в мой код, чтобы понять, почему это похоже на проблему, а это не так).

LinkedList seconds = 0.136

ArrayList seconds = 0,087

2 ответа

Если все, что вы делаете, это добавление элементов, обращение к элементам по индексу и последовательное повторение с помощью элементов, почему у ArrayList возникли проблемы? ArrayList очень эффективен во всех этих операциях.

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

Если вы не заботитесь о латентности, вы можете просто создать индекс для этого столбца в своей базе данных и сделать выборки по индексированному столбцу, что достаточно эффективно (хотя и не так быстро, как доступ к ссылке в памяти, очевидно). Если вы заботитесь о задержке и можете заранее предсказать, какие элементы вы, вероятно, будете получать доступ, то какой-то механизм кеширования можно легко сделать, чтобы соответствовать вашим требованиям к доступу к памяти и объекту.

К сожалению, я не знаю, каковы ваши требования к латентности, и ваш вопрос действительно не указывает, как вы будете использовать этот гигантский массив, поэтому эта неопределенная asspull - лучшее, что я могу сделать.


Учитывая массив A, индекс имеет тип integer, то есть он может иметь несколько миллионов записей. Поэтому самый простой способ иметь массив с миллионом записей типа O в нем - использовать

O[] o = new O[1000000];

licensed under cc by-sa 3.0 with attribution.