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

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

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

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);

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

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

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

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

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

Из Javadocs дляTreeSet :

Эта реализация обеспечивает гарантированные затраты времени log (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

Основываясь на прекрасном визуальном ответе на 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) вместо O (log n). Если набор содержит стандартные элементы, вы не будете "возиться с хэш-функциями", как это было сделано для вас. Если набор содержит пользовательские классы, вы должны реализовать его hashCodeдля использования HashSet(хотя Effective Java показывает, как), но если вы используете a, 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 позволяет перебирать элементы в том порядке, в котором они были вставлены.

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

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

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

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

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

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

Редактирование сообщения ( полное переписывание ) Когда порядок не имеет значения, это когда. Оба должны дать 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));
    }
}