【JavaSE面試篇】Java集合部分高頻八股匯總

概念

1.?說說Java中的集合？

2.?Java中的線程安全的集合有什么？

3.?Collections和Collection的區別？

4.?集合遍歷的方法有哪些？

List

5.?講一下java里面list的幾種實現，幾種實現有什么不同？

6.?Arraylist和LinkedList的區別？

7.?為什么ArrayList不是線程安全的，具體來說是哪里不安全？

8.?ArrayList的擴容機制說一下

9.?線程安全的 List， CopyonWriteArraylist是如何實現線程安全的？

Map

10. 如何對map進行快速遍歷？

11.?HashMap實現原理介紹一下？

12.?了解的哈希沖突解決方法有哪些？

13.?HashMap是線程安全的嗎？

14.?HashMap的put(key,val)和get(key)過程

15.?HashMap一般用什么做Key？為啥String適合做Key呢？

16.?為什么HashMap要用紅黑樹而不是平衡二叉樹？

17.?hashmap key可以為null嗎？

18.?重寫HashMap的equal和hashcode方法需要注意什么？

19.?列舉HashMap在多線程下可能會出現的問題？

20.?HashMap的擴容機制介紹一下

21.?HashMap的大小為什么是2的n次方大小呢？

22.?說說hashmap的負載因子

23.?Hashmap和Hashtable有什么不一樣的？Hashmap一般怎么用？

24.?ConcurrentHashMap怎么實現的？

25.?ConcurrentHashMap用了悲觀鎖還是樂觀鎖?

26.?HashTable 底層實現原理是什么？

27.?HashTable線程安全是怎么實現的？

28.?hashtable 和concurrentHashMap有什么區別？

29.?說一下HashMap和Hashtable、ConcurrentMap的區別？

Set

30.?Set集合有什么特點？如何實現key無重復的？

31.?有序的Set是什么？記錄插入順序的集合是什么？

概念

1.?說說Java中的集合？

用過的一些 Java 集合類：

ArrayList：動態數組，實現了?List?接口，支持動態增長。
LinkedList：雙向鏈表，也實現了?List?接口，支持快速的插入和刪除操作。
HashMap：基于哈希表的?Map?實現，存儲鍵值對，通過鍵快速查找值。
HashSet：基于?HashMap?實現的?Set?集合，用于存儲唯一元素。
TreeMap：基于紅黑樹實現的有序?Map?集合，可以按照鍵的順序進行排序。
LinkedHashMap：基于哈希表和雙向鏈表實現的?Map?集合，保持插入順序或訪問順序。

2.?Java中的線程安全的集合有什么？

在?java.util?包中的線程安全的類主要 2 個，其他都是非線程安全的。

Vector：線程安全的動態數組，其內部方法基本都經過?synchronized?修飾，如果不需要線程安全，并不建議選擇，畢竟同步是有額外開銷的。Vector?內部是使用對象數組來保存數據，可以根據需要自動的增加容量，當數組已滿時，會創建新的數組，并拷貝原有數組數據。
Hashtable：線程安全的哈希表，HashTable?的加鎖方法是給每個方法加上?synchronized?關鍵字，這樣鎖住的是整個?Table?對象，不支持?null?鍵和值，由于同步導致的性能開銷，所以已經很少被推薦使用，如果要保證線程安全的哈希表，可以用?ConcurrentHashMap。

java.util.concurrent?包提供的都是線程安全的集合：

并發 Map：

ConcurrentHashMap：它與?HashTable?的主要區別是二者加鎖粒度的不同，在 JDK1.7，ConcurrentHashMap?加的是分段鎖，也就是?Segment?鎖，每個?Segment?含有整個?table?的一部分，這樣不同分段之間的并發操作就互不影響。在 JDK 1.8 ，它取消了?Segment?字段，直接在?table?元素上加鎖，實現對每一行進行加鎖，進一步減小了并發沖突的概率。對于?put?操作，如果?Key?對應的數組元素為?null，則通過?CAS?操作（Compare and Swap）將其設置為當前值。如果?Key?對應的數組元素（也即鏈表表頭或者樹的根元素）不為?null，則對該元素使用?synchronized?關鍵字申請鎖，然后進行操作。如果該?put?操作使得當前鏈表長度超過一定閾值，則將該鏈表轉換為紅黑樹，從而提高尋址效率。
ConcurrentSkipListMap：實現了一個基于?SkipList（跳表）算法的可排序的并發集合，SkipList?是一種可以在對數預期時間內完成搜索、插入、刪除等操作的數據結構，通過維護多個指向其他元素的 “跳躍” 鏈接來實現高效查找。

并發 Set：

ConcurrentSkipListSet：是線程安全的有序的集合。底層是使用?ConcurrentSkipListMap?實現。
CopyOnWriteArraySet：是線程安全的?Set?實現，它是線程安全的無序的集合，可以將它理解成線程安全的?HashSet。有意思的是，CopyOnWriteArraySet?和?HashSet?雖然都繼承于共同的父類?AbstractSet；但是，HashSet?是通過 “散列表” 實現的，而?CopyOnWriteArraySet?則是通過 “動態數組（CopyOnWriteArrayList）” 實現的，并不是散列表。

