CODEWITHSUNDEEP
javahashsetcomparetotreeset
Daniel Mac
Daniel Mac

Reputation: 382

TreeSet and compareTo() method. Single sort or multiple sorts

Im currently working on a program, where im using a TreeSet to store unique keys. I'm using a TreeSet, because I want them sorted.

As of now, I have been making a TreeSet object, and added the strings one-at-a-time, when needed.

TreeSet set = new TreeSet();
set.add("How");
set.add("Are");
set.add("You");

Supposedly, the TreeSet uses the compareTo method in the Compareable interface, to sort the strings. That would mean that the TreeSet would have to do a sort each time I add a String to it.

Now my question is this: Would it be more efficient to create a HashSet and then create the TreeSet after all strings are added to the HashSet? 

TreeSet<String> treeSet = new TreeSet<String>(set);

My thoughts are going about whether the TreeSet would only need to do a single sort that way.

Thanks in advance

Upvotes: 2

Views: 1586

Answers (3)

BobMcGee
BobMcGee

Reputation: 20110

ConcurrentSkipListSet might offer better performance, depending.

This is based on an implementation of a sorted SkipList. Asymptotic performance is O(log n) like a TreeSet, but it is supposed to be faster in general, and more storage-compact. Plus, java includes the implementation already!

It might very well be faster to create the skiplist list from a sorted arraylist, depending on the implementation. Bulk additions are usually faster than one-by-one (depending on the implementation). The TreeSet represents something of an exception. Profile and find out!

Upvotes: 0

Yogendra Singh
Yogendra Singh

Reputation: 34367

It won't make any difference as it internally calls the "addAll()" method, which in turn, adds one element at a time.

public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    Iterator<? extends E> e = c.iterator();
    while (e.hasNext()) {
        if (add(e.next()))    //< -- Add one element at a time
           modified = true;
    }
    return modified;
}

Upvotes: 0

nosid
nosid

Reputation: 50044

TreeSet is a Self-balancing binary search tree. That means it will do log(n, 2) comparisons for each insert. It makes no difference if you add the elements independently or create the TreeSet from another collection.

Upvotes: 5

Related Questions