1、常見的集合有哪些

Java 集合， 也叫作容器，主要是由兩大接口派生而來：一個是 Collection 接口，主要用于存放單一元素，另一個是 Map 接口，主要用于存放鍵值對。對于 Collection 接口，下面又有三個主要的子接口：List、Set 和 Queue。Java 集合框架如下圖所示：

2、說說 List、Set、Queue、Map 四者的區別

• List：存儲的元素是有序的、可重復的。
• Set：存儲的元素是無序的、不可重復的。
• Queue：按特定的排隊規則來確定先后順序，存儲的元素是有序的、可重復的。
• Map：使用鍵值對存儲，保存鍵值對映射，映射關系可以一對一、多對一。

3、Collection 和 Collections 有什么區別

首先說下 collection，collection 它是一個接口，collection 接口的意義是為各種具體的集合提供統一的操作方式，它繼承 Iterable 接口，Iterable 接口中有一個最關鍵的方法， Iterator iterator()方法迭代器，可以迭代集合中的元素。
Collections 是操作集合的工具類，其中最出名的就是 Collections.sort(list) 方法進行排序，使用此方法排序集合元素類型必須實現Comparable接口重寫compareTo()方法，否則無法實現排序。

4、Comparable 和 Comparator 的區別

對集合排序最常見的就是 Collections.sort(arrayList) 方法，但是用這個方法排序，arrayList這個集合的元素類型必須實現 Comparable 接口并實現其中的 compareTo 方法并寫排序規則才能完成排序。

或者對集合排序也可使使用 sort 的一個重載方法 sort(List list, Comparator<? super T> c) 來實現排序，就是第一個參數為 arrayList 這個集合也不用再去實現 Comparable 接口了，而是在第二個參數寫 Comparator 的實現 compare 方法，例如

 Collections.sort(arrayList, new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
});

5、ArrayList 和 LinkedList 的區別是什么

• 底層數據結構： ArrayList 底層使用的是 Object 數組，LinkedList 底層使用的是 雙向鏈表 數據結構。

• 隨機訪問性能：ArrayList基于數組，所以它可以根據下標查找，支持隨機訪問，當然，它也實現了RandmoAccess 接口，這個接口只是用來標識是否支持隨機訪問。LinkedList基于鏈表，所以它沒法根據序號直接獲取元素，它沒有實現 RandmoAccess 接口，標記不支持隨機訪問。
• 插入和刪除是否受元素性能：LinkedList 的隨機訪問集合元素時性能較差，但在插入，刪除操作是更快的。因為 LinkedList 不像 ArrayList 一樣，不需要改變數組的大小，不需要在數組裝滿的時候要將所有的數據重新裝入一個新的數組，對于插入和刪除操作，LinkedList 優于 ArrayList。
• 內存空間占用：LinkedList 需要更多的內存，因為 ArrayList 的每個索引的位置是實際的數據，而 LinkedList 中的每個節點中存儲的是實際的數據和前后節點的位置。

6、ArrayList 和 Vector 的區別是什么

• Vector 的方法都是同步的，線程安全；ArrayList 非線程安全，但性能比 Vector 好。
• Vector 擴容默認擴容2倍，ArrayList 只增加1.5倍。

7、ArrayList 和 Vector 的擴容機制

ArrayList 是基于數組的集合，數組的容量是在定義的時候確定的，如果數組滿了，再插入，就會數組溢出。所以在插入時候，會先檢查是否需要擴容，如果當前容量+1超過數組長度，就會進行擴容

ArrayList 的擴容是創建一個1.5倍的新數組，然后把原數組的值拷貝過去。

底層代碼：

ArrayList無參構造

// Object類型的數組 elmentData []
transient Object[] elementData;
// {}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// ArrayList無參構造方法
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

底層用的是一個Object類型的數組elementData，當使用無參構造方法ArrayList后elementData是空的，也就是說使用無參構造方法后容量為0。