并發 List：

CopyOnWriteArrayList：它是?ArrayList?的線程安全的變體，其中所有寫操作（add，set?等）都通過對底層數組進行全新復制來實現，允許存儲?null?元素。即當對象進行寫操作時，使用了?Lock?鎖做同步處理，內部拷貝了原數組，并在新數組上進行添加操作，最后將新數組替換掉舊數組；若進行的讀操作，則直接返回結果，操作過程中不需要進行同步。

并發 Queue：

ConcurrentLinkedQueue：是一個適用于高并發場景下的隊列，它通過無鎖的方式（CAS），實現了高并發狀態下的高性能。通常，ConcurrentLinkedQueue?的性能要好于?BlockingQueue?。
BlockingQueue：與?ConcurrentLinkedQueue?的使用場景不同，BlockingQueue?的主要功能并不在于提升高并發時的隊列性能，而在于簡化多線程間的數據共享。BlockingQueue?提供一種讀寫阻塞等待的機制，即如果消費者速度較快，則?BlockingQueue?則可能被清空，此時消費線程再試圖從?BlockingQueue?讀取數據時就會被阻塞。反之，如果生產線程較快，則?BlockingQueue?可能會被裝滿，此時，生產線程再試圖向?BlockingQueue?隊列裝入數據時，便會被阻塞等待。

并發 Deque：

LinkedBlockingDeque：是一個線程安全的雙端隊列實現。它的內部使用鏈表結構，每一個節點都維護了一個前驅節點和一個后驅節點。LinkedBlockingDeque?沒有進行讀寫鎖的分離，因此同一時間只能有一個線程對其進行操作
ConcurrentLinkedDeque：ConcurrentLinkedDeque?是一種基于鏈接節點的無限并發鏈表。可以安全地并發執行插入、刪除和訪問操作。當許多線程同時訪問一個公共集合時，ConcurrentLinkedDeque?是一個合適的選擇。

3.?Collections和Collection的區別？

Collection：是 Java 集合框架中的一個接口，它是所有集合類的基礎接口。它定義了一組通用的操作和方法，如添加、刪除、遍歷等，用于操作和管理一組對象。Collection?接口有許多實現類，如?List、Set?和?Queue?等。
Collections（注意有一個?s）：是 Java 提供的一個工具類，位于?java.util?包中。它提供了一系列靜態方法，用于對集合進行操作和算法。Collections?類中的方法包括排序、查找、替換、反轉、隨機化等等。這些方法可以對實現了?Collection?接口的集合進行操作，如?List?和?Set。

4.?集合遍歷的方法有哪些？

在 Java 中，集合的遍歷方法主要有以下幾種：

普通?for?循環：可以使用帶有索引的普通?for?循環來遍歷?List。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");for (int i = 0; i < list.size(); i++) {String element = list.get(i);System.out.println(element);
}

增強?for?循環（for-each?循環）：用于循環訪問數組或集合中的元素。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");for (String element : list) {System.out.println(element);
}

Iterator?迭代器：可以使用迭代器來遍歷集合，特別適用于需要刪除元素的情況。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");Iterator<String> iterator = list.iterator();
while(iterator.hasNext()) {String element = iterator.next();System.out.println(element);
}

ListIterator?列表迭代器：ListIterator?是迭代器的子類，可以雙向訪問列表并在迭代過程中修改元素。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");ListIterator<String> listIterator= list.listIterator();
while(listIterator.hasNext()) {String element = listIterator.next();System.out.println(element);
}

使用?forEach?方法： Java 8 引入了?forEach?方法，可以對集合進行快速遍歷。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");list.forEach(element -> System.out.println(element));

Stream API： Java 8 的?Stream API?提供了豐富的功能，可以對集合進行函數式操作，如過濾、映射等。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");list.stream().forEach(element -> System.out.println(element));

List

常見的 List 集合（非線程安全）：

ArrayList?：基于動態數組實現，它允許快速的隨機訪問，即通過索引訪問元素的時間復雜度為 O (1)。在添加和刪除元素時，如果操作位置不是列表末尾，可能需要移動大量元素，性能相對較低。適用于需要頻繁隨機訪問元素，而對插入和刪除操作性能要求不高的場景，如數據的查詢和展示等。
LinkedList?：基于雙向鏈表實現，在插入和刪除元素時，只需修改鏈表的指針，不需要移動大量元素，時間復雜度為 O (1)。但隨機訪問元素時，需要從鏈表頭或鏈表尾開始遍歷，時間復雜度為 O (n)。適用于需要頻繁進行插入和刪除操作的場景，如隊列、棧等數據結構的實現，以及需要在列表中間頻繁插入和刪除元素的情況。

