雖然經常用java集合，在工作中經常開發單位信息管理系統影響不大，但在一些特殊開發場景還是要

詳細瞭解不同的特性的。

Java的集合主要有List , Set, Map

List , Set繼承至Collection接口，Map為獨立接口

List下有ArrayList，LinkedList，Vector

Set下有HashSet，LinkedHashSet，TreeSetMap下有HashMap，LinkedHashMap， TreeMap，Hashtable

總結:Connection接口:

1.List 有序,可重複

ArrayList:優點: 底層數據結構是數組，查詢快，增刪慢。缺點: 線程不安全，效率高

LinkedList:優點: 底層數據結構是鏈表，查詢慢，增刪快。缺點: 線程不安全，效率高

Vector:優點: 底層數據結構是數組，查詢快，增刪慢。缺點: 線程安全，效率低

2.Set 無序,唯一

（1）HashSet：底層數據結構是哈希表。(無序,唯一)如何來保證元素唯一性?1.依賴兩個方法：hashCode()和equals()

HashSet底層數據結構採用哈希表實現，元素無序且唯一，線程不安全，效率高，可以存儲null元素，元素的唯一性是靠所存儲元素類型是否重寫hashCode()和equals()方法來保證的，如果沒有重寫這兩個方法，則無法保證元素的唯一性。

具體實現唯一性的比較過程:

<code>1.存儲元素時首先會使用hash()算法函數生成一個int類型hashCode散列值，然後已經的所存儲的元素的hashCode值比較，如果hashCode不相等，肯定是不同的對象。2.hashCode值相同，再比較equals方法。3.equals相同，對象相同。（則無需儲存）/<code> 

（2）LinkedHashSet：底層數據結構是鏈表和哈希表。(FIFO插入有序,唯一)1.由鏈表保證元素有序2.由哈希表保證元素唯一

LinkedHashSet底層數據結構採用鏈表和哈希表共同實現，鏈表保證了元素的順序與存儲順序一致，哈希表保證了元素的唯一性。線程不安全，效率高。

（3）TreeSet：底層數據結構是紅黑樹。(唯一，有序)1. 如何保證元素排序的呢?自然排序比較器排序2.如何保證元素唯一性的呢?根據比較的返回值是否是0來決定

TreeSet底層數據結構採用紅黑樹來實現，元素唯一且已經排好序；唯一性同樣需要重寫hashCode和equals()方法，二叉樹結構保證了元素的有序性。根據構造方法不同，分為自然排序（無參構造）和比較器排序（有參構造），自然排序要求元素必須實現Compareable接口，並重寫裡面的compareTo()方法，元素通過比較返回的int值來判斷排序序列，返回0說明兩個對象相同，不需要存儲；比較器排需要在TreeSet初始化是時候傳入一個實現Comparator接口的比較器對象，或者採用匿名內部類的方式new一個Comparator對象，重寫裡面的compare()方法；

紅黑樹：

在學習紅黑樹之前，咱們需要先來理解下二叉查找樹（BST）。

二叉查找樹

要想了解二叉查找樹，我們首先看下二叉查找樹有哪些特性呢？

1， 左子樹上所有的節點的值均小於或等於他的根節點的值

2， 右子數上所有的節點的值均大於或等於他的根節點的值

3， 左右子樹也一定分別為二叉排序樹

我們來看下圖的這棵樹，他就是典型的二叉查找樹

紅黑樹

紅黑樹就是一種平衡的二叉查找樹，說他平衡的意思是他不會變成“瘸子”，左腿特別長或者右腿特別長。除了符合二叉查找樹的特性之外，還具體下列的特性：

1. 節點是紅色或者黑色

2. 根節點是黑色

3. 每個葉子的節點都是黑色的空節點（NULL）

4. 每個紅色節點的兩個子節點都是黑色的。

5. 從任意節點到其每個葉子的所有路徑都包含相同的黑色節點。

看下圖就是一個典型的紅黑樹：

TreeSet的兩種排序方式比較