// 容量為10
private static final int DEFAULT_CAPACITY = 10;
// add添加元素方法
public boolean add(E e) {// 按照元素個數+1，確認數組容量是否夠用，所需最小容量方法ensureCapacityInternal(size + 1);// 將數組第size位置添加為該元素elementData[size++] = e;return true;
}// 所需最小容量方法
private void ensureCapacityInternal(int minCapacity) {// 空數組初始所需最小容量為10，非空數組所需最小容量是元素個數+1if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}// 是否需要擴容方法ensureExplicitCapacity(minCapacity);
}// 是否需要擴容方法
private void ensureExplicitCapacity(int minCapacity) {modCount++;// 所需最小容量當前數組能否存下，如果現在數組存不下進行擴容if (minCapacity - elementData.length > 0)grow(minCapacity);
}// 容器擴容方法
private void grow(int minCapacity) {// 舊容量（原數組的長度）int oldCapacity = elementData.length;// 新容量（舊容量加上舊容量右移一位，也就是1.5倍）int newCapacity = oldCapacity + (oldCapacity >> 1);// 如果計算出的新容量比最小所需容量小就用最小所需容量作為新容量if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果計算出的新容量比MAX_ARRAY_SIZE大, 就調用hugeCapacity計算新容量if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 數組擴容成新容量elementData = Arrays.copyOf(elementData, newCapacity);
}

由此看出只有當第一次add添加元素的時候，才初始化容量，因為是空數組所需的最小容量為10，而 elementData 大小為0，新容量算出類也是0，此時最小所需容量作為新容量為10。

例如：

ArrayList<Object> objects = new ArrayList<>();
長度:  1 容量： 10
長度:  5 容量： 10
長度:  11 容量： 15
長度:  15 容量： 15
長度:  21 容量： 22

ArrayList有參構造

//有參構造方法
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}
}

有參構造和無參構造區別就是給數組初始化了長度initialCapacity并且數組不為空，不為空的數組最小所需容量就是集合元素長度，集合元素長度超過初始化長度initialCapacity值才擴容，擴容邏輯和無參構造一致。

例如：

ArrayList<Object> objects = new ArrayList<>(5);
長度:  3 容量： 5
長度:  5 容量： 5
長度:  7 容量： 7
長度:  11 容量： 15
長度:  15 容量： 15
長度:  19 容量： 22
ArrayList<Object> objects = new ArrayList<>(13);
長度:  15 容量： 19
長度:  17 容量： 19
長度:  21 容量： 28
長度:  25 容量： 28
長度:  29 容量： 42

Vector 擴容機制

Vector 的底層也是一個數組 elmentData，但相對于 ArrayList 來說，它是線程安全的，它的每個操作方法都是加了鎖的。如果在開發中需要保證線程安全，則可以使用 Vector。擴容機制也與 ArrayList 大致相同。唯一需要注意的一點是，Vector 的擴容量是2倍。

結論

數據類型	底層數據結構	默認初始容量	加載因子	擴容增量
ArrayList	數組	10（jdk7）0（jdk8）	加載因子1（元素滿了擴容）	0.5：擴容后容量為原容量的1.5倍
Vector	數組	10	加載因子1（元素滿了擴容）	1：擴容后容量為原容量的2倍

LinkedList，鏈表結構，且是是雙向鏈表，不涉及擴容的問題。

8、CopyOnWriteArrayList 了解多少

CopyOnWriteArrayList 就是線程安全版本的 ArrayList。

它的名字叫 CopyOnWrite —— 寫時復制，已經明示了它的原理。

CopyOnWriteArrayList 采用了一種讀寫分離的并發策略。CopyOnWriteArrayList 容器允許并發讀，讀操作是無鎖的，性能較高。至于寫操作，比如向容器中添加一個元素，則首先將當前容器復制一份，然后在新副本上執行寫操作，結束之后再將原容器的引用指向新容器。

CopyOnWriteArrayList 添加新元素是否需要擴容

CopyOnWriteArrayList 底層并非是動態擴容數組，不能動態擴容，其線程安全是通過ReentrantLock來保證的。當向其添加元素時候，線程獲取鎖的使用權，add方法中會新建一個容量為舊容量加一的數組，然后將舊數據拷貝到該數組，然后把新數據放在數組尾部。

9、為什么 ArrayList 不是線程安全的

ArrayList 和 Vector 線程安全區別就是add方法沒有被synchronized修飾，這樣的ArrayList會出現兩種線程安全問題，第一種就是集合數據出現NULL的情況，線程A 是第一次add的時候，他知道他要去擴容，他自己擴容完復制成一個新的數組，然后給數組第一個下標賦值，此時size下標加1，如果線程A沒有擴容完時候，線程B進入add方法時候，不巧也是以為要擴容，復制成一個新的數組，再賦值的時候，如果線程A把size加1了，那么線程B賦值時候就只能從第二個下標開始了。 [null , B的UUID值] 。

