Для поиска HashSet против Treeset

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

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

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

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

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

С javadocs для TreeSet:

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

1.Для поиска HashSet обеспечивает нулевой объект.

2.TreeSet не позволит нулевой объект. Если вы попытаетесь добавить значение null, оно вызовет исключение 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

основываясь на прекрасные визуальный ответ на картах @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 (хотя эффективная Java показывает, как), но если вы используете TreeSet вы должны сделать это Comparable или поставить Comparator. Это может быть проблемой, если класс не имеет особого порядок.

Я иногда использовал TreeSet (или на самом деле TreeMap) для очень маленьких наборов/карт (

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

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

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

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

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

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

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

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

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

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

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

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

серьезно, ребята и девочки - если ваша коллекция большая, читается и пишется в gazillions раз, и вы платите за циклы процессора, то выбор коллекции актуален только в том случае, если вам нужно, чтобы она работала лучше. Однако в большинстве случаев это не имеет большого значения - несколько миллисекунд здесь и там остаются незамеченными в человеческих терминах. Если это действительно так важно, почему вы не пишете код на ассемблере или 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));
    }
}