常見的 List 集合（線程安全）：

Vector?：和?ArrayList?類似，也是基于數組實現。Vector?中的方法大多是同步的，這使得它在多線程環境下可以保證數據的一致性，但在單線程環境下，由于同步帶來的開銷，性能會略低于?ArrayList?。
CopyOnWriteArrayList?：在對列表進行修改（如添加、刪除元素）時，會創建一個新的底層數組，將修改操作應用到新數組上，而讀操作仍然在原數組上進行，這樣可以保證讀操作不會被寫操作阻塞，實現了讀寫分離，提高了并發性能。適用于讀操作遠遠多于寫操作的并發場景，如事件監聽列表等，在這種場景下可以避免大量的鎖競爭，提高系統的性能和響應速度。

5.?講一下java里面list的幾種實現，幾種實現有什么不同？

ArrayList：是應用更加廣泛的動態數組實現，它本身不是線程安全的，所以性能要好很多。與?Vector?近似，ArrayList?也是可以根據需要調整容量，不過兩者的調整邏輯有所區別，Vector?在擴容時會提高 1 倍，而?ArrayList?則是增加 50%。
LinkedList：顧名思義是 Java 提供的雙向鏈表，所以它不需要像上面兩種那樣調整容量，它也不是線程安全的。

這幾種實現具體在什么場景下應該用哪種？

Vector?和?ArrayList：作為動態數組，其內部元素以數組形式順序存儲的，所以非常適合隨機訪問的場合。除了尾部插入和刪除元素，往往性能會相對較差，比如我們在中間位置插入一個元素，需要移動后續所有元素。
而?LinkedList：進行節點插入、刪除卻要高效得多，但是隨機訪問性能則要比動態數組慢。

6.?Arraylist和LinkedList的區別？

ArrayList和LinkedList都是 Java 中常見的集合類，它們都實現了List接口。

底層數據結構不同：ArrayList使用數組實現，通過索引進行快速訪問元素。LinkedList使用鏈表實現，通過節點之間的指針進行元素的訪問和操作。
插入和刪除操作的效率不同：ArrayList在尾部的插入和刪除操作效率較高，但在中間或開頭的插入和刪除操作效率較低，需要移動元素。LinkedList在任意位置的插入和刪除操作效率都比較高，因為只需要調整節點之間的指針，但是LinkedList是不支持隨機訪問的，所以除了頭結點外插入和刪除的時間復雜度都是O(n)，效率也不是很高所以LinkedList基本沒人用。
隨機訪問的效率不同：ArrayList支持通過索引進行快速隨機訪問，時間復雜度為O(1)。LinkedList需要從頭或尾開始遍歷鏈表，時間復雜度為O(n)。
空間占用：ArrayList在創建時需要分配一段連續的內存空間，因此會占用較大的空間。LinkedList每個節點只需要存儲元素和指針，因此相對較小。
使用場景：ArrayList適用于頻繁隨機訪問和尾部的插入刪除操作，而LinkedList適用于頻繁的中間插入刪除操作和不需要隨機訪問的場景。
線程安全：這兩個集合都不是線程安全的，Vector是線程安全的

7.?為什么ArrayList不是線程安全的，具體來說是哪里不安全？

在高并發添加數據下，ArrayList會暴露三個問題；

部分值為null（我們并沒有add null進去）
索引越界異常
size與我們add的數量不符

三種情況都是如何產生的：

部分值為null：當線程 1 走到了擴容那里發現當前size是 9，而數組容量是 10，所以不用擴容，這時候 cpu 讓出執行權，線程 2 也進來了，發現size是 9，而數組容量是 10，所以不用擴容，這時候線程 1 繼續執行，將數組下標索引為 9 的位置set值了，還沒有來得及執行size++，這時候線程 2 也來執行了，又把數組下標索引為 9 的位置set了一遍，這時候兩個先后進行size++，導致下標索引 10 的地方就為null了。
索引越界異常：線程 1 走到擴容那里發現當前size是 9，數組容量是 10 不用擴容，cpu 讓出執行權，線程 2 也發現不用擴容，這時候數組的容量就是 10，而線程 1?set完之后size++，這時候線程 2 再進來size就是 10，數組的大小只有 10，而你要設置下標索引為 10 的就會越界（數組的下標索引從 0 開始）；
size與我們add的數量不符：這個基本上每次都會發生，這個理解起來也很簡單，因為size++本身就不是原子操作，可以分為三步：獲取size的值，將size的值加 1，將新的size值覆蓋掉原來的，線程 1 和線程 2 拿到一樣的size值加完了同時覆蓋，就會導致一次沒有加上，所以肯定不會與我們add的數量保持一致的；

8.?ArrayList的擴容機制說一下

ArrayList在添加元素時，如果當前元素個數已經達到了內部數組的容量上限，就會觸發擴容操作。
ArrayList的擴容操作主要包括以下幾個步驟：