還有一種出現java.util.ConcurrentModificationException 并發沖突情況，modCount是修改記錄數，expectedModCount是期望修改記錄數，初始化的時候 expectedModCount=modCount，ArrayList的add函數、remove函數 操作都有對modCount++操作，當expectedModCount和modCount值不相等， 那就會報并發錯誤了。

實現 ArrayList 線程安全的方法

1.最簡單的方式， 也是面經上經常看到的  使用 Vector ：
List<String> resultList = new Vector<>();

2.使用 Collections里面的synchronizedList ：
List<String> list1 = Collections.synchronizedList(list);

3.使用juc包下的 CopyOnWriteArrayList ：
CopyOnWriteArrayList list2 = new CopyOnWriteArrayList();

拓展：set 因為實現類都是線程不安全的，所以解決方法有

// 方式一：使用Collections集合類
// Set<String> set = Collections.synchronizedSet(set1);
// 方式二：使用CopyOnWriteArraySet

10、HashSet 的實現原理

HashSet底層其實是一個HashMap實例，數據存儲結構都是數組+鏈表。HashSet中的元素都存放在HashMap的key上面，而value都是一個統一的對象PRESENT。

private static final Object PRESENT = new Object();

HashSet中add方法調用的是底層HashMap的put方法。如果是在HashMap中調用put方法，首先會去判斷key是否已經存在，如果存在，則修改value的值，如果不存在，則插入這個k-v對。而在Set中，value是沒有用的，所以也就不存在修改value的情況，故而，向HashSet中添加新的元素，首先判斷元素是否存在，不存在則插入，存在則pass，這樣HashSet中就不存在重復值了。

11、TreeSet 的實現原理

TreeSet底層實際是用TreeMap實現的，Treeset 底層是由紅黑樹實現的，內部維持了一個簡化版的TreeMap，通過key來存儲Set的元素。 TreeSet對存儲的元素進行排序，如果未指定比較器，TreeSet 會使用元素的自然順序（即元素必須實現 Comparable 接口）。如果指定了比較器，TreeSet 會使用比較器來排序元素。

12、Queue 與 Deque 的區別

Queue 是單端隊列，只能從一端插入元素，另一端刪除元素，實現上一般遵循 先進先出（FIFO） 規則。

Queue 擴展了 Collection 的接口，根據 因為容量問題而導致操作失敗后處理方式的不同 可以分為兩類方法: 一種在操作失敗后會拋出異常，另一種則會返回特殊值。
|

Queue 接口	拋出異常	返回特殊值
插入隊尾	add(E e)	offer(E e)
刪除隊首	remove()	poll()
查詢隊首元素	element()	peek()

Deque 是雙端隊列，在隊列的兩端均可以插入或刪除元素。

Deque 擴展了 Queue 的接口, 增加了在隊首和隊尾進行插入和刪除的方法，同樣根據失敗后處理方式的不同分為兩類：

Deque 接口	拋出異常	返回特殊值
插入隊首	addFirst(E e)	offerFirst(E e)
插入隊尾	addLast(E e)	offerLast(E e)
刪除隊首	removeFirst()	pollFirst()
刪除隊尾	removeLast()	pollLast()
查詢隊首元素	getFirst()	peekFirst()
查詢隊尾元素	getLast()	peekLast()

事實上，Deque 還提供有 push() 和 pop() 等其他方法，可用于模擬棧。

