Hashset против Treeset

HashSet намного быстрее, чем TreeSet (постоянное время по сравнению с временем журнала для большинства операций, таких как добавление, удаление и содержит), но не предлагает таких гарантий упорядочения, как TreeSet.

HashSet

• класс предлагает постоянное время выполнения основных операций (добавление, удаление, содержание и размер).
• это не гарантирует, что порядок элементов останется постоянным с течением времени.
• iteration performance depends on the initial capacity and the load factor of the HashSet.
  • It's quite safe to accept default load factor but you may want to specify an initial capacity that's about twice the size to which you expect the set to grow.

TreeSet

• гарантирует log (n) временные затраты для основных операций (добавить, удалить и содержать)
• гарантирует, что элементы набора будут отсортированы (по возрастанию, естественный или указанный вами через его конструктор) (реализует _ 1_)
• не предлагает никаких параметров настройки для выполнения итераций
• предлагает несколько удобных методов для работы с упорядоченным набором, например _ 2_, last(), _ 4_ и tailSet() и т. Д.

Важные точки:

• Оба гарантируют сбор элементов без дублирования.
• Как правило, быстрее добавлять элементы в HashSet, а затем преобразовывать коллекцию в TreeSet для отсортированного обхода без дублирования.
• Ни одна из этих реализаций не синхронизирована. То есть, если несколько потоков обращаются к набору одновременно, и хотя бы один из потоков изменяет набор, он должен быть синхронизирован извне.
• LinkedHashSet в некотором смысле занимает промежуточное положение между HashSet и TreeSet. Однако, реализованный в виде хеш-таблицы со связанным списком, через нее проходит она обеспечивает итерацию с упорядоченной вставкой, которая отличается от отсортированного обхода, гарантированного TreeSet.

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

• e.g. SortedSet<String> s = new TreeSet<String>(hashSet);

Одно еще не упомянутое преимущество TreeSet состоит в том, что он имеет большую "локальность", что является сокращением для выражения (1) если две записи находятся рядом в порядке, TreeSet помещает их рядом друг с другом в структуре данных и, следовательно, в памяти. ; и (2) это размещение использует принцип локальности, согласно которому аналогичные данные часто используются приложением с одинаковой частотой.

В этом отличие от HashSet, который распределяет записи по всей памяти, независимо от их ключей.

Когда стоимость задержки чтения с жесткого диска в тысячи раз превышает стоимость чтения из кеша или ОЗУ, и когда доступ к данным действительно осуществляется с локального доступа, TreeSet может быть гораздо лучшим выбором.

Основываясь на прекрасном визуальном ответе на Картах от @shevchyk, вот мое мнение:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   Property   ║       HashSet       ║      TreeSet      ║     LinkedHashSet   ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║  no guarantee order ║ sorted according  ║                     ║
║   Order      ║ will remain constant║ to the natural    ║    insertion-order  ║
║              ║      over time      ║    ordering       ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ Add/remove   ║        O(1)         ║     O(log(n))     ║        O(1)         ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║   NavigableSet    ║                     ║
║  Interfaces  ║         Set         ║       Set         ║         Set         ║
║              ║                     ║    SortedSet      ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║    not allowed    ║                     ║
║  Null values ║       allowed       ║ 1st element only  ║      allowed        ║
║              ║                     ║     in Java 7     ║                     ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║              ║   Fail-fast behavior of an iterator cannot be guaranteed      ║
║   Fail-fast  ║ impossible to make any hard guarantees in the presence of     ║
║   behavior   ║           unsynchronized concurrent modification              ║
╠══════════════╬═══════════════════════════════════════════════════════════════╣
║      Is      ║                                                               ║
║ synchronized ║              implementation is not synchronized               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

HashSet - это O (1) для доступа к элементам, поэтому это, безусловно, имеет значение. Но поддерживать порядок объектов в наборе невозможно.

TreeSet полезен, если для вас важно поддержание порядка (с точки зрения значений, а не порядка вставки). Но, как вы заметили, вы торгуете приказом на более медленное время для доступа к элементу: O (log n) для базовых операций.

Из javadocs для TreeSet:

Эта реализация обеспечивает гарантированные временные затраты журнала (n) для основных операций (add, remove и contains).

1.HashSet допускает нулевой объект.

2.TreeSet не разрешает нулевой объект. Если вы попытаетесь добавить нулевое значение, это вызовет исключение NullPointerException.

3.HashSet намного быстрее, чем TreeSet.

e.g.

 TreeSet<String> ts = new TreeSet<String>();
 ts.add(null); // throws NullPointerException

 HashSet<String> hs = new HashSet<String>();
 hs.add(null); // runs fine

Причина, по которой чаще всего используется HashSet, заключается в том, что операции (в среднем) составляют O (1) вместо O (log n). Если набор содержит стандартные элементы, вы не будете «возиться с хеш-функциями», как это было сделано за вас. Если набор содержит пользовательские классы, вы должны реализовать hashCode для использования HashSet (хотя в Effective Java показано, как это сделать), но если вы используете TreeSet, вы должны сделать его Comparable или предоставить Comparator. Это может быть проблемой, если в классе нет определенного порядка.

Я иногда использовал TreeSet (или фактически TreeMap) для очень маленьких наборов / карт (‹10 элементов), хотя я не проверял, есть ли реальный выигрыш от этого. Для больших наборов разница может быть значительной.

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

