Java 容器可以分為兩類,一類是 collection 表示的是集合,一類是 map,表示的是鍵值對結構。 Collection 它又可以分為三大類:List,Set,Queue。
Java 的 List 是非常常用的資料型別。
List 是有序的 Collection。
Java List 一共三個實現類: 分別是 ArrayList、Vector 和 LinkedList。
ArrayList 是最常用的 List 實現類,內部是通過陣列實現的,它允許對元素進行快速隨機存取。陣列的缺點是每個元素之間不能有間隔,當陣列大小不滿足時需要增加儲存能力,就要將已經有陣列的資料複製到新的儲存空間中。當從 ArrayList 的中間位置插入或者刪除元素時,需要對陣列進行復制、移動、代價比較高。因此,它適合隨機查詢和遍歷,不適合插入和刪除。
Vector 與 ArrayList 一樣,也是通過陣列實現的,不同的是它支援執行緒的同步,即某一時刻只有一個執行緒能夠寫 Vector,避免多執行緒同時寫而引起的不一致性,但實現同步需要很高的花費,因此, 存取它比存取 ArrayList 慢。
LinkedList 是用連結串列結構儲存資料的,很適合資料的動態插入和刪除,隨機存取和遍歷速度比較慢。另外,他還提供了 List 介面中沒有定義的方法,專門用於操作表頭和表尾元素,可以當作堆疊、佇列和雙向佇列使用。
Set 注重獨一無二的性質,該體系集合用於儲存無序 (存入和取出的順序不一定相同)元素,值不能重複。物件的相等性本質是物件 hashCode 值(java 是依據物件的記憶體地址計算出的此序號)判斷的,如果想要讓兩個不同的物件視為相等的,就必須覆蓋 Object 的 hashCode 方法和 equals 方法。
雜湊表邊存放的是雜湊值。HashSet 儲存元素的順序並不是按照存入時的順序(和 List 顯然不同) 而是按照雜湊值來存的所以取資料也是按照雜湊值取得。元素的雜湊值是通過元素的 hashcode 方法來獲取的,HashSet 首先判斷兩個元素的雜湊值,如果雜湊值一樣,接著會比較 equals 方法,如果結果為 true ,HashSet 就視為同一個元素。如果 equals 為 false 就不是同一個元素。
雜湊值相同 equals 為 false 的元素是怎麼儲存呢,就是在同樣的雜湊值下順延(可以認為雜湊值相同的元素放在一個雜湊桶中)。也就是雜湊一樣的存一列。
HashSet 通過 hashCode 值來確定元素在記憶體中的位置。一個 hashCode 位置上可以存放多個元素。
對於 LinkedHashSet 而言,它繼承於 HashSet、又基於 LinkedHashMap 來實現的。 LinkedHashSet 底層使用 LinkedHashMap 來儲存所有元素,它繼承與 HashSet,其所有的方法操作上又與 HashSet 相同,因此 LinkedHashSet 的實現上非常簡單,只提供了四個構造方法,並通過傳遞一個標識引數,呼叫父類別的構造器,底層構造一個 LinkedHashMap 來實現,在相關操作上與父類別 HashSet 的操作相同,直接呼叫父類別 HashSet 的方法即可。
HashSet 底層是 HashMap
SortedSet 底層是 TreeMap (SortedMap 介面)
HashMap 根據鍵的 hashCode 值儲存資料,大多數情況下可以直接定位到它的值,因而具有很快的存取速度,但遍歷順序卻是不確定的。 HashMap 最多隻允許一條記錄的鍵為 null,允許多條記錄的值為 null。
HashMap 非執行緒安全,即任一時刻可以有多個執行緒同時寫 HashMap,可能會導致資料的不一致。如果需要滿足執行緒安全,可以用 Collections 的 synchronizedMap 方法使 HashMap 具有執行緒安全的能力,或者使用 ConcurrentHashMap。
JAVA7 實現
大方向上,HashMap 裡面是一個陣列,然後陣列中每個元素是一個單向連結串列。上圖中,每個綠色的實體是巢狀類 Entry 的範例,Entry 包含四個屬性:key, value, hash 值和用於單向連結串列的 next。
JAVA8 實現
Java8 對 HashMap 進行了一些修改,最大的不同就是利用了紅黑樹,所以其由陣列+連結串列+紅黑樹組成。
根據 Java7 HashMap 的介紹,我們知道,查詢的時候,根據 hash 值我們能夠快速定位到陣列的具體下標,但是之後的話,需要順著連結串列一個個比較下去才能找到我們需要的,時間複雜度取決於連結串列的長度,為 O(n)。為了降低這部分的開銷,在 Java8 中,當連結串列中的元素超過了 8 個以後, 會將連結串列轉換為紅黑樹,在這些位置進行查詢的時候可以降低時間複雜度為 O(logN)。
ConcurrentHashMap 和 HashMap 思路是差不多的,但是因為它支援並行操作,所以要複雜一些。整個 ConcurrentHashMap 由一個個 Segment 組成,Segment 代表 」部分「 或 」一段「 的意思,所以很多地方都會將其描述為分段鎖。注意,行文中,我很多地方用了 「槽」 來代表一個 segment。
簡單理解就是,ConcurrentHashMap 是一個 Segment 陣列,Segment 通過繼承 ReentrantLock 來進行加鎖,所以每次需要加鎖的操作鎖住的是一個 Segment,這樣只要保證每個 Segment 是執行緒安全的,也就實現了全域性的執行緒安全。
concurrencyLevel:並行級別、並行數、Segment 數,怎麼翻譯不重要,理解它。預設是 16, 也就是說 ConcurrentHashMap 有 16 個 Segments,所以理論上,這個時候,最多可以同時支援 16 個執行緒並行寫,只要它們的操作分別分佈在不同的 Segment 上。這個值可以在初始化的時候設定為其他值,但是一旦初始化以後,它是不可以擴容的。再具體到每個 Segment 內部,其實每個 Segment 很像之前介紹的 HashMap,不過它要保證執行緒安全,所以處理起來要麻煩些。
ConcurrentHashMap 在 1,7 的實現是分段鎖,這個 segment 繼承 ReentrantLock,每次 put 的時候首先通過 key 定位到 segment,之後在對應的 segment 中進行具體的 put 操作。ConcurrentHashMap 已經支援了 N 個分段鎖的並行,N (並行度) 預設是 16,也就是一個桶一把鎖, 但是由於 HashMap 中 1.7 的問題,所以在 1.8 中,拋棄了原來的分段鎖,而是採用了 CAS+Synchronized 來保證並行安全,在 put 方法中,首先也是根據 key 得到 hash 值, 然後得到陣列的下標,當前位置為空表示可以插入,然後利用 CAS(自旋鎖) 嘗試寫入,失敗就自旋保證成功,如果都不滿足,就利用 Synchronized 鎖住後寫入資料。
HashTable 它的底層就是一個方法使用了一個 synchronized 進行修飾,並行度低。
Hashtable 是遺留類,很多對映的常用功能與 HashMap 類似,不同的是它承自 Dictionary 類, 並且是執行緒安全的,任一時間只有一個執行緒能寫 Hashtable,並行性不如 ConcurrentHashMap, 因為 ConcurrentHashMap 引入了分段鎖。Hashtable 不建議在新程式碼中使用,不需要執行緒安全的場合可以用 HashMap 替換,需要執行緒安全的場合可以用 ConcurrentHashMap 替換。
TreeMap 實現 SortedMap 介面,能夠把它儲存的記錄根據鍵排序,預設是按鍵值的升序排序,也可以指定排序的比較器,當用 Iterator 遍歷 TreeMap 時,得到的記錄是排過序的。 如果使用排序的對映,建議使用 TreeMap。
在使用 TreeMap 時,key 必須實現 Comparable 介面或者在構造 TreeMap 傳入自定義的 Comparator,否則會在執行時丟擲 java.lang.ClassCastException 型別的異常。
LinkedHashMap 是 HashMap 的一個子類,儲存了記錄的插入順序,在用 Iterator 遍歷 LinkedHashMap 時,先得到的記錄肯定是先插入的,也可以在構造時帶引數,按照存取次序排序。
Collections 是一個集合工具類,他裡面有一些 Synchronized 方法,主要是把一些普通的集合容器變成執行緒安全的,它的主要實現是在每一個方法執行的之後加了 Synchronized,並且 Synchronized 鎖的是 mutex(互斥量),它是一個全域性的 Object 物件。它的鎖的粒度相比較直接給一個方法加 Synchronized 加鎖要細一點,但是並沒有細化太多。
字面意思就是寫時複製,它是一種讀寫分離的思想,當我們需要往集合裡面新增元素的時候, 我們先把原來的集合複製出來,並且長度加一,然後我們把新增的元素放在複製出來的這個集合上面,然後改變原來的參照。 它適合讀操作多,但是寫操作少的這種場景。它的寫操作加鎖是通過 reentrantLock 來實現。