Эмпирическое правило для выбора реализации коллекции Java?

Мне очень нравится эта шпаргалка от Сергея Ковальчука запись в блог:

Подробнее блок-схема Александра Загниотова со своего сайта.

Я предполагаю, что вы знаете разницу между списком, набором и картой из приведенных выше ответов. Другое дело, почему вы выбрали бы между их классами реализации. Например:

список:

1. ArrayList быстро при извлечении, но медленно при вставке. Это хорошо для реализации, которая много читает, но не вставляет/удаляет много. Он хранит свои данные в одном непрерывном блоке памяти, поэтому каждый раз он должен расширяться, копирует весь массив.
2. LinkedList медленно при извлечении, но быстро при вставке. Это хорошо для реализации, которая вставляет/удаляет много, но не читает много. Он не сохраняет весь массив в одном непрерывном блоке памяти.

Set:

1. HashSet не гарантирует порядок итерации, и поэтому является самым быстрым из наборов. Он имеет высокие накладные расходы и медленнее, чем ArrayList, поэтому вы не должны использовать его, за исключением большого количества данных, когда его скорость хэширования становится фактором.
2. TreeSet сохраняет данные упорядоченными, поэтому медленнее, чем HashSet.

карты производительность и поведение HashMap и TreeMap параллельны реализации набора.

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

теоретически есть полезное О компромиссы, но на практике они почти никогда не имеют значения.

в реальных бенчмарках,ArrayList делает LinkedList даже с большими списками и с такими операциями, как "много вставок рядом с фронтом."Ученые игнорируют тот факт, что реальные алгоритмы имеют постоянные факторы, которые могут преодолеть асимптотическую кривую. Например, связанные списки требуют дополнительного выделения объектов для каждого узла, что означает более медленное создание узел и значительно худшие характеристики доступа к памяти.

мои правила:

1. ВСЕГДА НАЧИНАЙТЕ С ArrayList и HashSet и HashMap (т. е. не LinkedList или TreeMap).
2. объявления типов всегда должны быть интерфейсом (т. е. списком, набором, картой), поэтому, если профилировщик или обзор кода доказывают обратное, вы можете изменить реализацию, ничего не нарушая.

о вашем первом вопросе...

список, карта и набор служат различным целям. Я предлагаю прочитать о Java Collections Framework в http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html.

чтобы быть немного более конкретным:

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

о вашем втором вопросе...

основное различие между Vector и ArrayList заключается в том, что первый синхронизируется, второй не синхронизируется. Вы можете прочитать больше о синхронизации в параллелизм Java на практике.

разница между Hashtable (обратите внимание, что T не является заглавной буквой) и HashMap аналогична, первая синхронизирована, последний не синхронизирован.

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

для не отсортированных лучшим выбором, более чем в девяти случаях из десяти, будет: ArrayList, HashMap, HashSet.

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

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

для карт и наборов хэш-варианты будут быстрее, чем дерево/сортировка. Хэш-алгоритмы, как правило, имеют производительность O(1), тогда как деревья будут O(log n).

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

Я буду использовать карту всякий раз, когда мне нужно будет выполнить поиск.

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

на этой странице и много анимированных изображений вместе с образцом кода тестирования LinkedList против ArrayList, если вы заинтересованы в жестких числах.

EDIT: Я надеюсь, что следующие ссылки демонстрируют, как эти вещи на самом деле просто элементы в наборе инструментов, вы просто должны думать о том, что ваши потребности: см Commons-коллекции версий карта,список и Set.

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

ArrayList:

• большинство случаев, когда вам просто нужно хранить или перебирать "кучу вещей", а затем перебирать их. Итерация выполняется быстрее, так как ее индекс основан.
• всякий раз, когда вы создаете ArrayList, ему выделяется фиксированный объем памяти, и после того,как он будет удален, он копирует весь массив

LinkedList:

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

HashSet:

• принятие других решений да-нет об элементе, например "является ли элемент словом английского языка", " является ли элемент в базе данных?", "- это пункт в эта категория?" прием.

• запоминание "какие элементы вы уже обработали", например, при выполнении веб-обхода;

HashMap:

• используется в тех случаях, когда вам нужно сказать "для данного X, Что такое Y"? Это часто полезно для реализации кэшей в памяти или индексов, т. е. пар ключевых значений, например: Для данного идентификатора пользователя, каково их кэшированное имя / объект пользователя?.
• всегда идти с HashMap для выполнения уважать.

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

Я нашел мышление Брюса Экеля на Java, чтобы быть очень полезным. Он очень хорошо сравнивает разные коллекции. Я использовал, чтобы сохранить диаграмму, которую он опубликовал, показывая наследство heirachy на моей стене Куба в качестве краткой ссылки. Одна вещь, которую я предлагаю вам сделать, это иметь в виду потокобезопасность. Производительность обычно означает не потокобезопасность.