HashSet vs TreeSet vs LinkedHashSetSet接口HashSet，TreeSet，LinkedHashSet对比TreeSet例子HashSet例子LinkedHashSet例子性能测试

Set接口继承Collection接口。Set集合不允许里面存在重复元素，每个元素都必须是唯一的。你只需要往Set集合简单的添加元素，重复元素会被自动移除。

HashSet是基于散列表实现的，元素没有顺序；add、remove、contains方法的时间复杂度为O(1)。

TreeSet是基于树实现的（红黑树），元素是有序的；add、remove、contains方法的时间复杂度为O(log (n))。因为元素是有序的，它提供了若干个相关方法如first(), last(), headSet(), tailSet()等；

LinkedHashSet介于HashSet和TreeSet之间，是基于哈希表和链表实现的，支持元素的插入顺序；基本方法的时间复杂度为O(1)；

结果输出：

Tree set data: 12 34 45 63

现在，我们换个元素类型，在进行插入，首先定义一个Dog类，如下

然后，往TreeSet添加若干个Dog对象，如下：

以上代码，编译OK，但是运行时报错，如下：

Exception in thread "main" java.lang.ClassCastException: simplejava.Dog cannot be cast to java.lang.Comparable

    at java.util.TreeMap.compare(TreeMap.java:1188)

    at java.util.TreeMap.put(TreeMap.java:531)

    at java.util.TreeSet.add(TreeSet.java:255)

    at simplejava.Q17.main(Q17.java:22)

为什么呢？因为TreeSet是有序的，Dog类需要实现java.lang.Comparable接口的compareTo()，如下：

1 2 3

5 3 2 1 4

注意顺序是不确定的。

结果输出如下，保存了插入顺序：

2 1 3 5 4

以下代码测试了这三个类add方法的性能：

结果如下，我们可以发现，HashSet性能最好（注：以上代码我自己本地测试，HashSet不一定比LinkedHashSet快...）。

HashSet: 2244768

TreeSet: 3549314

LinkedHashSet: 2263320

这个测试并不是很精准，但是基本可以反映出TreeSet是性能最差的，因为需要排序。

本文转自风一样的码农博客园博客，原文链接：http://www.cnblogs.com/chenpi/p/5497125.html，如需转载请自行联系原作者