計算新的容量：一般情況下，新的容量會擴大為原容量的 1.5 倍（在 JDK 10 之后，擴容策略做了調整），然后檢查是否超過了最大容量限制。
創建新的數組：根據計算得到的新容量，創建一個新的更大的數組。
將元素復制：將原來數組中的元素逐個復制到新數組中。
更新引用：將ArrayList內部指向原數組的引用指向新數組。
完成擴容：擴容完成后，可以繼續添加新元素。

ArrayList的擴容操作涉及到數組的復制和內存的重新分配，所以在頻繁添加大量元素時，擴容操作可能會影響性能。為了減少擴容帶來的性能損耗，可以在初始化ArrayList時預分配足夠大的容量，避免頻繁觸發擴容操作。

之所以擴容是 1.5 倍，是因為 1.5 可以充分利用移位操作，減少浮點數或者運算時間和運算次數。

// 新容量計算
int newCapacity = oldCapacity + (oldCapacity >> 1);

9.?線程安全的 List， CopyonWriteArraylist是如何實現線程安全的？

CopyOnWriteArrayList底層也是通過一個數組保存數據，使用volatile關鍵字修飾數組，保證當前線程對數組對象重新賦值后，其他線程可以及時感知到。

private transient volatile Object[] array;

在寫入操作時，加了一把互斥鎖ReentrantLock以保證線程安全。

public boolean add(E e) {//獲取鎖final ReentrantLock lock = this.lock;//加鎖lock.lock();try {//獲取到當前List集合保存數據的數組Object[] elements = getArray();//獲取該數組的長度（這是一個伏筆，同時len也是新數組的最后一個元素的索引值）int len = elements.length;//將當前數組拷貝一份的同時，讓其長度加1Object[] newElements = Arrays.copyOf(elements, len + 1);//將加入的元素放在新數組最后一位，len不是舊數組長度嗎，為什么現在用它當成新數組的最后一個元素的索引？newElements[len] = e;//替換引用，將數組的引用指向給新數組的地址setArray(newElements);return true;} finally {//釋放鎖lock.unlock();}
}

看到源碼可以知道寫入新元素時，首先會先將原來的數組拷貝一份并且讓原來數組的長度 + 1 后就得到了一個新數組，新數組里的元素和舊數組的元素一樣并且長度比舊數組多一個長度，然后將新加入的元素放置都在新數組最后一個位置后，用新數組的地址替換掉老數組的地址就能得到最新的數據了。

在我們執行替換地址操作之前，讀取的是老數組的數據，數據是有效數據；執行替換地址操作之后，讀取的是新數組的數據，同樣也是有效數據，而且使用該方式能比讀寫都加鎖要更加的效率。

現在我們來看讀操作，讀是沒有加鎖的，所以讀是一直都能讀

public E get(int index) {return get(getArray(), index);
}

Map

常見的 Map 集合（非線程安全）：

HashMap?：是基于哈希表實現的?Map?，它根據鍵的哈希值來存儲和獲取鍵值對，JDK 1.8 中是用數組 + 鏈表 + 紅黑樹來實現的。HashMap?是非線程安全的，在多線程環境下，當多個線程同時對?HashMap?進行操作時，可能會導致數據不一致或出現死循環等問題。比如在擴容時，多個線程可能會同時修改哈希表的結構，從而破壞數據的完整性。
LinkedHashMap?：繼承自?HashMap?，它在?HashMap?的基礎上，使用雙向鏈表維護了鍵值對的插入順序或訪問順序，使得迭代順序與插入順序或訪問順序一致。由于它繼承自?HashMap?，在多線程并發訪問時，同樣會出現與?HashMap?類似的線程安全問題。
TreeMap?：是基于紅黑樹實現的?Map?，它可以對鍵進行排序，默認按照自然順序排序，也可以通過指定的比較器進行排序。TreeMap?是非線程安全的，在多線程環境下，如果多個線程同時對?TreeMap?進行插入、刪除等操作，可能會破壞紅黑樹的結構，導致數據不一致或程序出現異常。

常見的 Map 集合（線程安全）：

Hashtable?：是早期 Java 提供的線程安全的?Map?實現，它的實現方式與?HashMap?類似，但在方法上使用了?synchronized?關鍵字來保證線程安全。通過在每個可能修改?Hashtable?狀態的方法上加上?synchronized?關鍵字，使得在同一時刻，只能有一個線程能夠訪問?Hashtable?的這些方法，從而保證了線程安全。
ConcurrentHashMap?：在 JDK 1.8 以前采用了分段鎖等技術來提高并發性能。在?ConcurrentHashMap?中，將數據分成多個段（Segment），每個段都有自己的鎖。在進行插入、刪除等操作時，只需要獲取相應段的鎖，而不是整個?Map?的鎖，這樣可以允許多個線程同時訪問不同的段，提高了并發訪問的效率。在 JDK 1.8 以后是通過?volatile + CAS?或者?synchronized?來保證線程安全的。

