Java集合架構詳解

這篇文章詳細對比以及分析了java的集合架構的原理使用以及比較。

arraylist就是傳說中的動态數組，就是array的複雜版本，它提供了如下一些好處：動态的增加和減少元素、靈活的設定數組的大小……

arraylist底層是數組，并且add remove指定位置元素的時候，是通過memcpy來實作的。我們直接來看源碼：

arraylist源碼分析：

<a></a>

源碼中存放資料的數組是用transient關鍵字定義的

那什麼是transient呢？

java的serialization提供了一種持久化對象執行個體的機制。當持久化對象時，可能有一個特殊的對象資料成員，我們不想用serialization機制來儲存它。為了在一個特定對象的一個域上關閉serialization，可以在這個域前加上關鍵字transient。

ansient是java語言的關鍵字，用來表示一個域不是該對象串行化的一部分。當一個對象被串行化的時候，transient型變量的值不包括在串行化的表示中，然而非transient型的變量是被包括進去的。

在使用arraylist的toarray方法時候，因為不支援object[]向下轉型，是以我們使用 t[] toarray(t[] a) 這個方法。

下面是使用方法：

linkedlist也和arraylist一樣實作了list接口，但是它執行插入和删除操作時比arraylist更加高效，因為它是基于連結清單的。基于連結清單也決定了它在随機通路方面要比arraylist遜色一點。

vector實際上實作的原理和arraylist大部分都相同，不同的地方就是它絕大部分方法都使用了synchronized同步。是以會很影響性能。

源碼就不看了，如果想看的朋友可以看看這篇文章：

<a href="http://blog.csdn.net/chenssy/article/details/37520981" target="_blank">vector詳解</a>

對于hashset而言，它是基于hashmap實作的，hashset底層采用hashmap來儲存所有元素，是以hashset的實作比較簡單，檢視hashset的源代碼，可以看到：

由上面源程式可以看出，hashset 的實作其實非常簡單，它隻是封裝了一個 hashmap 對象來存儲所有的集合元素，所有放入 hashset 中的集合元素實際上由 hashmap 的 key 來儲存，而 hashmap 的 value 則存儲了一個 present，它是一個靜态的 object 對象。

hashset 的絕大部分方法都是通過調用 hashmap 的方法來實作的，是以 hashset 和 hashmap 兩個集合在實作本質上是相同的。

下面是一個hashset的例子：

這段測試居然輸出false。這是因為 hashset 判斷兩個對象相等的标準除了要求通過 equals() 方法比較傳回 true 之外，還要求兩個對象的 hashcode() 傳回值相等。而上面程式沒有重寫 name 類的 hashcode() 方法，兩個 name 對象的 hashcode() 傳回值并不相同，是以 hashset 會把它們當成 2 個對象處理，是以程式傳回 false。

由此可見，當我們試圖把某個類的對象當成 hashmap 的 key，或試圖将這個類的對象放入 hashset 中儲存時，重寫該類的 equals(object obj) 方法和 hashcode() 方法很重要，而且這兩個方法的傳回值必須保持一緻：當該類的兩個的 hashcode() 傳回值相同時，它們通過 equals() 方法比較也應該傳回 true。通常來說，所有參與計算 hashcode() 傳回值的關鍵屬性，都應該用于作為 equals() 比較的标準。

我們在剛剛的實體中加入重寫的hashcode方法，再進行一個測試：

根據equals和hashcode的比較，隻要first屬性相同，就認為這兩個對象是同一個對象。那麼不難想象上面的程式隻包含一個對象了。

linkedhashset概述:

linkedhashset是具有可預知疊代順序的set接口的哈希表和連結清單實作。此實作與hashset的不同之處在于，後者維護着一個運作于所有條目的雙重連結清單。此連結清單定義了疊代順序，該疊代順序可為插入順序或是通路順序。

注意，此實作不是同步的。如果多個線程同時通路連結的哈希set，而其中至少一個線程修改了該set，則它必須保持外部同步。

linkedhashset的實作:

對于linkedhashset而言，它繼承與hashset、又基于linkedhashmap來實作的。

linkedhashset底層使用linkedhashmap來儲存所有元素，它繼承與hashset，其所有的方法操作上又與hashset相同，是以linkedhashset 的實作上非常簡單，隻提供了四個構造方法，并通過傳遞一個辨別參數，調用父類的構造器，底層構造一個linkedhashmap來實作，在相關操作上與父類hashset的操作相同，直接調用父類hashset的方法即可。linkedhashset的源代碼如下：

