Java 容器 & 泛型：三、HashSet，TreeSet 和 LinkedHashSet比較

一個不包括重複元素（包括可變對象）的collection，是一種無序的集合。set不包含滿 a.equals(b) 的元素對a和b，并且最多有一個null。

泥瓦匠的記憶宮殿：

1、不允許包含相同元素

2、判斷對象是否相同，根據equals方法

一個按着hash算法來存儲集合中的元素，其元素值可以是null。它不能保證元素的排列順序。同樣，hashset是不同步的，如果需要多線程通路它的話，可以用 collections.synchronizedset 方法來包裝它：

<a href="http://www.bysocket.com/?p=195#">?</a>

1

<code>set s = collections.synchronizedset(new hashset(...));</code>

同上一節一樣，用疊代器的時候，也要注意 并發修改異常concurrentmodificationexception。

要注意的地方是，hashset集合判斷兩個元素相等不單單是equals方法，并且必須hashcode()方法傳回值也要相等。看下面的例子：

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

<code>import java.util.hashset;</code>

<code>class euqalsobj</code>

<code>{</code>

<code>    </code><code>public boolean equals(object obj)</code>

<code>    </code><code>{</code>

<code>        </code><code>return true;</code>

<code>    </code><code>}</code>

<code>}</code>

<code>class hashcodeobj</code>

<code>    </code><code>public int hashcode()</code>

<code>        </code><code>return 1;</code>

<code>class hashsetobj</code>

<code>        </code><code>return 2;</code>

<code>public class hashsettest</code>

<code>    </code><code>public static void main(string[] args)</code>

<code>        </code><code>hashset objs = new hashset();</code>

<code>        </code><code>objs.add(new euqalsobj());</code>

<code>        </code><code>objs.add(new hashcodeobj());</code>

<code>        </code><code>objs.add(new hashsetobj());</code>

<code>        </code> 

<code>        </code><code>system.out.println("hashset elements:");</code>

<code>        </code><code>system.out.print("\t" + objs + "\n");</code>

run 一下，控制台如下輸出：

<code>hashset elements:</code>

<code>    </code><code>[hashcodeobj@1, hashcodeobj@1, hashsetobj@2, euqalsobj@1471cb25, euqalsobj@3acff49f]</code>

泥瓦匠根據結果，一一到來。首先，排列順序不定。

hashsetobj 類滿足我們剛剛的要求，是以集合中隻有一個且它的hashcode值為2。

hashcodeobj 類雖然它們hashcode值為1，但是他們不相等。（其實當hashcode值一樣，這個存儲位置會采用鍊式結構儲存兩個hashcodeobj對象。）

同樣,equalsobj 類他們相等，但是他們hashcode值不等，分别為1471cb25、3acff49f。

是以，用hashset添加可變對象，要注意當對象有可能修改後和其他對象沖突，這樣我們無法從hashset找到準确我們需要的對象。

hashset的子類，也同樣有hashcode值來決定元素位置。但是它使用連結清單維護元素的次序。記住兩個字：有序。

有序的妙用，複制。比如泥瓦匠實作一個hashset無序添加，然後複制一個一樣次序的hashset來。代碼如下：

<code>package com.sedion.bysocket.collection;</code>

<code>import java.util.linkedhashset;</code>

<code>import java.util.set;</code>

<code>public class linkedhashlisttest</code>

<code>        </code><code>/* 複制hashset */</code>

<code>        </code><code>set h1 = new hashset&lt;</code><code>string</code><code>&gt;();</code>

<code>        </code><code>h1.add("list");</code>

<code>        </code><code>h1.add("queue");</code>

<code>        </code><code>h1.add("set");</code>

<code>        </code><code>h1.add("map");</code>

<code>        </code><code>system.out.print("\t" + h1 + "\n");</code>

<code>        </code><code>set h2 = copy(h1);</code>

<code>        </code><code>system.out.println("hashset elements after copy:");</code>

<code>        </code><code>system.out.print("\t" + h2 + "\n");</code>

<code>    </code> 

<code>    </code><code>@suppresswarnings({ "rawtypes", "unchecked" })</code>

<code>    </code><code>public static set copy(set set)</code>

<code>        </code><code>set setcopy = new linkedhashset(set);</code>

<code>        </code><code>return setcopy;</code>

run 一下，控制台輸出：

<code>    </code><code>[map, queue, set, list]</code>

<code>hashset elements after copy:</code>

可見，每個資料結構都有它存在的理由。