1.基本數據類型默認按升序排序

2.自定義排序

（1）自然排序：重寫Comparable接口中的Compareto方法

（2）比較器排序：重寫Comparator接口中的Compare方法

<code>compare(T o1,T o2)      比較用來排序的兩個參數。/<code>

<code>o1：代表當前添加的數據o2：代表集合中已經存在的數據0： 表示 o1 == o2-1(逆序輸出)： o1 < o2 1(正序輸出): o1 > o2 /<code>

1：o1 - o2（升序排列）-1：o2 - o1 (降序排列)

例子1：

<code> 1 import java.util.Comparator; 2 import java.util.Set; 3 import java.util.TreeSet; 4  5 public class Test { 6     public static void main(String[] args) { 7  8         /** 9          * 自定義規則的TreeSet10          * 客戶端排序：自己寫一個比較器，轉給TreeSet11          *12          * 比較規則13          * 當TreeSet集合添加數據的時候就會觸發比較器的compare()方法14          */15         Comparator<integer> comp = new Comparator<integer>() {16             /**17              * o1 當前添加的數據18              * o2 集合中已經存在的數據19              * 0： 表示 o1 == o220              * -1 ： o1 < o221              * 1 : o1 > o222              */23             @Override24             public int compare(Integer o1, Integer o2) {25                 System.out.println(o1+"--"+o2);26                 return o2 -o1; //輸出53 33 10，降序排序27               //  return  0;  //只輸出一個元素：3328               //   return -1; //輸出53 10 33，倒序輸出29               //  return 1;  //輸出33 10 5530             }31         };32 33         Set<integer> s2 = new TreeSet<>(comp);34         s2.add(33);35         s2.add(10);36         s2.add(55);37 38         System.out.println(s2); //輸入53 33 10，降序排序39 40     }41 }/<integer>/<integer>/<integer>/<code>

例2：

<code> 1 import java.util.Comparator; 2 import java.util.Iterator; 3 import java.util.Set; 4 import java.util.TreeSet; 5  6 /** 7  * 使用TreeSet和Comparator（使用匿名類），寫Test.java 8  * 要求：對TreeSet中的元素 9  *     1，2，3，4，5，6，7，8，9，10進行排列，10  * 排序邏輯為奇數在前偶數在後，11  * 奇數按照升序排列，偶數按照降序排列12  * 輸出結果：1 3 5 7 9 10 8 6 4 213  */14 public class Test {15     public static void main(String[] args) {16         Set<integer> s = new TreeSet<>(new Comparator<integer>() {17             //重寫compare方法18             @Override19             public int compare(Integer o1, Integer o2) {20                 System.out.println("o1="+o1+" o2="+o2);21                 if(o2%2==0){22                     if (o1%2==0){23                             return o2 -o1;24                     }else{25                         return -1;26                     }27                 }else {28                     if (o1%2==0){29                         return 1;30                     }else{31                         return o1 -o2;32                     }33                 }34 35 36             }37         });38 39         s.add(2);40         s.add(6);41         s.add(4);42         s.add(1);43         s.add(3);44         s.add(5);45         s.add(8);46         s.add(10);47         s.add(9);48         s.add(7);49 50         Iterator iterator = s.iterator();51 52         while(iterator.hasNext()){53             System.out.print(iterator.next()+" ");54         }55 56     }57 }/<integer>/<integer>/<code>

輸出結果：

3.Map接口:

Map用於保存具有映射關係的數據，Map裡保存著兩組數據：key和value，它們都可以使任何引用類型的數據，但key不能重複。所以通過指定的key就可以取出對應的value。

Map接口有四個比較重要的實現類，分別是HashMap、LinkedHashMap、TreeMap和HashTable。

TreeMap是有序的，HashMap和HashTable是無序的。

Hashtable的方法是同步的，HashMap的方法不是同步的。這是兩者最主要的區別。

HashMap

Map 主要用於存儲鍵(key)值(value)對，根據鍵得到值，因此鍵不允許重複,但允許值重複。HashMap 是一個最常用的Map,它根據鍵的HashCode 值存儲數據,根據鍵可以直接獲取它的值，具有很快的訪問速度。HashMap最多隻允許一條記錄的鍵為Null;允許多條記錄的值為 Null;HashMap不支持線程的同步，即任一時刻可以有多個線程同時寫HashMap;可能會導致數據的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。HashMap基於哈希表結構實現的 ，當一個對象被當作鍵時，必須重寫hasCode和equals方法。

LinkedHashMap

LinkedHashMap繼承自HashMap，它主要是用鏈表實現來擴展HashMap類，HashMap中條目是沒有順序的，但是在LinkedHashMap中元素既可以按照它們插入圖的順序排序，也可以按它們最後一次被訪問的順序排序。

TreeMap

TreeMap基於紅黑樹數據結構的實現，鍵值可以使用Comparable或Comparator接口來排序。TreeMap繼承自AbstractMap，同時實現了接口NavigableMap，而接口NavigableMap則繼承自SortedMap。SortedMap是Map的子接口，使用它可以確保圖中的條目是排好序的。

在實際使用中，如果更新圖時不需要保持圖中元素的順序，就使用HashMap，如果需要保持圖中元素的插入順序或者訪問順序，就使用LinkedHashMap，如果需要使圖按照鍵值排序，就使用TreeMap。

Hashtable

Hashtable和前面介紹的HashMap很類似，它也是一個散列表，存儲的內容是鍵值對映射，不同之處在於，Hashtable是繼承自Dictionary的，Hashtable中的函數都是同步的，這意味著它也是線程安全的，另外，Hashtable中key和value都不可以為null。

適用場景分析:HashSet是基於Hash算法實現的，其性能通常都優於TreeSet。為快速查找而設計的Set，我們通常都應該使用HashSet，在我們需要排序的功能時，我們才使用TreeSet。

怎麼選擇：

遍歷map實例

<code> 1 import java.util.HashMap;   2 import java.util.Iterator;   3 import java.util.Map;   4    5 public class Test {      6      7     public static void main(String[] args) {      8         Map<string> map = new HashMap<string>();      9         map.put("first", "linlin");     10         map.put("second", "好好學java");     11         map.put("third", "sihai");    12         map.put("first", "sihai2");   13     14     15         // 第一種：通過Map.keySet遍歷key和value     16         System.out.println("===================通過Map.keySet遍歷key和value:===================");     17         for (String key : map.keySet()) {     18             System.out.println("key= " + key + "  and  value= " + map.get(key));     19         }     20              21         // 第二種：通過Map.entrySet使用iterator遍歷key和value     22         System.out.println("===================通過Map.entrySet使用iterator遍歷key和value:===================");     23         Iterator<map.entry>> it = map.entrySet().iterator();     24         while (it.hasNext()) {     25             Map.Entry<string> entry = it.next();     26             System.out.println("key= " + entry.getKey() + "  and  value= "    27                     + entry.getValue());     28         }     29     30         // 第三種：通過Map.entrySet遍歷key和value     31         System.out.println("===================通過Map.entrySet遍歷key和value:===================");     32         for (Map.Entry<string> entry : map.entrySet()) {     33             System.out.println("key= " + entry.getKey() + "  and  value= "    34                     + entry.getValue());     35         }     36     37         // 第四種：通過Map.values()遍歷所有的value，但是不能遍歷鍵key     38         System.out.println("===================通過Map.values()遍歷所有的value:===================");     39         for (String v : map.values()) {     40             System.out.println("value= " + v);     41         }     42     }     43     44 }    /<string>/<string>/<map.entry>/<string>/<string>/<code>

重點問題重點分析:

（一）說說List,Set,Map三者的區別？

• List(對付順序的好幫手)： List接口存儲一組不唯一（可以有多個元素引用相同的對象），有序的對象
• Set(注重獨一無二的性質): 不允許重複的集合。不會有多個元素引用相同的對象。
• Map(用Key來搜索的專家): 使用鍵值對存儲。Map會維護與Key有關聯的值。兩個Key可以引用相同的對象，但Key不能重複，典型的Key是String類型，但也可以是任何對象。

（二）Arraylist 與 LinkedList 區別?

• 1. 是否保證線程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；
• 2. 底層數據結構： Arraylist 底層使用的是 Object 數組；LinkedList 底層使用的是 雙向鏈表 數據結構（JDK1.6之前為循環鏈表，JDK1.7取消了循環。注意雙向鏈表和雙向循環鏈表的區別，下面有介紹到！）
• 3. 插入和刪除是否受元素位置的影響： ① 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）。
• 4. 是否支持快速隨機訪問： LinkedList 不支持高效的隨機元素訪問，而 ArrayList 支持。快速隨機訪問就是通過元素的序號快速獲取元素對象(對應於get(int index) 方法)。
• 5. 內存空間佔用： ArrayList的空 間浪費主要體現在在list列表的結尾會預留一定的容量空間，而LinkedList的空間花費則體現在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放直接後繼和直接前驅以及數據）。

1.ArrayList是實現了基於動態數組的數據結構，LinkedList基於鏈表的數據結構。　　

2.對於隨機訪問get和set，ArrayList覺得優於LinkedList，因為LinkedList要移動指針。　　

3.對於新增和刪除操作add和remove，LinedList比較佔優勢，因為ArrayList要移動數據。 儘量避免同時遍歷和刪除集合。因為這會改變集合的大小；

（三）ArrayList 與 Vector 區別呢?為什麼要用Arraylist取代Vector呢？

Vector類的所有方法都是同步的。可以由兩個線程安全地訪問一個Vector對象、但是一個線程訪問Vector的話代碼要在同步操作上耗費大量的時間。

Arraylist不是同步的，所以在不需要保證線程安全時建議使用Arraylist。

（四）說一說 ArrayList 的擴容機制吧

https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/ArrayList-Grow.md

（五）HashSet與TreeSet與LinkedHashSet對比

HashSet不能保證元素的排列順序，順序有可能發生變化，不是同步的，集合元素可以是null,但只能放入一個nullTreeSet是SortedSet接口的唯一實現類，TreeSet可以確保集合元素處於排序狀態。TreeSet支持兩種排序方式，自然排序 和定製排序，其中自然排序為默認的排序方式。向 TreeSet中加入的應該是同一個類的對象。TreeSet判斷兩個對象不相等的方式是兩個對象通過equals方法返回false，或者通過CompareTo方法比較沒有返回0自然排序自然排序使用要排序元素的CompareTo（Object obj）方法來比較元素之間大小關係，然後將元素按照升序排列。定製排序自然排序是根據集合元素的大小，以升序排列，如果要定製排序，應該使用Comparator接口，實現 int compare(To1,To2)方法LinkedHashSet集合同樣是根據元素的hashCode值來決定元素的存儲位置，但是它同時使用鏈表維護元素的次序。這樣使得元素看起 來像是以插入順 序保存的，也就是說，當遍歷該集合時候，LinkedHashSet將會以元素的添加順序訪問集合的元素。

（六）LinkedHashMap和HashMap，TreeMap對比

Hashtable與 HashMap類似,它繼承自Dictionary類，不同的是:它不允許記錄的鍵或者值為空;它支持線程的同步，即任一時刻只有一個線程能寫Hashtable,因此也導致了 Hashtable在寫入時會比較慢。Hashmap 是一個最常用的Map,它根據鍵的HashCode 值存儲數據,根據鍵可以直接獲取它的值，具有很快的訪問速度，遍歷時，取得數據的順序是完全隨機的。LinkedHashMap保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的.也可以在構造時用帶參數，按照應用次數排序。在遍歷的時候會比HashMap慢，不過有種情況例外，當HashMap容量很大，實際數據較少時，遍歷起來可能會比LinkedHashMap慢，因為LinkedHashMap的遍歷速度只和實際數據有關，和容量無關，而HashMap的遍歷速度和他的容量有關。TreeMap實現SortMap接口，能夠把它保存的記錄根據鍵排序,默認是按鍵值的升序排序，也可以指定排序的比較器，當用Iterator 遍歷TreeMap時，得到的記錄是排過序的。我們用的最多的是HashMap,HashMap裡面存入的鍵值對在取出的時候是隨機的,在Map 中插入、刪除和定位元素，HashMap 是最好的選擇。TreeMap取出來的是排序後的鍵值對。但如果您要按

（七）HashMap 和 Hashtable 的區別

1. 線程是否安全： HashMap 是非線程安全的，HashTable 是線程安全的；HashTable 內部的方法基本都經過synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧！）；
2. 效率： 因為線程安全的問題，HashMap 要比 HashTable 效率高一點。另外，HashTable 基本被淘汰，不要在代碼中使用它；
3. 對Null key 和Null value的支持： HashMap 中，null 可以作為鍵，這樣的鍵只有一個，可以有一個或多個鍵所對應的值為 null。。但是在 HashTable 中 put 進的鍵值只要有一個 null，直接拋出 NullPointerException。
4. 初始容量大小和每次擴充容量大小的不同 ： ①創建時如果不指定容量初始值，Hashtable 默認的初始大小為11，之後每次擴充，容量變為原來的2n+1。HashMap 默認的初始化大小為16。之後每次擴充，容量變為原來的2倍。②創建時如果給定了容量初始值，那麼 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充為2的冪次方大小（HashMap 中的tableSizeFor()方法保證，下面給出了源代碼）。也就是說 HashMap 總是使用2的冪作為哈希表的大小,後面會介紹到為什麼是2的冪次方。
5. 底層數據結構： JDK1.8 以後的 HashMap 在解決哈希衝突時有了較大的變化，當鏈表長度大於閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間。Hashtable 沒有這樣的機制。

（八）HashMap 和 HashSet區別

如果你看過 HashSet 源碼的話就應該知道：HashSet 底層就是基於 HashMap 實現的。（HashSet 的源碼非常非常少，因為除了 clone() 、writeObject()、readObject()是 HashSet 自己不得不實現之外，其他方法都是直接調用 HashMap 中的方法。

（九）HashSet如何檢查重複

當你把對象加入HashSet時，HashSet會先計算對象的hashcode值來判斷對象加入的位置，同時也會與其他加入的對象的hashcode值作比較，如果沒有相符的hashcode，HashSet會假設對象沒有重複出現。但是如果發現有相同hashcode值的對象，這時會調用equals（）方法來檢查hashcode相等的對象是否真的相同。如果兩者相同，HashSet就不會讓加入操作成功。（摘自我的Java啟蒙書《Head fist java》第二版）

hashCode（）與equals（）的相關規定：

1. 如果兩個對象相等，則hashcode一定也是相同的
2. 兩個對象相等,對兩個equals方法返回true
3. 兩個對象有相同的hashcode值，它們也不一定是相等的
4. 綜上，equals方法被覆蓋過，則hashCode方法也必須被覆蓋
5. hashCode()的默認行為是對堆上的對象產生獨特值。如果沒有重寫hashCode()，則該class的兩個對象無論如何都不會相等（即使這兩個對象指向相同的數據）。

（十）HashMap的底層實現

JDK1.8之前

JDK1.8 之前 HashMap 底層是 數組和鏈表 結合在一起使用也就是 鏈表散列。HashMap 通過 key 的 hashCode 經過擾動函數處理過後得到 hash 值，然後通過 (n - 1) & hash 判斷當前元素存放的位置（這裡的 n 指的是數組的長度），如果當前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話，直接覆蓋，不相同就通過拉鍊法解決衝突。

所謂擾動函數指的就是 HashMap 的 hash 方法。使用 hash 方法也就是擾動函數是為了防止一些實現比較差的 hashCode() 方法 換句話說使用擾動函數之後可以減少碰撞。

HashMap實現原理（比較好的描述）：HashMap以鍵值對（key-value）的形式來儲存元素，但調用put方法時，HashMap會通過hash函數來計算key的hash值，然後通過hash值&(HashMap.length-1)判斷當前元素的存儲位置，如果當前位置存在元素的話，就要判斷當前元素與要存入的key是否相同，如果相同則覆蓋，如果不同則通過拉鍊表來解決。JDk1.8時，當鏈表長度大於8時，將鏈表轉為紅黑樹。

JDK 1.8 HashMap 的 hash 方法源碼:

JDK 1.8 的 hash方法 相比於 JDK 1.7 hash 方法更加簡化，但是原理不變。

<code>1     static final int hash(Object key) {2       int h;3       // key.hashCode()：返回散列值也就是hashcode4       // ^ ：按位異或5       // >>>:無符號右移，忽略符號位，空位都以0補齊6       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);7   }/<code>

對比一下 JDK1.7的 HashMap 的 hash 方法源碼.

<code>1 static int hash(int h) {2     // This function ensures that hashCodes that differ only by3     // constant multiples at each bit position have a bounded4     // number of collisions (approximately 8 at default load factor).5 6     h ^= (h >>> 20) ^ (h >>> 12);7     return h ^ (h >>> 7) ^ (h >>> 4);8 }/<code>

相比於 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能會稍差一點點，因為畢竟擾動了 4 次。

所謂 “拉鍊法” 就是：將鏈表和數組相結合。也就是說創建一個鏈表數組，數組中每一格就是一個鏈表。若遇到哈希衝突，則將衝突的值加到鏈表中即可。

JDK1.8之後

相比於之前的版本， JDK1.8之後在解決哈希衝突時有了較大的變化，當鏈表長度大於閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間。

TreeMap、TreeSet以及JDK1.8之後的HashMap底層都用到了紅黑樹。紅黑樹就是為了解決二叉查找樹的缺陷，因為二叉查找樹在某些情況下會退化成一個線性結構。

（十一）HashMap 的長度為什麼是2的冪次方

為了能讓 HashMap 存取高效，儘量較少碰撞，也就是要儘量把數據分配均勻。我們上面也講到了過了，Hash 值的範圍值-2147483648到2147483647，前後加起來大概40億的映射空間，只要哈希函數映射得比較均勻鬆散，一般應用是很難出現碰撞的。但問題是一個40億長度的數組，內存是放不下的。所以這個散列值是不能直接拿來用的。用之前還要先做對數組的長度取模運算，得到的餘數才能用來要存放的位置也就是對應的數組下標。這個數組下標的計算方法是“ (n - 1) & hash”。（n代表數組長度）。這也就解釋了 HashMap 的長度為什麼是2的冪次方。

這個算法應該如何設計呢？

我們首先可能會想到採用%取餘的操作來實現。但是，重點來了：“取餘(%)操作中如果除數是2的冪次則等價於與其除數減一的與(&)操作（也就是說 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 並且 採用二進制位操作 &，相對於%能夠提高運算效率，這就解釋了 HashMap 的長度為什麼是2的冪次方。

（十二）HashMap 多線程操作導致死循環問題

主要原因在於 併發下的Rehash 會造成元素之間會形成一個循環鏈表。不過，jdk 1.8 後解決了這個問題，但是還是不建議在多線程下使用 HashMap,因為多線程下使用 HashMap 還是會存在其他問題比如數據丟失。併發環境下推薦使用 ConcurrentHashMap 。

Rehash：一般來說，Hash表這個容器當有數據要插入時，都會檢查容量有沒有超過設定的thredhold，如果超過，需要增大Hash表的尺寸，但是這樣一來，整個Hash表裡的無素都需要被重算一遍。這叫rehash，這個成本相當的大。

（十三）ConcurrentHashMap 和 Hashtable 的區別

ConcurrentHashMap 和 Hashtable 的區別主要體現在實現線程安全的方式上不同。

• 底層數據結構： JDK1.7的 ConcurrentHashMap 底層採用 分段的數組+鏈表 實現，JDK1.8 採用的數據結構跟HashMap1.8的結構一樣，數組+鏈表/紅黑二叉樹。Hashtable 和 JDK1.8 之前的 HashMap 的底層數據結構類似都是採用 數組+鏈表 的形式，數組是 HashMap 的主體，鏈表則是主要為了解決哈希衝突而存在的；
• 實現線程安全的方式（重要）： ① 在JDK1.7的時候，ConcurrentHashMap（分段鎖） 對整個桶數組進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分數據，多線程訪問容器裡不同數據段的數據，就不會存在鎖競爭，提高併發訪問率。 到了 JDK1.8 的時候已經摒棄了Segment的概念，而是直接用 Node 數組+鏈表+紅黑樹的數據結構來實現，併發控制使用 synchronized 和 CAS 來操作。（JDK1.6以後 對 synchronized鎖做了很多優化） 整個看起來就像是優化過且線程安全的 HashMap，雖然在JDK1.8中還能看到 Segment 的數據結構，但是已經簡化了屬性，只是為了兼容舊版本；② Hashtable(同一把鎖) :使用 synchronized 來保證線程安全，get/put所有相關操作都是synchronized的，這相當於給整個哈希表加了一把大鎖,效率非常低下。當一個線程訪問同步方法時，其他線程也訪問同步方法，可能會進入阻塞或輪詢狀態，如使用 put 添加元素，另一個線程不能使用 put 添加元素，也不能使用 get，競爭會越來越激烈效率越低。

兩者的對比圖：

HashTable:

JDK1.7的ConcurrentHashMap：

（十四）ConcurrentHashMap線程安全的具體實現方式/底層具體實現

JDK1.7（上面有示意圖）

首先將數據分為一段一段的存儲，然後給每一段數據配一把鎖，當一個線程佔用鎖訪問其中一個段數據時，其他段的數據也能被其他線程訪問。

ConcurrentHashMap 是由 Segment 數組結構和 HashEntry 數組結構組成。

Segment 實現了 ReentrantLock,所以 Segment 是一種可重入鎖，扮演鎖的角色。HashEntry 用於存儲鍵值對數據。

<code>static class Segment extends ReentrantLock implements Serializable {}/<code>

一個 ConcurrentHashMap 裡包含一個 Segment 數組。Segment 的結構和HashMap類似，是一種數組和鏈表結構，一個 Segment 包含一個 HashEntry 數組，每個 HashEntry 是一個鏈表結構的元素，每個 Segment 守護著一個HashEntry數組裡的元素，當對 HashEntry 數組的數據進行修改時，必須首先獲得對應的 Segment的鎖。

JDK1.8 （上面有示意圖）

ConcurrentHashMap取消了Segment分段鎖，採用CAS和synchronized來保證併發安全。數據結構跟HashMap1.8的結構類似，數組+鏈表/紅黑二叉樹。Java 8在鏈表長度超過一定閾值（8）時將鏈表（尋址時間複雜度為O(N)）轉換為紅黑樹（尋址時間複雜度為O(log(N))）

synchronized只鎖定當前鏈表或紅黑二叉樹的首節點，這樣只要hash不衝突，就不會產生併發，效率又提升N倍。

（十五）comparable 和 Comparator的區別

• comparable接口實際上是出自java.lang包 它有一個 compareTo(Object obj)方法用來排序
• comparator接口實際上是出自 java.util 包它有一個compare(Object obj1, Object obj2)方法用來排序

一般我們需要對一個集合使用自定義排序時，我們就要重寫compareTo()方法或compare()方法，當我們需要對某一個集合實現兩種排序方式，比如一個song對象中的歌名和歌手名分別採用一種排序方法的話，我們可以重寫compareTo()方法和使用自制的Comparator方法或者以兩個Comparator來實現歌名排序和歌星名排序，第二種代表我們只能使用兩個參數版的 Collections.sort().

閱讀更多 SoftCloud 的文章

關鍵字: 算法 數據結構 信息管理系統