почему лучше конвертировать hashset в treeset, чем работать напрямую с treeset

Question

Во многих местах в Интернете, включая сайт Sun, появляется следующее предложение:

Это обычно быстрее, чтобы преформ действий на hashSet, а затем преобразовать hashset до treeset.

Хорошо, я немного запутался, это правильно, добавление элемента в hashset - это o(1), а добавление объекта в treeset (черно-красное дерево) - o(logn), но когда я конвертирую хэш-набор в набор деревьев мне нужно отсортировать мои данные o(nlogn), так почему же работать с hashset быстрее, а затем преобразовать их в treeset? я знаю, что если вы преформуете удаление или существующий элемент, то есть разница между хешем и деревом, но я не думаю, что это тот фактор, на который ссылается солнце (по крайней мере, я на это надеюсь, так как это выглядит как очень малая вещь) если методы hashcode могут быть не очень хорошими, то добавление элементов в хэш не будет o(1) или метод hashcode может быть сложным. так что обычно я не понимаю предложение. кто-нибудь может мне помочь?

Answer 1

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

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

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

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