在父類hashset中，專為linkedhashset提供的構造方法如下，該方法為包通路權限，并未對外公開。

由上述源代碼可見，linkedhashset通過繼承hashset，底層使用linkedhashmap，以很簡單明了的方式來實作了其自身的所有功能。

檢視treeset的源碼可以發現，它是利用treemap來實作的。

treeset是無序的（關于這個是不是有序無序，在總結裡面講的很清楚）。但是它可以自定義排序規則，使它按照某種順序排列。我們可以自定義比較器，也可以把比較器傳給treeset構造一個擁有自定義比較器的set。

在treeset裡面放入integer和string的時候，系統會預設幫我們排序。因為它們都已經實作了comparable接口，并且重寫了compareto方法。我們自己定義一個類放入treeset的時候，務必要重寫實作comparable并且重寫compareto方法。

這個是treeset中存放對象的map，這個navigablemap繼承于sortedmap，而sortedmap繼承于map。很明顯，這個map帶有排序功能。

這兩個構造函數說明了，預設是以treemap來實作的。是以，這裡就不講太多它的實作，我們會在treemap部分講解。

下面是treeset的使用：

第一種，我們可以讓我們的實體實作comparable接口。

還有一種，我們可以自定義一個構造器，通過構造方法傳入treeset

有空再進行整理

java中有序和無序的概念

    有序指的是存儲順序與添加順序相同，并且可以通過下标通路，list就是這樣。

    無序剛好相反，指的是存儲順序與添加順序無關，沒有下标，當然也不可能通過下标通路，set就是如此。

    這裡需要注意的是，有序、無序中的“序”與我們平常所說的順序無關。

而treeset是無序，但又是排好序的。即添加順序與存儲順序無關，但是其中的對象實作了排序。

set集合總體分析

    hashset的元素存放順序和添加進去時候的順序沒有任何關系；而linkedhashset 則保持元素的添加順序；treeset則是對我們的set中的元素進行排序存放。

    一般來說，當要從集合中以有序的方式抽取元素時，treeset 實作就會有用處。為了能順利進行，添加到 treeset 的元素必須是可排序的。 而同樣需要對添加到treeset中的類對象實作 comparable 接口的支援。對于comparable接口的實作。假定一棵樹知道如何保持 java.lang 包裝程式器類元素的有序狀态。一般說來，先把元素添加到 hashset，再把集合轉換為 treeset 來進行有序周遊會更快。這點和hashmap的使用非常的類似。

    其實set的實作原理是基于map上面的。set中很多實作類和map中的一些實作類的使用上非常的相似。map中的“鍵值對”，其中的 “鍵”是不能重複的。這個和set中的元素不能重複一緻，其實set利用的就是map中“鍵”不能重複的特性來實作的。 hashset的巧妙實作：就是建立一個“鍵值對”，“鍵”就是我們要存入的對象，“值”則是一個常量。這樣可以確定， 我們所需要的存儲的資訊之是“鍵”。而“鍵”在map中是不能重複的，這就保證了我們存入set中的所有的元素都不重複。而判斷是否添加元素成功，則是通 過判斷我們向map中存入的“鍵值對”是否已經存在，如果存在的話，那麼傳回值肯定是常量：present ，表示添加失敗。如果不存在，傳回值就為null 表示添加成功。

list集合總體分析

vector的方法都是同步的（synchronized），是線程安全的（thread-safe），而arraylist的方法不是，由于線程的同步必然要影響性能，是以，arraylist的性能要比vector好。

當vector或arraylist中的元素超過它的初始大小時，vector會将它的容量翻倍，而arraylist隻增加50%大小，這樣，arraylist就有利于節約記憶體空間。

而arraylist和linkedlist通過源碼發現有很大差别。一個是基于數組實作的，一個是基于連結清單實作。這樣，當arraylist在插入資料時，必須将所有後面的資料後移，這樣必然要花費較多時間。是以，當你的操作是在一列資料的後面添加資料而不是在前面或中間，并且需要随機地通路其中的元素時，使用arraylist會提供比較好的性能。而通路連結清單中的某個元素時,就必須從連結清單的一端開始沿着連接配接方向一個一個元素地去查找,直到找到所需的元素為止，是以,當你的操作是在一列資料的前面或中間添加或删除資料，并且按照順序通路其中的元素時，就應該使用linkedlist了。