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

Question

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

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

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

Список:

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

Набор:

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

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

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

Answer 4

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

В реальных тестах 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, если вам нужна структура данных, подобная массиву, и вам нужно перебирать элементы
• используйте карту, если вам нужно что-то вроде словаря
• используйте Set, если вам нужно только решить, принадлежит ли что-то набору или нет.

По поводу вашего второго вопроса...

Основное различие между 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 для достаточно небольших списков и HashSet для достаточно небольших наборов, но существует множество реализаций (включая те, которые вы пишете сами).HashMap довольно распространен для Карт.Что-то большее, чем «достаточно мало», и вам придется начать беспокоиться о памяти, так что алгоритмически это будет намного более конкретным.

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

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

Answer 8

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

Список массивов:

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

Связанный список:

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

Хэшсет:

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

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

ХэшМап:

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

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

Answer 9

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

Answer 10

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

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

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

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

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

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