Java集合源碼學習（五）幾種常用集合類的比較

這篇筆記對幾個常用的集合實作，從效率，線程安全和應用場景進行綜合比較。

（1）相同和不同

都實作了list接口，使用類似。

vector和arraylist的底層實作都是數組，這一點與linkedlist的雙向連結清單不同。

vector和arraylist在更多元素添加進來時會請求更大的空間。vector每次請求其大小的雙倍空間，而arraylist每次對size增長50%。

（2）線程安全

arraylist、linkedlist都沒有進行同步，可以使用 collections的同步方法進行包裝。

（3）性能比較

在arraylist和vector中，從一個指定的位置（通過索引）查找資料或是在集合的末尾增加、移除一個元素所花費的時間是一樣的，這個時間我們用o(1)表示。但是，如果在集合的其他位置增加或移除元素那麼花費的時間會呈線形增長：o(n-i)，其中n代表集合中元素的個數，i代表元素增加或移除元素的索引位置，即時間複雜度o(n)。為什麼會這樣呢？因為數組在記憶體上是連續的，進行上述操作的時候集合中第i和第i個元素之後的所有元素都要執行位移的操作。

如果你隻是查找特定位置的元素或隻在集合的末端增加、移除元素，那麼使用vector或arraylist都可以。如果是其他操作，你最好選擇其他的集合操作類。比如，linklist集合類在增加或移除集合中任何位置的元素所花費的時間都是一樣的o(1)，但它在索引一個元素的是有比較慢，o(i)，其中i是索引的位置。

（1）是否允許空值

hashmap允許 null 值(key和value都可以)，hashtable不允許 null 值(key 和 value 都不可以)，

這一點在之前學習源碼時也注意到了，看一下hashtable的源碼：

1

2

3

4

5

6

7

<code>public synchronized v put(k key, v value) {</code>

<code>       </code><code>// make sure the value is not null</code>

<code>       </code><code>if (value == null) {</code>

<code>           </code><code>throw new nullpointerexception();</code>

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

<code>       </code><code>......</code>

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

（2）哈希值的使用不同

hashtable直接使用對象的hashcode，代碼是這樣的：

<code>int hash = key.hashcode();</code>

<code>int index = (hash &amp; 0x7fffffff) % tab.length;</code>

而hashmap重新計算hash值，這一點在之前的分析中也看到了：

<code>int hash = hash(k);</code>

<code>int i = indexfor(hash, table.length);</code>

另外還有一些如内部連結清單數組使用方式不同等差異。

（3）線程安全

hashmap和hashtable線上程安全性上就如同arraylist和vector類似，

hashtable的操作都使用synchronized做了同步。需要注意這是一種性能較低的線程安全。

hashset 實作了 set 接口，它不允許集合中有重複的值，在将對象存儲在 hashset 之前，要先確定對象重寫 equals()和 hashcode()方法，這樣才能比較對象的值是否相等，以確定set中沒有儲存相等的對象。

hashmap 實作了 map 接口，map 接口對鍵值對進行映射。map 中不允許重複的鍵。map 接口有兩個基本的實作，hashmap 和 treemap。treemap 儲存了對象的排列次序，而 hashmap 則不能。hashmap 允許鍵和值為 null。

（1）不同之處

hashmap實作了map接口 hashset實作了set接口

hashmap儲存鍵值對 hashset僅僅存儲對象

使用put()方法将元素放入map中 使用add()方法将元素放入set中

hashmap中使用鍵對象來計算hashcode值 hashset使用成員對象來計算hashcode值，對于兩個對象來說hashcode可能相同，是以equals()方法用來判斷對象的相等性，如果兩個對象不同的話，那麼傳回false

hashmap比較快，因為是使用唯一的鍵來擷取對象 hashset較hashmap來說比較慢

hashmap 是非 synchronized 的。