Java 的集合體系

 Java集合可分為兩大體系：Collection 和 Map

1.常見的Java集合如下：

Collection介面：單列資料，定義了存取一組物件的方法的集合

• List：元素有序(指的是存取時，與存放順序保持一致)、可重復的集合
• Set：元素無序、不可重復的集合

Map介面：雙列資料，保存具有映射關系“key-value對”的集合，根據元素的key訪問value

2.集合中執行緒安全的集合和執行緒不安全的集合

執行緒安全的：

• Hashtable：比HashMap多了個執行緒安全，
• ConcurrentHashMap:是一種高效但是執行緒安全的集合，
• Vector：比Arraylist多了個同步化機制，
• Stack：堆疊，也是執行緒安全的，繼承于Vector，

線性不安全的：

• HashMap - 陣列 + 鏈表 + 紅黑樹
• Arraylist - 陣列
• LinkedList - 雙向回圈鏈表
• HashSet - HashjMap
• TreeSet - 二叉樹
• TreeMap - 紅黑樹

3. Arraylist與 LinkedList 異同點？

• 是否保證執行緒安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證執行緒安全；
• 底層資料結構： Arraylist 底層使用的是Object陣列；LinkedList 底層使用的是雙向回圈鏈表資料結構；
• 插入和洗掉是否受元素位置的影響： ArrayList 采用陣列存盤，所以插入和洗掉元素的時間復雜度受元素位置的影響， 比如：執行add(E e)方法的時候， ArrayList 會默認在將指定的元素追加到此串列的末尾，這種情況時間復雜度就是O(1)，但是如果要在指定位置 i 插入和洗掉元素的話（add(int index, E element)）時間復雜度就為 O(n-i)，因為在進行上述操作的時候集合中第 i 和第 i 個元素之后的(n-i)個元素都要執行向后位/向前移一位的操作， LinkedList 采用鏈表存盤，所以插入，洗掉元素時間復雜度不受元素位置的影響，都是近似 O（1）而陣列為近似 O（n），
• 是否支持快速隨機訪問： LinkedList 不支持高效的隨機元素訪問，而ArrayList 實作了RandmoAccess 介面，所以有隨機訪問功能，快速隨機訪問就是通過元素的序號快速獲取元素物件(對應于get(int index)方法)，
• 記憶體空間占用： ArrayList的空 間浪費主要體現在在list串列的結尾會預留一定的容量空間，而LinkedList的空間花費則體現在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放直接后繼和直接前驅以及資料），

4. ArrayList 與 Vector 區別？

• Vector是執行緒安全的，ArrayList不是執行緒安全的，其中，Vector在關鍵性的方法前面都加了synchronized關鍵字，來保證執行緒的安全性，如果有多個執行緒會訪問到集合，那最好是使用 Vector，因為不需要我們自己再去考慮和撰寫執行緒安全的代碼，
• ArrayList在底層陣列不夠用時在原來的基礎上擴展0.5倍，Vector是擴展1倍，這樣ArrayList就有利于節約記憶體空間，

5. Collection子介面：Set 介面

• Set介面描述

• Set介面是Collection的子介面，set介面沒有提供額外的方法，
• Set 集合存取元素同樣是無序的，
• Set 集合不允許包含相同的元素，如果試把兩個相同的元素加入同一個Set 集合中，則添加操作失敗，
• Set 判斷兩個物件是否相同不是使用 == 運算子，而是根據 equals() 方法，
• Set 實作類之一：HashSet
  • HashSet 是 Set 介面的典型實作，大多數時候使用 Set 集合時都使用這個實作類，HashSet的底層其實就是HashMap，只不過我們HashSet是實作了Set介面并且把資料作為K值，而V值一直使用一個相同的虛值來保存，
  • HashSet 按 Hash 演算法來存盤集合中的元素，因此具有很好的存取、查找、洗掉性能，
  • HashSet 具有以下特點：不能保證元素的排列順序、HashSet 不是執行緒安全的、集合元素可以是 null
  • HashSet 集合判斷兩個元素相等的標準：兩個物件通過 hashCode() 方法比較相等，并且兩個物件的 equals() 方法回傳值也相等，
  • 對于存放在Set容器中的物件，對應的類一定要重寫equals()和hashCode(Object obj)方法，以實作物件相等規則，即：“相等的物件必須具有相等的散列碼”，

• Set實作類之二：LinkedHashSet
• LinkedHashSet 是 HashSet 的子類
• LinkedHashSet 根據元素的 hashCode 值來決定元素的存盤位置，但它同時使用雙向鏈表維護元素的次序，這使得元素看起來是以插入順序保存的，
• LinkedHashSet插入性能略低于 HashSet，但在迭代訪問 Set 里的全部元素時有很好的性能，
• LinkedHashSet 不允許集合元素重復，
• Set實作類之三：TreeSet

• TreeSet 是 SortedSet 介面的實作類，TreeSet 可以確保集合元素處于排序狀態，

• TreeSet底層使用紅黑樹結構存盤資料
• TreeSet 兩種排序方法：自然排序和定制排序，默認情況下，TreeSet 采用自然排序，

