Тип коллекции по умолчанию

Question

Предположим, вам нужно хранить / извлекать элементы в Collection, не заботитесь о порядке заказа, допускаются дубликаты, какой тип Collection вы используете?

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

Я понимаю, что все дискуссии о производительности несколько бессмысленны, единственное, что действительно имеет значение, - это измерение.Тем не менее, мне интересно узнать, что другие используют для Collection, когда они не заботятся о порядке и допускаются дубликаты и почему ?

Answer 1

«Это зависит». Сначала вам нужно ответить на вопрос: «Для чего я хочу использовать коллекцию?»

Если вы часто вставляете / удаляете элементы на одном из концов (начало, конец), Queue будет лучше, чем ArrayList. Однако во многих случаях вы создаете коллекцию, чтобы просто читать из нее. В этом случае ArrayList гораздо более эффективен: поскольку он реализован в виде массива, вы можете перебирать его довольно эффективно (то же самое относится к LinkedList). Однако LinkedList использует ссылки для связывания отдельных элементов. Поэтому, если вам не нужно случайное удаление элементов (посередине), лучше использовать ArrayList: ArrayList будет использовать меньше памяти, поскольку элементам не нужно хранилище для ссылки на следующий / предыдущий элемент.

Подводя итог:

ArrayList = хорошо, если вы вставляете один раз и часто читаете (произвольный или последовательный)

LinkedList = хорошо, если вы часто вставляете / удаляете в случайных позициях и читаете только последовательно

ArrayDeque (только java6) = хорошо, если вы вставляете / удаляете в начале / конце и читаете случайное или последовательное

Answer 2

ArrayList в основном содержит массив внутри (поэтому он называется ArrayList).А такие операции, как добавление / удаление в произвольных позициях, выполняются простым способом, поэтому, если вы их не используете, производительности не вредят.

Answer 3

По умолчанию я предпочитаю от LinkedList до ArrayList. Очевидно, я использую их не через интерфейс List, а через интерфейс Collection.

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

Answer 4

Я понимаю, что все дискуссии о производительности несколько бессмысленны, единственное, что действительно имеет значение, это измерение.

Это не обязательно так.

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

Например, если в вашем приложении, вероятно, будет доминировать тестирование, если коллекция содержит данный объект, тот факт, что Collection.contains(Object) равен O(N) для LinkedList<T> и ArrayList<T> , может означает, что ни один из них не является подходящим типом коллекции. Вместо этого, возможно, вам следует представлять коллекцию в виде HashMap<T, Integer>, где Integer представляет количество вхождений T в «коллекции». Это даст вам O(1) тестирование и удаление за счет увеличения затрат на пространство и более медленной (хотя все еще O(1)) вставки.

Но следует подчеркнуть, что если вы, вероятно, имеете дело с действительно большими коллекциями, не должно быть такого понятия, как тип коллекции "по умолчанию". Вы должны думать о коллекции в контексте алгоритмов. (И обратная сторона в том, что если коллекции всегда будут небольшими, то, вероятно, не имеет значения, какой тип коллекции вы выберете.)

Answer 5

Это зависит от того, что вы знаете об этом.

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

Answer 6

Если упорядочение и дубликаты не являются проблемой и дело только для хранения,

Я использую ArrayList , так как он реализует все операции со списком.Никогда не испытывал проблем с производительностью этих операций (никогда не влиял на мои проекты).На самом деле использование этих операций имеет простое использование, и мне не нужно заботиться о том, как его внутренне управлять.

Только если несколько потоков будут иметь доступ к этому списку, я использую Vector , потому что его методы синхронизированы.

Также ArrayList и Vector - это коллекции, которые вы изучаете первыми:).