Если вы не вставляете достаточно элементов, чтобы приводить к частым повторным хешированиям (или столкновениям, если ваш HashSet не может изменить размер), HashSet, безусловно, дает вам преимущество постоянного доступа по времени. Но на наборах с большим увеличением или уменьшением вы можете получить лучшую производительность с помощью Treesets, в зависимости от реализации.

Амортизированное время может быть близко к O (1) при работающем красно-черном дереве, если мне не изменяет память. У книги Окасаки было бы лучшее объяснение, чем я могу. (Или просмотрите его список публикаций)

Реализации HashSet, конечно, намного быстрее - меньше накладных расходов, потому что нет упорядочивания. Хороший анализ различных реализаций Set в Java представлен по адресу http://java.sun.com/docs/books/tutorial/collections/implementations/set.html.

Обсуждение там также указывает на интересный подход «золотой середины» к вопросу о дереве и хэше. Java предоставляет LinkedHashSet, который представляет собой HashSet с проходящим через него связанным списком, ориентированным на вставку, то есть последний элемент в связанном списке также является последним элементом, вставленным в Hash. Это позволяет избежать неправильного использования неупорядоченного хэша без увеличения стоимости TreeSet.

TreeSet - это одна из двух отсортированных коллекций (вторая - TreeMap). Он использует красно-черную древовидную структуру (но вы это знали) и гарантирует, что элементы будут располагаться в порядке возрастания в соответствии с естественным порядком. При желании вы можете создать TreeSet с конструктором, который позволяет вам дать коллекции свои собственные правила для того, каким должен быть порядок (вместо того, чтобы полагаться на порядок, определенный классом элементов), используя Comparable или Comparator

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

Зачем есть яблоки, если можно есть апельсины?

Серьезно, ребята и девчонки - если ваша коллекция большая, читается и записывается миллионы раз, и вы платите за циклы процессора, то выбор коллекции актуален ТОЛЬКО в том случае, если вам НУЖНО, чтобы она работала лучше. Однако в большинстве случаев это не имеет особого значения - несколько миллисекунд тут и там остаются незамеченными с точки зрения человека. Если это действительно так важно, почему вы не пишете код на ассемблере или C? [указать на другое обсуждение]. Итак, суть в том, что если вы довольны использованием той коллекции, которую выбрали, и это решает вашу проблему (даже если это не лучший тип коллекции для данной задачи), вы выбиваете себе самоуверенность. Программное обеспечение податливо. При необходимости оптимизируйте свой код. Дядя Боб говорит, что преждевременная оптимизация - это корень всех зол. Так говорит дядя Боб

Даже спустя 11 лет никто не подумал упомянуть о очень важной разнице.

Считаете ли вы, что если HashSet равно TreeSet, то верно и обратное? Взгляните на этот код:

TreeSet<String> treeSet = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
HashSet<String> hashSet = new HashSet<>();
treeSet.add("a");
hashSet.add("A");
System.out.println(hashSet.equals(treeSet));
System.out.println(treeSet.equals(hashSet));

Попробуйте угадать результат, а затем наведите указатель мыши на фрагмент, чтобы увидеть, каков реальный результат. Готовый? Ну вот:

ложь
истина

Правильно, они не содержат отношения эквивалентности для компаратора, несовместимого с равенством. Причина этого в том, что TreeSet использует компаратор для определения эквивалентности, а HashSet использует equals. Внутри они используют HashMap и TreeMap, поэтому вы должны ожидать такого поведения и с упомянутыми Map.

Первоначальный ответ

Редактировать сообщение (полное переписывание) Когда порядок не имеет значения, вот когда. Оба должны выдавать Log (n) - было бы полезно посмотреть, быстрее ли один из них более чем на пять процентов. HashSet может дать тест O (1) в цикле, чтобы выяснить, есть ли это.

Было дано множество ответов, основанных на технических соображениях, особенно в отношении производительности. На мой взгляд, выбор между TreeSet и HashSet имеет значение.

Но я бы предпочел, чтобы выбор в первую очередь был обусловлен концептуальными соображениями.

Если для объектов вам нужно манипулировать, естественный порядок не имеет смысла, тогда не используйте TreeSet.
Это отсортированный набор, поскольку он реализует SortedSet. Это означает, что вам нужно переопределить функцию compareTo, которая должна соответствовать тому, что возвращает функция equals. Например, если у вас есть набор объектов класса Student, то я не думаю, что TreeSet будет иметь смысл, поскольку между учениками нет естественного порядка. Вы можете отсортировать их по средней оценке, но это не «естественный порядок». Функция compareTo вернет 0 не только тогда, когда два объекта представляют одного и того же учащегося, но также и тогда, когда у двух разных учеников одинаковая оценка. Во втором случае equals вернет false (если вы не решите сделать последнее возвращать true, когда два разных студента имеют одинаковую оценку, что приведет к тому, что функция equals будет иметь вводящее в заблуждение значение, если не сказать неправильное значение.)
Обратите внимание, что соответствие между equals и compareTo необязательно, но настоятельно рекомендуется. В противном случае контракт интерфейса Set будет нарушен, что приведет к тому, что ваш код будет вводить в заблуждение других людей, что также может привести к неожиданному поведению.

Эта ссылка может быть хорошим источником информации по этому вопросу.