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，如需轉載請自行聯系原作者