/*** 測試隊列 特殊的線性表，隊列中限制了對線性表的訪問只能從線性表的一端添加元素，從另一端取出，遵循先進先出(FIFO)原則*/@Testpublic void test01() {Queue<String> que = new LinkedList<String>();// 添加隊尾que.offer("3");que.offer("1");que.offer("2");// 獲取隊首String str = que.peek();System.out.println(str);// 3// 移除隊首que.poll();System.out.println(que);// [1, 2]}/*** 棧是隊的子接口，棧是繼承隊的，定義類"雙端列"從隊列的兩端可以入隊(offer)和出隊(poll)* LinkedList實現了該接口，如果限制Deque雙端入隊和出隊，將雙端隊列改為單端隊列即為棧，棧遵循先進后出(FILO)的原則*/@Testpublic void test02() {Deque<String> stack = new LinkedList<String>();// 壓棧stack.push("aaa");stack.push("bbb");stack.push("ccc");System.out.println(stack);// [ccc, bbb, aaa]// 彈棧String lastStr = stack.pop();System.out.println(lastStr);// ccclastStr = stack.pop();System.out.println(lastStr);// bbblastStr = stack.pop();System.out.println(lastStr);// aaa}

13、ArrayDeque 與 LinkedList 的區別

ArrayDeque 和 LinkedList 都實現了 Deque 接口，兩者都具有隊列的功能，但兩者有什么區別呢？

• ArrayDeque 是基于可變長的數組和雙指針來實現，而 LinkedList 則通過鏈表來實現。
• ArrayDeque 不支持存儲 NULL 數據，但 LinkedList 支持。
• ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 時就已經存在。
• ArrayDeque 插入時可能存在擴容過程, 不過均攤后的插入操作依然為 O(1)。雖然 LinkedList 不需要擴容，但是每次插入數據時均需要申請新的堆空間，均攤性能相比更慢。

從性能的角度上，選用 ArrayDeque 來實現隊列要比 LinkedList 更好。此外，ArrayDeque 也可以用于實現棧。

14、HashMap 的數據結構

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

相比于之前的版本， JDK1.8 之后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為 8）將鏈表轉化為紅黑樹，以減少搜索時間。但將鏈表轉換成紅黑樹前會判斷，如果當前數組的長度小于 64，那么會選擇先進行數組擴容，而不是轉換為紅黑樹。

其中，桶數組是用來存儲數據元素，鏈表是用來解決沖突，紅黑樹是為了提高查詢的效率。

• 數據元素通過映射關系，也就是散列函數，映射到桶數組對應索引的位置。
• 如果發生沖突，從沖突的位置拉一個鏈表，插入沖突的元素。
• 如果鏈表長度 > 8 并且數組大小 >= 64，鏈表轉為紅黑樹。
• 如果紅黑樹節點個數 < 6 ，轉為鏈表。

15、HashMap 的put流程

• 對 Key 求 Hash 值，然后再計算下標
• 如果沒有碰撞，直接放入桶中（碰撞的意思是計算得到的 Hash 值相同，需要放到同一個 bucket 中）
• 如果碰撞了，以鏈表的方式鏈接到后面
• 如果鏈表長度超過閥值( TREEIFY THRESHOLD==8)，就把鏈表轉成紅黑樹，鏈表長度低于 6，就把紅黑樹轉回鏈表
• 如果節點已經存在就替換舊值
• 如果桶滿了(容量 16*加載因子 0.75)，就需要 resize（擴容 2 倍后重排）
  • initialCapacity：初始容量。指的是 HashMap 集合初始化的時候自身的容量。可以在構造方法中指定；如果不指定的話，總容量默認值是 16 。需要注意的是初始容量必須是 2 的冪次方。
  • size：當前 HashMap 中已經存儲著的鍵值對數量，即 HashMap.size()
  • loadFactor：加載因子。所謂的加載因子就是 HashMap (當前的容量/總容量) 到達一定值的時候，HashMap 會實施擴容。加載因子也可以通過構造方法中指定，默認的值是 0.75 。
  • threshold：擴容閥值。即 擴容閥值 = HashMap 總容量 * 加載因子。當前 HashMap 的容量
    大于或等于擴容閥值的時候就會去執行擴容。擴容的容量為當前 HashMap 總容量的兩倍。

舉個例子，假設有一個 HashMap 的初始容量為 16 ，那么擴容的閥值就是 0.75 * 16 = 12 。也就是說，在你打算存入第 13 個值的時候，HashMap 會先執行擴容，那么擴容之后為 32 。

16、HashMap 怎么查找元素的呢

首先，調用鍵的 hashCode() 方法，計算鍵的哈希值，然后，通過 HashMap 的哈希函數將哈希值映射到桶數組的索引。根據索引找到對應的桶（鏈表或紅黑樹的頭節點）。遍歷鏈表或紅黑樹，比較每個節點的鍵與目標鍵：

• 如果鍵相等（通過 equals() 方法判斷），則返回對應的值。
• 如果遍歷完鏈表或紅黑樹仍未找到，則返回 null。

17、為什么 HashMap 的容量是2的倍數呢

1. 優化索引計算：通過位運算 (n - 1) & hash 替代取模運算，提高性能。
2. 均勻分布哈希值：充分利用哈希值的所有位，減少哈希沖突。
3. 擴容優化：擴容時只需簡單判斷高位，避免重新計算所有元素的索引。

HashMap 初始化容量設置多少合適

return (int) ((float) expectedSize / 0.75F + 1.0F);

18、1.8 對 HashMap 主要做了哪些優化

1. 引入紅黑樹，在 Java 8 之前，HashMap 的沖突解決方式是完全基于鏈表的。當哈希沖突較多時，鏈表會變得很長，導致查找效率下降（時間復雜度為 O(n)）。當鏈表的長度超過閾值（默認是 8）時，HashMap 會將鏈表轉換為紅黑樹（一種自平衡的二叉搜索樹）。紅黑樹的查找、插入和刪除操作的時間復雜度為 O(log n)，顯著提高了性能。
2. 優化哈希函數，Java 8 的哈希函數更加簡潔，只進行一次異或運算（h ^ (h >>> 16)）。
3. 改進擴容機制，Java 7 擴容時，所有元素需要重新計算索引，并插入到新的桶數組中。Java 8擴容時，HashMap 利用了 高位掩碼 的特性，將元素分為兩類，避免了重新計算所有元素的索引，提高了擴容的效率。

19、HashMap 和 Hashtable 有什么區別

• 線程是否安全： HashMap 是非線程安全的，Hashtable 是線程安全的,因為 Hashtable 內部的方法基本都經過synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧！）
• 效率： 因為線程安全的問題，HashMap 要比 Hashtable 效率高一點。另外，Hashtable 基本被淘汰，不要在代碼中使用它。
• 對 Null key 和 Null value 的支持： HashMap 可以存儲 null 的 key 和 value，但 null 作為鍵只能有一個，null 作為值可以有多個；Hashtable 不允許有 null 鍵和 null 值，否則會拋出 NullPointerException。
• 底層數據結構： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為 8）時，將鏈表轉化為紅黑樹（將鏈表轉換成紅黑樹前會判斷，如果當前數組的長度小于64，那么會選擇先進行數組擴容，而不是轉換為紅黑樹），以減少搜索時間（后文中我會結合源碼對這一過程進行分析）。Hashtable 沒有這樣的機制。
• 初始容量大小和每次擴充容量大小的不同 ： ① 創建時如果不指定容量初始值，Hashtable 默認的初始大小為 11，之后每次擴充，容量變為原來的 2n+1。HashMap 默認的初始化大小為 16。之后每次擴充，容量變為原來的 2 倍。② 創建時如果給定了容量初始值，那么 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充為 2 的冪次方大小。也就是說 HashMap 總是使用 2 的冪作為哈希表的大小。

20、HashMap 和 TreeMap 區別

TreeMap 和HashMap 都繼承自AbstractMap ，但是需要注意的是TreeMap它還實現了NavigableMap接口和SortedMap 接口。

實現 NavigableMap 接口讓 TreeMap 有了對集合內元素的搜索的能力。

實現SortedMap接口讓 TreeMap 有了對集合中的元素根據鍵排序的能力。默認是按 key 的升序排序，不過我們也可以指定排序的比較器。示例代碼如下：

TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {@Overridepublic int compare(Person person1, Person person2) {int num = person1.getAge() - person2.getAge();return Integer.compare(num, 0);}});

