Хэшсет против Трисет

Я всегда любил деревья, это мило O(n*log(n)) и чистота их. Тем не менее, каждый программист, которого я когда-либо знал, спрашивал меня, почему я бы использовал TreeSet, Исходя из опыта работы с CS, я не думаю, что это так важно, как вы используете, и я не хочу возиться с хэш-функциями и контейнерами (в случае Java).

В каких случаях я должен использовать HashSet через TreeSet?

Источник

13 ответов

Решение

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

HashSet

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

TreeSet

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

Важные моменты:

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

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

  • например SortedSet<String> s = new TreeSet<String>(hashSet);
Источник

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

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

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

Источник

Основываясь на прекрасном визуальном ответе на Maps от @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) для основных операций.

Из ага дляTreeSet:

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

Источник

1.HashSet позволяет нулевой объект.

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

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

например

 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 (хотя Эффективная 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.

Источник

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

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

Источник

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

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

Источник

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

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

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

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

Источник

Даже спустя 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 поэтому вы должны ожидать такого поведения с упомянутым Maps тоже.

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

Источник

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

Источник 
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class HashTreeSetCompare {

    //It is generally faster to add elements to the HashSet and then
    //convert the collection to a TreeSet for a duplicate-free sorted
    //Traversal.

    //really? 
    O(Hash + tree set) > O(tree set) ??
    Really???? Why?



    public static void main(String args[]) {

        int size = 80000;
        useHashThenTreeSet(size);
        useTreeSetOnly(size);

    }

    private static void useTreeSetOnly(int size) {

        System.out.println("useTreeSetOnly: ");
        long start = System.currentTimeMillis();
        Set<String> sortedSet = new TreeSet<String>();

        for (int i = 0; i < size; i++) {
            sortedSet.add(i + "");
        }

        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useTreeSetOnly: " + (end - start));
    }

    private static void useHashThenTreeSet(int size) {

        System.out.println("useHashThenTreeSet: ");
        long start = System.currentTimeMillis();
        Set<String> set = new HashSet<String>();

        for (int i = 0; i < size; i++) {
            set.add(i + "");
        }

        Set<String> sortedSet = new TreeSet<String>(set);
        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useHashThenTreeSet: " + (end - start));
    }
}
Источник
Другие вопросы по тегам