TreeSet的一个尚未被提及的优点是它有更大的“局部性”，这是以下说法的简写:(1)如果两个条目在顺序上是相邻的，TreeSet将它们放在数据结构中彼此相邻的地方，因此在内存中也是如此;并且(2)这种布局利用了局部性原则，该原则说类似的数据通常被一个应用程序以相似的频率访问。

这与HashSet相反，HashSet将条目分布在内存中，而不管它们的键是什么。

当从硬盘读取的延迟成本是从缓存或RAM读取的延迟成本的数千倍，并且当数据确实是通过局部性访问时，TreeSet可能是更好的选择。

TreeSet的一个尚未被提及的优点是它有更大的“局部性”，这是以下说法的简写:(1)如果两个条目在顺序上是相邻的，TreeSet将它们放在数据结构中彼此相邻的地方，因此在内存中也是如此;并且(2)这种布局利用了局部性原则，该原则说类似的数据通常被一个应用程序以相似的频率访问。

这与HashSet相反，HashSet将条目分布在内存中，而不管它们的键是什么。

当从硬盘读取的延迟成本是从缓存或RAM读取的延迟成本的数千倍，并且当数据确实是通过局部性访问时，TreeSet可能是更好的选择。

如果您没有插入足够多的元素导致频繁重散列(或冲突，如果您的HashSet不能调整大小)，那么HashSet当然可以为您提供常量时间访问的好处。但是对于有大量增长或收缩的集合，使用Treesets实际上可能会获得更好的性能，这取决于实现。

如果我没记错的话，平摊时间可以接近于一个功能性红黑树的O(1)。冈崎的书会有比我更好的解释。(或参阅他的出版物列表)

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class HashTreeSetCompare {

    //It is generally faster to add elements to the HashSet and then
    //convert the collection to a TreeSet for a duplicate-free sorted
    //Traversal.

    //really? 
    O(Hash + tree set) > O(tree set) ??
    Really???? Why?



    public static void main(String args[]) {

        int size = 80000;
        useHashThenTreeSet(size);
        useTreeSetOnly(size);

    }

    private static void useTreeSetOnly(int size) {

        System.out.println("useTreeSetOnly: ");
        long start = System.currentTimeMillis();
        Set<String> sortedSet = new TreeSet<String>();

        for (int i = 0; i < size; i++) {
            sortedSet.add(i + "");
        }

        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useTreeSetOnly: " + (end - start));
    }

    private static void useHashThenTreeSet(int size) {

        System.out.println("useHashThenTreeSet: ");
        long start = System.currentTimeMillis();
        Set<String> set = new HashSet<String>();

        for (int i = 0; i < size; i++) {
            set.add(i + "");
        }

        Set<String> sortedSet = new TreeSet<String>(set);
        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useHashThenTreeSet: " + (end - start));
    }
}

消息编辑(完全重写)当顺序无关紧要时，就是这样。两者都应该给出Log(n) -看看其中一个是否比另一个快5%以上是有用的。HashSet可以在循环中给出O(1)测试，应该可以揭示它是否正确。

TreeSet是两个排序集合之一(另一个是 TreeMap)。它使用红黑树结构(但你知道)，并保证 元素会按照自然的顺序，按升序排列。可选地, 您可以使用构造函数构造TreeSet，该构造函数允许您为集合提供您的 自己制定顺序规则(而不是依赖于定义的顺序) 通过使用Comparable或Comparator)

LinkedHashSet是HashSet的有序版本 在所有元素之间维护一个双链接列表。使用这个类而不是HashSet 当你关心迭代顺序时。迭代HashSet时 顺序是不可预测的，而LinkedHashSet允许您迭代元素 按照它们被插入的顺序