3.4 Set

Set是一個接口，這個接口約定了在其中的數據是不能重復的，它有許多不同的實現類，圖3-15給出了常用的Set的實現類。

這一節重點介紹其中的三個：HashSet、LinkedHashSet和TreeSet。

3.4.1 HashSet

在介紹HashSet之前，首先需要理解HashSet的兩個重要的特性：

1）HashSet中不會有重復的元素；

2）HashSet中最多只允許有一個null。

顯然HashMap也有著相同的特性：HashMap的key不能有重復的元素，key最多也只能有一個null。正因為如此，HashSet內部是通過HashMap來實現的。只不過對于HashMap來說，每個key可以有自己的value；而在HashSet中，由于只關心key的值，因此所有的key都會使用相同的value（PRESENT）。由于PRESENT被定義為static，因此會被所有的對象共享，這樣的實現顯然會節約空間。

需要注意的是：

1）HashSet不是線程安全的，如果想使用線程安全的Set，那么可以使用CopyOnWriteArraySet、Collections.synchronizedSet(Set set)、ConcurrentSkipListSet和Collections.newSetFromMap(NewConcur-rentHashMap)。

2）HashSet不會維護數據插入的順序，如果想維護插入順序，那么可以使用LinkedHashSet。

3）HashSet也不會對數據進行排序，如果想對數據進行排序，那么可以使用TreeSet。

HashSet的使用示例代碼如下：

從運行結果可以看出，HashSet中的數據是無序的。

3.4.2 LinkedHashSet

LinkedHashSet是HashSet的擴展，HashSet并不維護數據的順序，而LinkedHashSet維護了數據插入的順序。HashSet在內部是使用HashMap來實現的，而LinkedHashSet內部通過LinkedHashMap來實現。

示例代碼如下：

從運行結果可以看出LinkedHashSet維護了數據插入的順序。

3.4.3 TreeSet

TreeSet不僅有HashSet所有的特性，而且它還增加了一個排序的特性。也就是說TreeSet中的數據是有序的，它默認使用的是數據的自然順序，當然在創建TreeSet的時候也可以指定Comparator來對數據進行排序。那么TreeSet底層是如何實現數據排序的，下面給出TreeSet內部實現的部分源碼：

通過源碼可以發現，它的實現與HashMap類似，底層使用TreeMap來存儲數據，因此把數據有序功能的實現交給了TreeMap。這里重點介紹一下add方法。對于TreeMap而言，它的返回值有兩種情況：

1）如果新增加的key是唯一的，那么它會返回null；

2）如果新增加的key在TreeMap中已經存在了，那么它會返回key對應的value值。

因此TreeSet的add方法正是通過這個返回值來判斷新的數據是否被加入進去：如果put方法返回null，那么說明數據被插入到TreeSet中了，此時map.put(e, PRESENT)==null的值為true，因此add方法返回true。否則返回false表示數據已經在TreeSet中了，不需要再次插入了。

對于其他的方法而言，它們的實現與HashSet類似，交給底層TreeMap來實現了。

示例代碼如下：

從運行結果可以看出，TreeMap維護了數據的順序。