綜上，相比于HashMap來說 TreeMap 主要多了對集合中的元素根據鍵排序的能力以及對集合內元素的搜索的能力。

21、為什么 HashMap 線程不安全

Java8中已經不再采用頭插法，改為尾插法，即直接插入鏈表尾部，因此不會出現死循環和數據丟失，但是在多線程環境下仍然會有數據覆蓋的問題。

首先我們看一下Java8中put操作的源碼

注意紅色框內的部分，如果插入元素沒有發生hash碰撞則直接插入。

如果線程A和線程B同時進行put，剛好兩條數據的hash值相同，如果線程A已經判斷該位置數據為null，此時被掛起，線程B正常執行，并且正常插入數據，隨后線程A繼續執行就會將線程A的數據給覆蓋。發生線程不安全。

Java7中頭插法擴容會導致死循環和數據丟失，Java8中將頭插法改為尾插法后死循環和數據丟失已經得到解決，但仍然有數據覆蓋的問題。

有什么辦法能解決HashMap線程不安全的問題呢

并發環境下推薦使用 ConcurrentHashMap（ConcurrentHashMap 在jdk1.7中使用分段鎖，在jdk1.8中使用 CAS + synchronized） 。或者

// 方式一：使用古老實現類Hashtable（是直接在操作方法上加 synchronized 關鍵字，鎖住整個table數組，粒度比較大）
// Hashtable<String, String> table = new Hashtable<>();// 方式二：使用Collections集合類（ 是使用 Collections 集合工具的內部類，通過傳入 Map 封裝出一個 SynchronizedMap 對象，內部定義了一個對象鎖，方法內通過對象鎖實現）
// Map<String, String> map1 = Collections.synchronizedMap(map);

