Правило для выбора реализации коллекции Java?

Question

У кого-нибудь есть хорошее эмпирическое правило для выбора между различными реализациями интерфейсов Java Collection, такими как List, Map или Set?

Например, вообще, почему или в каких случаях я бы предпочел использовать Vector или ArrayList, Hashtable или HashMap?

Answer 1

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

Более подробно была блок-схема Александра Загниотова, но, к сожалению, он не в сети.

Answer 2

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

Список

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

Установка:

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

Карта: Производительность и поведение HashMap и TreeMap параллельны реализациям Set.

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

Answer 3

Я всегда принимал эти решения в каждом конкретном случае, в зависимости от варианта использования, например:

• Нужен ли заказ, чтобы остаться?
• Будет ли у меня нулевой ключ / значения? Dups
• Будет ли доступ к нему несколькими потоками
• Нужна ли мне пара ключ / значение
• Нужен ли мне произвольный доступ?

А потом я выкладываю свой удобный 5-й выпуск Java в двух словах и сравниваю ~ 20 или около того вариантов. В пятой главе есть хорошие столики, которые помогут понять, что уместно.

Хорошо, может быть, если я узнаю, что простой ArrayList или HashSet справятся с задачей, я не буду все это искать. ;) но если в моем использовании с отступами есть что-то сложное, держите пари, я в книге. Кстати, я думаю, что Вектор должен быть «старой шляпой» - я не пользовался годами.

Answer 4

Теоретически существуют полезные Big-Oh компромиссы, но на практике они почти никогда не имеют значения.

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

Мое правило:

1. Всегда начинайте с ArrayList, HashSet и HashMap (т.е. не LinkedList или TreeMap).
2. Объявления типов всегда должны быть интерфейсом (т. Е. List, Set, Map), поэтому, если профилировщик или просмотр кода подтвердит иное, вы можете изменить реализацию, не нарушая ничего.

Answer 5

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

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

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

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

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

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

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

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

Answer 6

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

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

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

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

Answer 7

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

ArrayList:

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

LinkedList:

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

HashSet:

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

• Запоминание «какие элементы вы уже обработали», например, при выполнении веб-сканирования;

HashMap:

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

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

Answer 8

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

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

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

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

РЕДАКТИРОВАТЬ: Я надеюсь, что следующие ссылки демонстрируют, как эти вещи на самом деле являются просто элементами в наборе инструментов, вам просто нужно подумать о своих потребностях: См. Версии Commons-Collections Map , Список и Набор .

Answer 9

Ну, это зависит от того, что вам нужно. Общие рекомендации:

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

Set - пакет элементов без дублирования (если вы повторно вставите тот же элемент, он не будет добавлен). Данные не имеют понятия порядка.

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

Атрибуция: https://stackoverflow.com/a/21974362/2811258

Для получения дополнительной информации о коллекциях Java, ознакомьтесь с этой статьей .

Answer 10

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