treeset使用樹結構實作（紅黑樹），集合中的元素進行排序，但是添加、删除和包含的算法複雜度為o（log（n））。

舉個例子吧，首先我們定義一個bird類。（鳥是泥瓦匠最喜歡的動物）

<code>class bird</code>

<code>    </code><code>int size;</code>

<code>    </code><code>public bird(int s)</code>

<code>        </code><code>size = s;</code>

<code>    </code><code>public string tostring()</code>

<code>        </code><code>return size + "";</code>

然後用treeset添加bird類。

<code>public class treesettest</code>

<code>        </code><code>treeset&lt;</code><code>bird</code><code>&gt; bset = new treeset&lt;</code><code>bird</code><code>&gt;();</code>

<code>        </code><code>bset.add(new bird(1));</code>

<code>        </code><code>bset.add(new bird(3));</code>

<code>        </code><code>bset.add(new bird(2));</code>

<code>        </code><code>iterator&lt;</code><code>bird</code><code>&gt; iter = bset.iterator();</code>

<code>        </code><code>while (iter.hasnext())</code>

<code>        </code><code>{</code>

<code>            </code><code>bird bird = (bird) iter.next();</code>

<code>            </code><code>system.out.println(bird);</code>

<code>        </code><code>}</code>

run一下,控制台輸出如下：

<code>exception in thread "main" java.lang.classcastexception: bird cannot be cast to java.lang.comparable</code>

<code>    </code><code>at java.util.treemap.compare(unknown source)</code>

<code>    </code><code>at java.util.treemap.put(unknown source)</code>

<code>    </code><code>at java.util.treeset.add(unknown source)</code>

<code>    </code><code>at com.sedion.bysocket.collection.treesettest.main(treesettest.java:29)</code>

答案很明顯，treeset是排序的。是以bird需要實作comparable此接口。

java.lang.comparable此接口強行對實作它的每個類的對象進行整體排序。這種排序被稱為類的自然排序，類的 compareto 方法被稱為它的自然比較方法。

修改bird如下：

<code>class bird implements comparable&lt;</code><code>bird</code><code>&gt;</code>

<code>        </code><code>return size + "号鳥";</code>

<code>    </code><code>@override</code>

<code>    </code><code>public int compareto(bird o)</code>

<code>        </code><code>return size - o.size;</code>

再次run一下：

<code>1号鳥</code>

<code>2号鳥</code>

<code>3号鳥</code>

五、性能測試比較

針對上面三種set集合，我們對它們的add方法進行性能測試：

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

<code>import java.util.random;</code>

<code>import java.util.treeset;</code>

<code>public class set</code>

<code>        </code><code>random r = new random();</code>

<code>         </code> 

<code>        </code><code>hashset&lt;</code><code>bird</code><code>&gt; hashset = new hashset&lt;</code><code>bird</code><code>&gt;();</code>

<code>        </code><code>treeset&lt;</code><code>bird</code><code>&gt; treeset = new treeset&lt;</code><code>bird</code><code>&gt;();</code>

<code>        </code><code>linkedhashset&lt;</code><code>bird</code><code>&gt; linkedset = new linkedhashset&lt;</code><code>bird</code><code>&gt;();</code>

<code>     </code> 

<code>        </code><code>// start time</code>

<code>        </code><code>long starttime = system.nanotime();</code>

<code>        </code><code>for (int i = 0; i &lt; 1000; i++) {</code>

<code>            </code><code>int x = r.nextint(1000 - 10) + 10;</code>

<code>            </code><code>hashset.add(new bird(x));</code>

<code>        </code><code>// end time</code>

<code>        </code><code>long endtime = system.nanotime();</code>

<code>        </code><code>long duration = endtime - starttime;</code>

<code>        </code><code>system.out.println("hashset: " + duration);</code>

<code>        </code><code>starttime = system.nanotime();</code>

<code>            </code><code>treeset.add(new bird(x));</code>

<code>        </code><code>endtime = system.nanotime();</code>

<code>        </code><code>duration = endtime - starttime;</code>

<code>        </code><code>system.out.println("treeset: " + duration);</code>

<code>            </code><code>linkedset.add(new bird(x));</code>

<code>        </code><code>system.out.println("linkedhashset: " + duration);</code>

run一下，可以在控制台中看出：

<code>hashset: 2610998</code>

<code>treeset: 3195378</code>

<code>linkedhashset: 2673782</code>

可見，treeset因為需要進行比較，是以性能比較差。

hashset：equlas hashcode

linkedhashset：鍊式結構

treeset：比較，comparable接口，性能較差