22、怎么確保一個集合不能被修改

final關鍵字可以修飾類，方法，成員變量，final修飾的類不能被繼承，final修飾的方法不能被重寫，final修飾的成員變量必須初始化值，如果這個成員變量是基本數據類型，表示這個變量的值是不可改變的，如果說這個成員變量是引用類型，則表示這個引用的地址值是不能改變的，但是這個引用所指向的對象里面的內容還是可以改變的。

集合（map，set，list…）都是引用類型，所以我們如果用final修飾的話，集合里面的內容還是可以修改的。我們可以采用Collections包下來讓集合不能修改：

1. Collections.unmodifiableList(List)
2. Collections.unmodifiableSet(Set)
3. Collections.unmodifiableSet(map)

23、LinkedHashMap 怎么實現有序的

LinkedHashMap維護了一個雙向鏈表，有頭尾節點，同時 LinkedHashMap 節點 Entry 內部除了繼承 HashMap 的 Node 屬性，還有 before 和 after 用于標識前置節點和后置節點。

可以實現按插入的順序或訪問順序排序。

24、ConcurrentHashMap 實現原理

HashMap 在我們日常的開發中使用頻率最高的一個工具類之一，然而使用 HashMap 最大的問題之一就是它是線程不安全的，如果我們想要線程安全, 這時候就可以選擇使用 ConcurrentHashMap，ConcurrentHashMap 和 HashMap 的功能是基本一樣的，ConcurrentHashMap 是 HashMap 的線程安全版本。

ConcurrentHashMap 原理

ConcurrentHashMap 是 HashMap 的線程安全版本，如何實現線程的安全性？

加鎖。但是這個鎖應該怎么加呢？在 HashTable 中，是直接在 put 和 get 方法上加上了 synchronized，理論上來說 ConcurrentHashMap 也可以這么做，但是這么做鎖的粒度太大，會非常影響并發性能，所以在 ConcurrentHashMap 中并沒有采用這么直接簡單粗暴的方法，其內部采用了非常精妙的設計，大大減少了鎖的競爭，提升了并發性能。

ConcurrentHashmap線程安全在jdk1.7版本是基于分段鎖實現，在jdk1.8是基于CAS + synchronized實現。

jdk1.7 基于分段鎖

在JDK1.7中，ConcurrentHashMap使用了分段鎖技術，即將哈希表分成多個段，每個段擁有一個獨立的鎖。這樣可以在多個線程同時訪問哈希表時，只需要鎖住需要操作的那個段，而不是整個哈希表，從而提高了并發性能。

雖然JDK1.7的這種方式可以減少鎖競爭，但是在高并發場景下，仍然會出現鎖競爭，從而導致性能下降。

在 JDK1.7 版本中，ConcurrentHashMap 由數組 + Segment + 分段鎖實現，其內部分為一個個段（Segment）數組，Segment 通過繼承 ReentrantLock 來進行加鎖，通過每次鎖住一個 segment 來降低鎖的粒度而且保證了每個 segment 內的操作的線程安全性，從而實現線程安全。下圖就是 JDK1.7 版本中 ConcurrentHashMap 的結構示意圖

實際上就是相當于每個Segment都是一個HashMap，默認的Segment長度是16，也就是支持16個線程的并發寫，Segment之間相互不會受到影響。

+-------------------+       +-------------------+
| Segment 1         |       | Segment 2         |
| +---------------+ |       | +---------------+ |
| | HashEntry[]   | |       | | HashEntry[]   | |
| +---------------+ |       | +---------------+ |
+-------------------+       +-------------------+

put流程

整個流程和HashMap非常類似，只不過是先定位到具體的Segment，然后通過ReentrantLock去操作而已，后面的流程，就和HashMap基本上是一樣的。

1. 計算hash，定位到segment，segment如果是空就先初始化
2. 使用ReentrantLock加鎖，如果獲取鎖失敗則嘗試自旋，自旋超過次數就阻塞獲取，保證一定獲取鎖成功
3. 遍歷HashEntry，就是和HashMap一樣，數組中key和hash一樣就直接替換，不存在就再插入鏈表，鏈表同樣操作

get流程

