Is iterating through a TreeSet slower than iterati

I'm running some benchmarks. One of my tests depends on order, so I'm using a TreeSet for that. My second test doesn't, so I'm using a HashSet for it.

I know that insertion is slower for the TreeSet. But what about iterating through all elements?

回答1:

From a similar post (Hashset vs Treeset):

HashSet is much faster than TreeSet (constant-time versus log-time for most operations like add, remove and contains) but offers no ordering guarantees like TreeSet.

HashSet:

class offers constant time performance for the basic operations (add, remove, contains and size).
it does not guarantee that the order of elements will remain constant over time
iteration performance depends on the initial capacity and the load factor of the HashSet.
- It's quite safe to accept default load factor but you may want to specify an initial capacity that's about twice the size to which you expect the set to grow.

TreeSet:

guarantees log(n) time cost for the basic operations (add, remove and contains)
guarantees that elements of set will be sorted (ascending, natural, or the one specified by you via it's constructor)
doesn't offer any tuning parameters for iteration performance
offers a few handy methods to deal with the ordered set like first(), last(), headSet(), and tailSet() etc

Important points:

Both guarantee duplicate-free collection of elements
It is generally faster to add elements to the HashSet and then convert the collection to a TreeSet for a duplicate-free sorted traversal.
None of these implementation are synchronized. That is if multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
LinkedHashSet is in some sense intermediate between HashSet and TreeSet. Implemented as a hash table with a linked list running through it, however it provides insertion-ordered iteration which is not same as sorted traversal guaranteed by TreeSet.

So choice of usage depends entirely on your needs but I feel that even if you need an ordered collection then you should still prefer HashSet to create the Set and then convert it into TreeSet.

e.g. Set<String> s = new TreeSet<String>(hashSet);

回答2:

TreeSets internally uses TreeMaps which are Red Black Trees (special type of BST) .

BST Inorder Traversal is O(n)

HashSets internally uses HashMaps which use an array for holding Entry objects.

Here also traversal should be O(n) .

Unless you write a benchmark it is going to be difficult to prove which is faster.

回答3:

If you want stable ordering with (nearly) the performance of a HashSet, then use a LinkedHashSet. You will still get constant-time operations, whereas I would assume a TreeSet will get you logarithmic time.