10. 如何對map進行快速遍歷？

使用 Lambda 表達式和?forEach()?方法：在 Java 8 及以上版本中，可以使用 Lambda 表達式和?forEach()?方法來遍歷?Map，這種方式更加簡潔和函數式。

import java.util.HashMap;
import java.util.Map;public class MapTraversalExample {public static void main(String[] args) {Map<String, Integer> map = new HashMap<>();map.put("key1", 1);map.put("key2", 2);map.put("key3", 3);// 使用 Lambda 表達式和 forEach() 方法遍歷 Mapmap.forEach((key, value) -> System.out.println("Key: " + key + ", Value: " + value));}
}

使用?Stream API：Java 8 引入的?Stream API?也可以用于遍歷?Map，可以將?Map?轉換為流，然后進行各種操作。

import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;public class MapTraversalExample {public static void main(String[] args) {Map<String, Integer> map = new HashMap<>();map.put("key1", 1);map.put("key2", 2);map.put("key3", 3);// 使用 Stream API 遍歷 Mapmap.entrySet().stream().forEach(entry -> System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue()));// 還可以進行其他操作，如過濾、映射等Map<String, Integer> filteredMap = map.entrySet().stream().filter(entry -> entry.getValue() > 1).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));System.out.println(filteredMap);}
}

11.?HashMap實現原理介紹一下？

在 JDK 1.7 版本之前，HashMap?數據結構是數組和鏈表，HashMap通過哈希算法將元素的鍵（Key）映射到數組中的槽位（Bucket）。如果多個鍵映射到同一個槽位，它們會以鏈表的形式存儲在同一個槽位上，因為鏈表的查詢時間是O(n)，所以沖突很嚴重，一個索引上的鏈表非常長，效率就很低了。

所以在?JDK 1.8?版本的時候做了優化，當一個鏈表的長度超過 8 的時候就轉換數據結構，不再使用鏈表存儲，而是使用紅黑樹，查找時使用紅黑樹，時間復雜度O（log n)，可以提高查詢性能，但是在數量較少時，即數量小于 6 時，會將紅黑樹轉換回鏈表。

12.?了解的哈希沖突解決方法有哪些？

鏈接法：使用鏈表或其他數據結構來存儲沖突的鍵值對，將它們鏈接在同一個哈希桶中。
開放尋址法：在哈希表中找到另一個可用的位置來存儲沖突的鍵值對，而不是存儲在鏈表中。常見的開放尋址方法包括線性探測、二次探測和雙重散列。
再哈希法（Rehashing）：當發生沖突時，使用另一個哈希函數再次計算鍵的哈希值，直到找到一個空槽來存儲鍵值對。
哈希桶擴容：當哈希沖突過多時，可以動態地擴大哈希桶的數量，重新分配鍵值對，以減少沖突的概率。

13.?HashMap是線程安全的嗎？

hashmap 不是線程安全的，hashmap 在多線程會存在下面的問題：

JDK 1.7 HashMap 采用數組 + 鏈表的數據結構，多線程背景下，在數組擴容的時候，存在 Entry 鏈死循環和數據丟失問題。
JDK 1.8 HashMap 采用數組 + 鏈表 + 紅黑二叉樹的數據結構，優化了 1.7 中數組擴容的方案，解決了 Entry 鏈死循環和數據丟失問題。但是多線程背景下，put 方法存在數據覆蓋的問題。

如果要保證線程安全，可以通過這些方法來保證：

多線程環境可以使用Collec tions.synchronizedMap同步加鎖的方式，還可以使用HashTable，但是同步的方式顯然性能不達標，而ConurrentHashMap更適合高并發場景使用。
ConcurrentHashmap在 JDK1.7 和 1.8 的版本改動比較大，1.7 使用Segment+HashEntry分段鎖的方式實現，1.8 則拋棄了Segment，改為使用CAS+synchronized+Node實現，同樣也加入了紅黑樹，避免鏈表過長導致性能的問題。

14.?HashMap的put(key,val)和get(key)過程

存儲對象時，我們將K/V傳給put方法時，它調用hashCode計算hash從而得到bucket位置，進一步存儲，HashMap會根據當前bucket的占用情況自動調整容量 (超過Load Facotr則resize為原來的 2 倍)。
獲取對象時，我們將K傳給get，它調用hashCode計算hash從而得到bucket位置，并進一步調用?equals()方法確定鍵值對。如果發生碰撞的時候，Hashmap通過鏈表將產生碰撞沖突的元素組織起來，在Java 8中，如果一個bucket中碰撞沖突的元素超過某個限制 (默認是8)，則使用紅黑樹來替換鏈表，從而提高速度。

15.?HashMap一般用什么做Key？為啥String適合做Key呢？

用?string?做?key，因為?String對象是不可變的，一旦創建就不能被修改，這確保了Key的穩定性。如果Key是可變的，可能會導致hashCode和equals方法的不一致，進而影響HashMap的正確性。

16.?為什么HashMap要用紅黑樹而不是平衡二叉樹？

平衡二叉樹追求的是一種?“完全平衡”?狀態：任何結點的左右子樹的高度差不會超過 1，優勢是樹的結點是很平均分配的。這個要求實在是太嚴了，導致每次進行插入 / 刪除節點的時候，幾乎都會破壞平衡樹的第二個規則，進而我們都需要通過左旋和右旋來進行調整，使之再次成為一顆符合要求的平衡樹。
紅黑樹不追求這種完全平衡狀態，而是追求一種?“弱平衡”?狀態：整個樹最長路徑不會超過最短路徑的 2 倍。優勢是雖然犧牲了一部分查找的性能效率，但是能夠換取一部分維持樹平衡狀態的成本。與平衡樹不同的是，紅黑樹在插入、刪除等操作，不會像平衡樹那樣，頻繁著破壞紅黑樹的規則，所以不需要頻繁著調整，這也是我們為什么大多數情況下使用紅黑樹的原因。

17.?hashmap key可以為null嗎？

可以為 null。

hashMap 中使用hash()方法來計算key的哈希值，當key為空時，直接另key的哈希值為 0，不走 key.hashCode ()方法；

static final int hash(Object key) {int h;//當key等于null的時候，不走hashCode()方法return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hashMap 雖然支持key和value為null，但是null作為key只能有一個，null作為value可以有多個；
因為 hashMap 中，如果key值一樣，那么會覆蓋相同key值的value為最新，所以key為null只能有一個。

18.?重寫HashMap的equal和hashcode方法需要注意什么？

HashMap 使用Key對象的hashCode()和equals方法去決定key-value對的索引。當我們試著從HashMap中獲取值的時候，這些方法也會被用到。如果這些方法沒有被正確地實現，在這種情況下，兩個不同Key也許會產生相同的 hashCode ()和equals ()?輸出，HashMap將會認為它們是相同的，然后覆蓋它們，而非把它們存儲到不同的地方。

同樣的，所有不允許存儲重復數據的集合類都使用 hashCode ()和equals ()?去查找重復，所以正確實現它們非常重要。equals ()和hashCode ()?的實現應該遵循以下規則：

如果o1.equals(o2)，那么o1.hashCode() == o2.hashCode()總是為true的。
如果o1.hashCode() == o2.hashCode()，并不意味著o1.equals(o2)會為true。

19.?列舉HashMap在多線程下可能會出現的問題？

JDK1.7中的?HashMap?使用頭插法插入元素，在多線程的環境下，擴容的時候有可能導致環形鏈表的出現，形成死循環。因此，JDK1.8使用尾插法插入元素，在擴容時會保持鏈表元素原本的順序，不會出現環形鏈表的問題。
多線程同時執行?put?操作，如果計算出來的索引位置是相同的，那會造成前一個?key?被后一個?key?覆蓋，從而導致元素的丟失。此問題在JDK 1.7和?JDK 1.8?中都存在。

20.?HashMap的擴容機制介紹一下

hashMap 默認的負載因子是 0.75，即如果 hashmap 中的元素個數超過了總容量 75%，則會觸發擴容，擴容分為兩個步驟：

第 1 步是對哈希表長度的擴展（2 倍）
第 2 步是將舊哈希表中的數據放到新的哈希表中。

因為我們使用的是 2 次冪的擴展 (指長度擴為原來 2 倍)，所以，元素的位置要么是在原位置，要么是在原位置再移動 2 次冪的位置。

如我們從 16 擴展為 32 時，具體的變化如下所示：

因此元素在重新計算hash之后，因為n變為 2 倍，那么n - 1的mask范圍在高位多1bit(紅色)，因此新的index就會發生這樣的變化：

因此，我們在擴充HashMap的時候，不需要重新計算hash，只需要看看原來的hash值新增的那個bit是 1 還是 0 就好了，是 0 的話索引沒變，是 1 的話索引變成 “原索引 +oldCap”。可以看看下圖為 16 擴充為 32 的resize示意圖：

這個設計確實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由于新增的1bit是 0 還是 1 可以認為是隨機的，因此resize的過程，均勻的把之前的沖突的節點分散到新的bucket了。

21.?HashMap的大小為什么是2的n次方大小呢？

在?JDK1.7?中，HashMap?整個擴容過程就是分別取出數組元素，一般該元素是最后一個放入鏈表中的元素，然后遍歷以該元素為頭的單向鏈表元素，依據每個被遍歷元素的?hash?值計算其在新數組中的下標，然后進行交換。這樣的擴容方式會將原來哈希沖突的單向鏈表尾部變成擴容后單向鏈表的頭部。

而在?JDK 1.8?中，HashMap?對擴容操作做了優化。由于擴容數組的長度是 2 倍關系，所以對于假設初始?tableSize = 4?要擴容到 8 來說就是 0100 到 1000 的變化（左移一位就是 2 倍），在擴容中只用判斷原來的?hash?值和左移動的一位（newtable?的值）按位與操作是 0 或 1 就行，0 的話索引不變，1 的話索引變成原索引加上擴容前數組。

之所以能通過這種 “與運算” 來重新分配索引，是因為?hash?值本來就是隨機的，而?hash?按位與上?newTable?得到的 0（擴容前的索引位置）和 1（擴容前索引位置加上擴容前數組長度的數值索引處）就是隨機的，所以擴容的過程就能把之前哈希沖突的元素再隨機分布到不同的索引中去。

22.?說說hashmap的負載因子

HashMap?負載因子?loadFactor?的默認值是 0.75，當?HashMap?中的元素個數超過了容量的 75% 時，就會進行擴容。

默認負載因子為 0.75，是因為它提供了空間和時間復雜度之間的良好平衡。

負載因子太低會導致大量的空桶浪費空間，負載因子太高會導致大量的碰撞，降低性能。0.75 的負載因子在這兩個因素之間取得了良好的平衡。

23.?Hashmap和Hashtable有什么不一樣的？Hashmap一般怎么用？

HashMap 線程不安全，效率高一點，可以存儲 null 的 key 和 value，null 的 key 只能有一個，null 的 value 可以有多個。默認初始容量為 16，每次擴充變為原來 2 倍。創建時如果給定了初始容量，則擴充為 2 的冪次方大小。底層數據結構為數組 + 鏈表，插入元素后如果鏈表長度大于閾值（默認為 8），先判斷數組長度是否小于 64，如果小于，則擴充數組，反之將鏈表轉化為紅黑樹，以減少搜索時間。
HashTable 線程安全，效率低一點，其內部方法基本都經過 synchronized 修飾，不可以有 null 的 key 和 value。默認初始容量為 11，每次擴容變為原來的 2n+1。創建時給定了初始容量，會直接用給定的大小。底層數據結構為數組 + 鏈表。它基本被淘汰了，要保證線程安全可以用 ConcurrentHashMap。
怎么用：HashMap 主要用來存儲鍵值對，可以調用 put 方法向其中加入元素，調用 get 方法獲取某個鍵對應的值，也可以通過 containsKey 方法查看某個鍵是否存在等

24.?ConcurrentHashMap怎么實現的？

JDK 1.7 ConcurrentHashMap

在 JDK 1.7 中它使用的是數組加鏈表的形式實現的，而數組又分為：大數組?Segment?和小數組?HashEntry。?Segment?是一種可重入鎖（ReentrantLock），在?ConcurrentHashMap?里扮演鎖的角色；HashEntry?則用于存儲鍵值對數據。一個?ConcurrentHashMap?里包含一個?Segment?數組，一個?Segment?里包含一個?HashEntry?數組，每個?HashEntry?是一個鏈表結構的元素。

JDK 1.7?ConcurrentHashMap?分段鎖技術將數據分成一段一段的存儲，然后給每一段數據配一把鎖，當一個線程占用鎖訪問其中一個段數據的時候，其他段的數據也能被其他線程訪問，能夠實現真正的并發訪問。

JDK 1.8 ConcurrentHashMap

在 JDK 1.7 中，ConcurrentHashMap?雖然是線程安全的，但因為它的底層實現是數組 + 鏈表的形式，所以在數據比較多的情況下訪問是很慢的，因為要遍歷整個鏈表，而 JDK 1.8 則使用了數組 + 鏈表 / 紅黑樹的方式優化了?ConcurrentHashMap?的實現，具體實現結構如下：

JDK 1.8 ConcurrentHashMap JDK 1.8 ConcurrentHashMap 主要通過?volatile + CAS?或者?synchronized?來實現的線程安全的。添加元素時首先會判斷容器是否為空：

如果為空則使用?volatile?加?CAS?來初始化
如果容器不為空，則根據存儲的元素計算該位置是否為空。
- 如果根據存儲的元素計算結果為空，則利用?CAS?設置該節點；
- 如果根據存儲的元素計算結果不為空，則使用?synchronized?，然后，遍歷桶中的數據，并替換或新增節點到桶中，最后再判斷是否需要轉為紅黑樹，這樣就能保證并發訪問時的線程安全了。

如果把上面的執行用一句話歸納的話，就相當于是ConcurrentHashMap通過對頭結點加鎖來保證線程安全的，鎖的粒度相比?Segment?來說更小了，發生沖突和加鎖的頻率降低了，并發操作的性能就提高了。

而且 JDK 1.8 使用的是紅黑樹優化了之前的固定鏈表，那么當數據量比較大的時候，查詢性能也得到了很大的提升，從之前的?O(n)?優化到了?O(logn)?的時間復雜度。

25.?ConcurrentHashMap用了悲觀鎖還是樂觀鎖?

悲觀鎖和樂觀鎖都有用到。

添加元素時首先會判斷容器是否為空：

如果為空則使用?volatile?加?CAS（樂觀鎖）?來初始化。
如果容器不為空，則根據存儲的元素計算該位置是否為空。
如果根據存儲的元素計算結果為空，則利用?CAS（樂觀鎖）?設置該節點；
如果根據存儲的元素計算結果不為空，則使用?synchronized（悲觀鎖）?，然后，遍歷桶中的數據，并替換或新增節點到桶中，最后再判斷是否需要轉為紅黑樹，這樣就能保證并發訪問時的線程安全了。

26.?HashTable 底層實現原理是什么？

Hashtable 的底層數據結構主要是數組加上鏈表，數組是主體，鏈表是解決 hash 沖突存在的。
HashTable 是線程安全的，實現方式是Hashtable 的所有公共方法均采用 synchronized 關鍵字，當一個線程訪問同步方法，另一個線程也訪問的時候，就會陷入阻塞或者輪詢的狀態。

27.?HashTable線程安全是怎么實現的？

Hashtable是通過使用了 synchronized 關鍵字來保證其線程安全

因為它的put，get做成了同步方法，保證了Hashtable的線程安全性，每個操作數據的方法都進行同步控制之后，由此帶來的問題任何一個時刻，只能有一個線程可以操縱Hashtable，所以其效率比較低。
?

28.?hashtable 和concurrentHashMap有什么區別？

底層數據結構：

jdk7 之前的 ConcurrentHashMap 底層采用的是分段的數組 + 鏈表實現，jdk8 之后采用的是數組 + 鏈表 / 紅黑樹；
HashTable 采用的是數組 + 鏈表，數組是主體，鏈表是解決 hash 沖突存在的。

實現線程安全的方式：

jdk8 以前，ConcurrentHashMap 采用分段鎖，對整個數組進行了分段分割，每一把鎖只鎖容器里的一部分數據，多線程訪問不同數據段里的數據，就不會存在鎖競爭，提高了并發訪問；jdk8 以后，直接采用數組 + 鏈表 / 紅黑樹，并發控制使用 CAS 和 synchronized 操作，更加提高了速度。
HashTable：所有的方法都加了鎖來保證線程安全，但是效率非常的低下，當一個線程訪問同步方法，另一個線程也訪問的時候，就會陷入阻塞或者輪詢的狀態。

29.?說一下HashMap和Hashtable、ConcurrentMap的區別？

HashMap線程不安全，效率高一點，可以存儲 null 的 key 和 value，null 的 key 只能有一個，null 的 value 可以有多個。默認初始容量為 16，每次擴充變為原來 2 倍。創建時如果給定了初始容量，則擴充為 2 的冪次方大小。底層數據結構為數組 + 鏈表，插入元素后如果鏈表長度大于閾值（默認為 8），先判斷數組長度是否小于 64，如果小于，則擴充數組，反之將鏈表轉化為紅黑樹，以減少搜索時間。
HashTable線程安全，效率低一點，其內部方法基本都經過synchronized修飾，不可以有 null 的 key 和 value。默認初始容量為 11，每次擴容變為原來的 2n+1。創建時給定了初始容量，會直接用給定的大小。底層數據結構為數組 + 鏈表。它基本被淘汰了，要保證線程安全可以用ConcurrentHashMap。
ConcurrentHashMap是 Java 中的一個線程安全的哈希表實現，它可以在多線程環境下并發地進行讀寫操作，而不需要像傳統的HashTable那樣在讀寫時加鎖。ConcurrentHashMap的實現原理主要基于分段鎖和CAS操作。它將整個哈希表分成了多Segment（段），每個Segment都類似于一個小的HashMap，它擁有自己的數組和一個獨立的鎖。在ConcurrentHashMap中，讀操作不需要鎖，可以直接對Segment進行讀取，而寫操作則只需要鎖定對應的Segment，而不是整個哈希表，這樣可以大大提高并發性能。

Set

30.?Set集合有什么特點？如何實現key無重復的？

set 集合特點：Set 集合中的元素是唯一的，不會出現重復的元素。
set 實現原理：Set 集合通過內部的數據結構（如哈希表、紅黑樹等）來實現 key 的無重復。當向 Set 集合中插入元素時，會先根據元素的hashCode值來確定元素的存儲位置，然后再通過equals方法來判斷是否已經存在相同的元素，如果存在則不會再次插入，保證了元素的唯一性。

31.?有序的Set是什么？記錄插入順序的集合是什么？

有序的 Set 是 TreeSet 和 LinkedHashSet。TreeSet 是基于紅黑樹實現，保證元素的自然順序。LinkedHashSet 是基于雙重鏈表和哈希表的結合來實現元素的有序存儲，保證元素添加的自然順序
記錄插入順序的集合通常指的是 LinkedHashSet，它不僅保證元素的唯一性，還可以保持元素的插入順序。當需要在 Set 集合中記錄元素的插入順序時，可以選擇使用 LinkedHashSet 來實現。