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

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

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

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

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

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

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

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

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

Из javadocs для TreeSet :

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

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

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

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

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

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

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