get也很簡單，key通過hash定位到segment，再遍歷鏈表定位到具體的元素上，需要注意的是value是volatile的，所以get是不需要加鎖的。

但是這么做的缺陷就是每次通過 hash 確認位置時需要 2 次才能定位到當前 key 應該落在哪個槽：

• 通過 hash 值和 段數組長度-1 進行位運算確認當前 key 屬于哪個段，即確認其在 segments 數組的位置。
• 再次通過 hash 值和 table 數組（即 ConcurrentHashMap 底層存儲數據的數組）長度 - 1進行位運算確認其所在。

jdk1.8 基于CAS + synchronized

在JDK1.8中，ConcurrentHashMap的實現方式進行了改進，使用CAS+Synchronized的機制來保證線程安全。實現線程安全不是在數據結構上下功夫，它得數據結構和hashMap一樣，，ConcurrentHashMap會在添加或刪除元素時，首先使用CAS操作來嘗試修改元素，如果CAS操作失敗，則使用Synchronizeds鎖住當前槽，再次嘗試put或者delete。這樣可以避免分段鎖機制下的鎖粒度太大，以及在高并發場景下，由于線程數量過多導致的鎖競爭問題，提高了并發性能。

+---+    +---+    +---+
| 0 | -> | A | -> | B | -> null
+---+    +---+    +---+
| 1 | -> null
+---+
| 2 | -> | C | -> null
+---+    +---+
|...|
+---+
| n | -> null
+---+

put流程

1. 首先計算hash，遍歷node數組，如果node是空的話，就通過CAS+自旋的方式初始化
2. 如果當前數組位置是空則直接通過CAS自旋寫入數據
3. 如果哈希槽處已經有節點，且hash值為MOVED，說明需要擴容，執行擴容
4. 如果都不滿足，就使用synchronized寫入數據，寫入數據同樣判斷鏈表、紅黑樹，鏈表寫入和HashMap的方式一樣，key hash一樣就覆蓋，反之就尾插法，鏈表長度超過8就轉換成紅黑樹

get查詢

get很簡單，和HashMap基本相同，通過key計算位置，table該位置key相同就返回，如果是紅黑樹按照紅黑樹獲取，否則就遍歷鏈表獲取。

25、ConcurrentHashMap 和 Hashtable 區別

HashTable 使用的是 Synchronized 關鍵字修飾，ConcurrentHashMap 是JDK1.7使用了鎖分段技術來保證線程安全的。JDK1.8ConcurrentHashMap取消了Segment分段鎖，采用CAS和synchronized來保證并發安全。數據結構跟HashMap1.8的結構類似，數組+鏈表/紅黑二叉樹。

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

26、Iterator 怎么使用

