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

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

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

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

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

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

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

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

    Карта Java / Коллекция

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

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

    Список :

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

    Задавать:

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

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

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

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

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

    Мое правило:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    ArrayList:

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

    LinkedList:

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

    HashSet:

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

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

    HashMap:

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

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

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

    Давайте будем гением компьютера.