6. Map介面

• Map介面概述
  • Map與Collection并列存在，用于保存具有映射關系的資料:key-value
  • Map 中的 key 和 value 都可以是任何參考型別的資料
  • Map 中的 key 用Set方法來存放，不允許重復，即同一個 Map 物件所對應的類，須重寫 hashCode()和equals() 方法
  • 常用String類作為Map的“鍵”
  • key值唯一，但可以為null
  • key 和 value 之間存在單向一對一關系，即通過指定的 key 總能找到唯一的、確定的 value
  • Map介面的常用實作類：HashMap、TreeMap、LinkedHashMap和Properties，其中，HashMap是 Map 介面使用頻率最高的實作類

 7. Map實作類之一：HashMap

• HashMap是 Map 介面使用頻率最高的實作類，
• 允許使用null鍵和null值，與HashSet一樣，不保證映射的順序，
• 所有的key構成的集合是Set:無序的、不可重復的，所以，key所在的類要重寫：equals()和hashCode()
• 所有的value構成的集合是Collection:無序的、可以重復的，所以，value所在的類要重寫：equals()
• 一個key-value構成一個entry
• 所有的entry構成的集合是無序的、不可重復的
• HashMap 判斷兩個 key 相等的標準是：兩個 key 通過 equals() 方法回傳 true，hashCode 值也相等，
• HashMap 判斷兩個 value相等的標準是：兩個 value 通過 equals() 方法回傳 true，
• 擴容負載因子是0.75，擴容倍數：2

8. HashMap 的 底層資料結構是什么？

在JDK1.7 和JDK1.8 中有所差別：

在JDK1.7 中，由“陣列+鏈表”組成，陣列是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的，

在JDK1.8 中，由“陣列+鏈表+紅黑樹”組成，當鏈表過長，則會嚴重影響 HashMap 的性能，紅黑樹搜索時間復雜度是 O(logn)，而鏈表是糟糕的 O(n)，因此，JDK1.8 對資料結構做了進一步的優化，引入了紅黑樹，鏈表和紅黑樹在達到一定條件會進行轉換：

• 當鏈表超過 8 且資料總量超過 64 才會轉紅黑樹，

• 將鏈表轉換成紅黑樹前會判斷，如果當前陣列的長度小于 64，那么會選擇先進行陣列擴容，而不是轉換為紅黑樹，以減少搜索時間，

9. 解決hash沖突的辦法有哪些？HashMap用的哪種？

解決Hash沖突方法有:開放定址法、再哈希法、鏈地址法（拉鏈法）、建立公共溢位區，HashMap中采用的是 鏈地址法 ，

• 開放定址法也稱為再散列法，基本思想就是，如果p=H(key)出現沖突時，則以p為基礎，再次hash，p1=H(p),如果p1再次出現沖突，則以p1為基礎，以此類推，直到找到一個不沖突的哈希地址pi， 因此開放定址法所需要的hash表的長度要大于等于所需要存放的元素，而且因為存在再次hash，所以只能在洗掉的節點上做標記，而不能真正洗掉節點，
• 再哈希法(雙重散列，多重散列)，提供多個不同的hash函式，當R1=H1(key1)發生沖突時，再計算R2=H2(key1)，直到沒有沖突為止， 這樣做雖然不易產生堆集，但增加了計算的時間，
• 鏈地址法(拉鏈法)，將哈希值相同的元素構成一個同義詞的單鏈表,并將單鏈表的頭指標存放在哈希表的第i個單元中，查找、插入和洗掉主要在同義詞鏈表中進行，鏈表法適用于經常進行插入和洗掉的情況，
• 建立公共溢位區，將哈希表分為公共表和溢位表，當溢位發生時，將所有溢位資料統一放到溢位區，

Collections工具類

• Collections 是一個操作 Set、List 和 Map 等集合的工具類

• Collections 中提供了一系列靜態的方法對集合元素進行排序、查詢和修改等操作，
  還提供了對集合物件設定不可變、對集合物件實作同步控制等方法
• 排序操作：（均為static方法）
  • reverse(List)：反轉 List 中元素的順序
  • shuffle(List)：對 List 集合元素進行隨機排序
  • sort(List)：根據元素的自然順序對指定 List 集合元素按升序排序
  • sort(List，Comparator)：根據指定的 Comparator 產生的順序對 List 集合元素進行排序
  • swap(List，int， int)：將指定 list 集合中的 i 處元素和 j 處元素進行交換

• Collections常用方法（查找、替換）

  • Object max(Collection)：根據元素的自然順序，回傳給定集合中的最大元素
  • Object max(Collection，Comparator)：根據 Comparator 指定的順序，回傳給定集合中的最大元素
  • Object min(Collection)
  • Object min(Collection，Comparator)
  • int frequency(Collection，Object)：回傳指定集合中指定元素的出現次數
  • void copy(List dest,List src)：將src中的內容復制到dest中 ?boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替換List 物件的所有舊值

標籤：其他

上一篇：idea永久激活教程(新版)

下一篇：編譯型與解釋型編程語言的區別