Самый эффективный способ сохранить коллекцию на Java?

Question

В настоящее время у меня есть LinkedList, который хранит пользовательский класс Node. Узлы в настоящее время удаляются по порядку и оцениваются, что обычно добавляет больше узлов в LinkedList, рассматривая его как очередь.

Но на самом деле я не забочусь о поддержании порядка узлов, потому что заказ, который они добавляют или удаляют, не имеет значения. Вы можете удалить 1-й, 54-й или 1032-й узлы из списка, это не имеет значения. Все, что имеет значение, - это то, что Узлы обрабатываются быстро, что означает, что один удаляется (случайным образом), мутируется, затем добавляется обратно вместе с несколькими его вариантами (еще раз порядок не имеет значения).

Поскольку я не смог найти реализацию Java Bag, какой наиболее эффективный способ поддерживать этот тип коллекции? Заранее спасибо.

PS Из лени я избегаю использования массивов, потому что набор узлов теоретически может варьироваться от 1 узла до 3^64 узлов, хотя он, скорее всего, останется под миллионом.

Answer 1

Здесь могут быть использованы типы Java HashSet или TreeSet, поскольку они представляют собой неупорядоченные коллекции элементов, которые поддерживают быструю вставку и удаление элементов. Тем не менее, вы не можете удерживать значения в памяти, так как это интересно 3.4336838 , число, значительно превышающее любой объем оперативной памяти, о котором я знаю, может быть сохранен.

EDIT: На основе описанного варианта использования (поддержка эффективной вставки и удаления случайных элементов) вы можете принять подход described in this older question for building a data structure that does just that. Интуитивно, вы использовали бы ArrayList, а затем удаляли элементы, заменяя их до конца ArrayList и удаляя их. Это дает возможность установки O (1) и O (1) с чрезвычайно низкими накладными расходами.

Надеюсь, это поможет!