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

Question

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

Answer 1

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.

Answer 2

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;
}

Answer 3

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!