why it is better to convert hashset to treeset then working directly with treeset

Question

In many places in the web including sun website, the following sentence appear:

It generally faster to preform actions on hashSet and then convert the hashset to treeset.

well, i'm a little bit confused, thats correct that add element in hashset is o(1) and adding object in treeset (black & red tree) is o(logn) but when i convert the hashset to the treeset i need to sort my data which is o(nlogn) so why it is faster to work with hashset and then convert it to treeset? i know that if you preform remove or existing element so there is a diffrence between hash and tree but i don't think it is the factor that sun refer to (at least i hope so since it looks like a very small thing) another thing is the hashcode methods can be not so good and then adding elements to the hash will not be o(1) or the hashcode method can be complicated. so generally i don't understand the sentence. can anyone help me?

Answer 1

It depends on how many operations happen in the hash table before you copy the elements to the sorted tree structure. If all you do is insert n distinct elements to the hash table, then no, it will not be faster to do so then copy them to the tree :)

A hashed set of items can be converted to a sorted tree by either: using a regular sort then building the tree from that, or inserting the items into the tree one at a time. The former means an extra copy/traversal; the latter means extra overhead to maintain a balanced tree (although if you iterate a hash table, you get the items in effectively random order, which means you could probably avoid most rebalancing).

Hash tables are indeed typically faster than search trees for the operations that are well supported (insert/modify/delete), but it's definitely not worth doing what Sun recommends until you actually measure the performance of your whole application and can expect a valuable overall speedup from what will likely be a slight improvement.

Hash tables do have an even larger advantage over sorted trees when the key comparison is expensive (as with strings), because for large sets, fewer items will have a hash collision than a search tree is deep, and because it's possible to cache the hash code for keys already in the set, skipping the expensive comparison for (probably) all but the matching result.