/*** 測試Collection迭代對象的方式 迭代器的方式 Iterator接口，定義了迭代Collection 容器中對象的統一操作方式 集合對象中的迭代器是采用內部類的方式實現 這些內部類都實現了Iterator接口* 使用迭代器迭代集合中數據期間，不能使用集合對象 刪除集合中的數據*/@Testpublic void test02() {Collection<String> c1 = new HashSet<String>();c1.add("java");c1.add("css");c1.add("html");c1.add("javaScript");Iterator<String> it = c1.iterator();while (it.hasNext()) {String str = it.next();System.out.println(str);// css java javaScript htmlif (str.equals("css")) {// c1.remove(str);//會拋出異常it.remove();}}System.out.println(c1);// [java, javaScript, html]}

27、Java 集合使用注意事項總結

① 集合判空

判斷所有集合內部的元素是否為空，使用 isEmpty() 方法，而不是 size()==0 的方式。

② 集合轉 Map

在使用 java.util.stream.Collectors 類的 toMap() 方法轉為 Map 集合時，一定要注意當 value 為 null 時會拋 NPE 異常。

List<Person> bookList = new ArrayList<>();
bookList.add(new Person("jack","18163138123"));
bookList.add(new Person("martin",null));
// 空指針異常
bookList.stream().collect(Collectors.toMap(Person::getName, Person::getPhoneNumber));

③ 集合遍歷

不要在 foreach 循環里進行元素的 remove/add 操作。remove 元素請使用 Iterator 方式，如果并發操作，需要對 Iterator 對象加鎖。

通過反編譯你會發現 foreach 語法底層其實還是依賴 Iterator 。不過， remove/add 操作直接調用的是集合自己的方法，而不是 Iterator 的 remove/add方法這就導致 Iterator 莫名其妙地發現自己有元素被 remove/add ，然后，它就會拋出一個 ConcurrentModificationException 來提示用戶發生了并發修改異常。這就是單線程狀態下產生的 fail-fast 機制。

fail-fast 機制 ：多個線程對 fail-fast 集合進行修改的時候，可能會拋出ConcurrentModificationException。 即使是單線程下也有可能會出現這種情況，上面已經提到過。

④ 集合去重

可以利用 Set 元素唯一的特性，可以快速對一個集合進行去重操作，避免使用 List 的 contains() 進行遍歷去重或者判斷包含操作。

⑤ 集合轉數組

使用集合轉數組的方法，必須使用集合的 toArray(T[] array)，傳入的是類型完全一致、長度為 0 的空數組。toArray(T[] array) 方法的參數是一個泛型數組，如果 toArray 方法中沒有傳遞任何參數的話返回的是 Object類 型數組。

String [] s= new String[]{"dog", "lazy", "a", "over", "jumps", "fox", "brown", "quick", "A"
};
List<String> list = Arrays.asList(s);
Collections.reverse(list);
//沒有指定類型的話會報錯
s=list.toArray(new String[0]);

由于 JVM 優化，new String[0]作為Collection.toArray()方法的參數現在使用更好，new String[0]就是起一個模板的作用，指定了返回數組的類型，0 是為了節省空間，因為它只是為了說明返回的類型。

⑥ 數組轉集合

使用工具類 Arrays.asList() 把數組轉換成集合時，不能使用其修改集合相關的方法， 它的 add/remove/clear 方法會拋出 UnsupportedOperationException 異常。

基本數據類型數組轉集合

錯誤代碼如下（示例）：

int[] arr = {1, 2, 3};
List list = Arrays.asList(arr);
System.out.println("集合為：" + list + " 長度為：" + list.size());
//集合為：[[I@4554617c] 長度為：1

當把基礎數據類型的數組轉為集合時，由于Arrays.asList參數為可變長泛型，而基本類型是無法泛型化的，所以它把int[] arr數組當成了一個泛型對象，所以集合中最終只有一個元素arr。

正確代碼如下（示例）：

//（1）通過for循環遍歷數組將其轉為集合
int a[] = {1, 2, 3};
ArrayList<Integer> aList = new ArrayList<>();
for (Integer i : a) {aList.add(i);
}//（2）使用Java8的Stream實現轉換（依賴boxed的裝箱操作）
int [] myArray = { 1, 2, 3 };
List myList = Arrays.stream(myArray).boxed().collect(Collectors.toList());

包裝數據類型數組轉集合

 Integer[] arr = {1, 2, 3};List list = Arrays.asList(arr);System.out.println("集合為：" + list + " 長度為：" + list.size());
//集合為：[1, 2, 3] 長度為：3

使用集合的修改方法: add()、remove()、clear()會拋出異常。

List myList = Arrays.asList(1, 2, 3);
myList.add(4);//運行時報錯：UnsupportedOperationException
myList.remove(1);//運行時報錯：UnsupportedOperationException
myList.clear();//運行時報錯：UnsupportedOperationException

Arrays.asList() 方法返回的并不是 java.util.ArrayList ，而是 java.util.Arrays 的一個內部類，這個內部類并沒有實現集合的修改方法或者說并沒有重寫這些方法。

28、如何利用List實現LRU

LRU 即最近最少使用策略，基于時空局部性原理（最近問的，未來也會被訪問），往往作為緩存淘汰的策略，如Redis和GuavaMap都使用了這種淘汰策略。

我們可以基于LinkedList來實現LRU，因為LinkedList基于雙向鏈表，每個結點都會記錄上一個和下一個的節點，
具體實現方式如下：

package com.example.test.other.base;import java.util.LinkedList;public class LruListCache<E> {private final int maxSize;private final LinkedList<E> list = new LinkedList<>();public LruListCache(int maxSize) {this.maxSize = maxSize;}public void add(E e) {if (list.size() < maxSize) {list.addFirst(e);} else {list.removeLast();list.addFirst(e);}}public E get(int index) {E e = list.get(index);list.remove(e);add(e);return e;}@Overridepublic String toString() {return list.toString();}public static void main(String[] args) {LruListCache lruListCache = new LruListCache(2);lruListCache.add(1);lruListCache.add(2);lruListCache.add(3);System.out.println(lruListCache.get(1));System.out.println(lruListCache.toString());}
}