Правило большого пальца для выбора реализации Java Collection?

Ответ 1

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

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

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

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

Ответ 2

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

Более детальной была блок-схема Александра Загниотова, но, к сожалению, она не в сети. Однако у Wayback Machine есть копия блога:

Ответ 3

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

List

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

Set:

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

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

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

Ответ 4

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

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

Мое правило:

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

Ответ 5

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

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

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

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

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

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

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

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

Ответ 6

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

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

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

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

Ответ 7

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

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

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

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

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

Ответ 8

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

ArrayList:

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

LinkedList

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

HashSet:

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

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

HashMap

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

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

Ответ 9

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

Ответ 10

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

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

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

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

Атрибуция: fooobar.com/info/62908/...

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