文章目錄
集合容器概述
什么是集合
集合的特點
集合和數組的區(qū)別
使用集合框架的好處
常用的集合類有哪些？
List，Set，Map三者的區(qū)別？List、Set、Map 是否繼承自 Collection 接口？List、
Map、Set 三個接口存取元素時，各有什么特點？
集合框架底層數據結構
哪些集合類是線程安全的？
Java集合的快速失敗機制 “fail-fast”？
怎么確保一個集合不能被修改？
Collection接口
List接口
迭代器 Iterator 是什么？
Iterator 怎么使用？有什么特點？
如何邊遍歷邊移除 Collection 中的元素？
Iterator 和 ListIterator 有什么區(qū)別？
遍歷一個 List 有哪些不同的方式？每種方法的實現原理是什么？Java 中 List 遍歷的最佳實踐是什么？
說一下 ArrayList 的優(yōu)缺點
如何實現數組和 List 之間的轉換？
ArrayList 和 LinkedList 的區(qū)別是什么？
ArrayList 和 Vector 的區(qū)別是什么？
插入數據時，ArrayList、LinkedList、Vector誰速度較快？闡述 ArrayList、Vector、LinkedList 的存儲性能和特性？
多線程場景下如何使用 ArrayList？
為什么 ArrayList 的 elementData 加上 transient 修飾？
List 和 Set 的區(qū)別
Set接口
說一下 HashSet 的實現原理？
HashSet如何檢查重復？HashSet是如何保證數據不可重復的？
HashSet與HashMap的區(qū)別
Queue
BlockingQueue是什么？
在 Queue 中 poll()和 remove()有什么區(qū)別？
Map接口
說一下 HashMap 的實現原理？
HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底層實現
JDK1.8之前
JDK1.8之后
JDK1.7 VS JDK1.8 比較
HashMap的put方法的具體流程？
HashMap的擴容操作是怎么實現的？
HashMap是怎么解決哈希沖突的？
什么是哈希？
什么是哈希沖突？
HashMap的數據結構
hash()函數
JDK1.8新增紅黑樹
總結
能否使用任何類作為 Map 的 key？
為什么HashMap中String、Integer這樣的包裝類適合作為K？
如果使用Object作為HashMap的Key，應該怎么辦呢？
HashMap為什么不直接使用hashCode()處理后的哈希值直接作為table的下標？
HashMap 的長度為什么是2的冪次方
HashMap 與 HashTable 有什么區(qū)別？
如何決定使用 HashMap 還是 TreeMap？
HashMap 和 ConcurrentHashMap 的區(qū)別
ConcurrentHashMap 和 Hashtable 的區(qū)別？
ConcurrentHashMap 底層具體實現知道嗎？實現原理是什么？
輔助工具類
Array 和 ArrayList 有何區(qū)別？
如何實現 Array 和 List 之間的轉換？
comparable 和 comparator的區(qū)別？
Collection 和 Collections 有什么區(qū)別？
TreeMap 和 TreeSet 在排序時如何比較元素？Collections 工具類中的 sort()方法如何比較元素？
Java面試總結匯總，整理了包括Java基礎知識，集合容器，并發(fā)編程，JVM，常用開源框架Spring，MyBatis，數據庫，中間件等，包含了作為一個Java工程師在面試中需要用到或者可能用到的絕大部分知識。歡迎大家閱讀，本人見識有限，寫的博客難免有錯誤或者疏忽的地方，還望各位大佬指點，在此表示感激不盡。文章持續(xù)更新中…

集合容器概述
什么是集合
集合框架：用于存儲數據的容器。

集合框架是為表示和操作集合而規(guī)定的一種統(tǒng)一的標準的體系結構。
任何集合框架都包含三大塊內容：對外的接口、接口的實現和對集合運算的算法。

接口：表示集合的抽象數據類型。接口允許我們操作集合時不必關注具體實現，從而達到“多態(tài)”。在面向對象編程語言中，接口通常用來形成規(guī)范。

實現：集合接口的具體實現，是重用性很高的數據結構。

算法：在一個實現了某個集合框架中的接口的對象身上完成某種有用的計算的方法，例如查找、排序等。這些算法通常是多態(tài)的，因為相同的方法可以在同一個接口被多個類實現時有不同的表現。事實上，算法是可復用的函數。
它減少了程序設計的辛勞。

集合框架通過提供有用的數據結構和算法使你能集中注意力于你的程序的重要部分上，而不是為了讓程序能正常運轉而將注意力于低層設計上。
通過這些在無關API之間的簡易的互用性，使你免除了為改編對象或轉換代碼以便聯(lián)合這些API而去寫大量的代碼。 它提高了程序速度和質量。
集合的特點
集合的特點主要有如下兩點：

對象封裝數據，對象多了也需要存儲。集合用于存儲對象。

對象的個數確定可以使用數組，對象的個數不確定的可以用集合。因為集合是可變長度的。

集合和數組的區(qū)別

數組是固定長度的；集合可變長度的。

數組可以存儲基本數據類型，也可以存儲引用數據類型；集合只能存儲引用數據類型。

數組存儲的元素必須是同一個數據類型；集合存儲的對象可以是不同數據類型。

數據結構：就是容器中存儲數據的方式。

對于集合容器，有很多種。因為每一個容器的自身特點不同，其實原理在于每個容器的內部數據結構不同。

集合容器在不斷向上抽取過程中，出現了集合體系。在使用一個體系的原則：參閱頂層內容。建立底層對象。

使用集合框架的好處

1. 容量自增長；
2. 提供了高性能的數據結構和算法，使編碼更輕松，提高了程序速度和質量；
3. 允許不同 API 之間的互操作，API之間可以來回傳遞集合；
4. 可以方便地擴展或改寫集合，提高代碼復用性和可操作性。
5. 通過使用JDK自帶的集合類，可以降低代碼維護和學習新API成本。

常用的集合類有哪些？

Map接口和Collection接口是所有集合框架的父接口：

1. Collection接口的子接口包括：Set接口和List接口
2. Map接口的實現類主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等
3. Set接口的實現類主要有：HashSet、TreeSet、LinkedHashSet等
4. List接口的實現類主要有：ArrayList、LinkedList、Stack以及Vector等

image.png

Java 容器分為 Collection 和 Map 兩大類，Collection集合的子接口有Set、List、Queue三種子接口。我們比較常用的是Set、List，Map接口不是collection的子接口。

Collection集合主要有List和Set兩大接口

List：一個有序（元素存入集合的順序和取出的順序一致）容器，元素可以重復，可以插入多個null元素，元素都有索引。常用的實現類有 ArrayList、LinkedList 和 Vector。
Set：一個無序（存入和取出順序有可能不一致）容器，不可以存儲重復元素，只允許存入一個null元素，必須保證元素唯一性。Set 接口常用實現類是 HashSet、LinkedHashSet 以及 TreeSet。
Map是一個鍵值對集合，存儲鍵、值和之間的映射。 Key無序，唯一；value 不要求有序，允許重復。Map沒有繼承于Collection接口，從Map集合中檢索元素時，只要給出鍵對象，就會返回對應的值對象。

Map 的常用實現類：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap
集合框架底層數據結構
Collection

1. List
   Arraylist： Object數組
   Vector： Object數組
   LinkedList： 雙向循環(huán)鏈表
2. Set
   HashSet（無序，唯一）：基于 HashMap 實現的，底層采用 HashMap 來保存元素
   LinkedHashSet： LinkedHashSet 繼承與 HashSet，并且其內部是通過 LinkedHashMap 來實現的。有點類似于我們之前說的LinkedHashMap 其內部是基于 Hashmap 實現一樣，不過還是有一點點區(qū)別的。
   TreeSet（有序，唯一）： 紅黑樹(自平衡的排序二叉樹。)
   Map

HashMap： JDK1.8之前HashMap由數組+鏈表組成的，數組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8以后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間
LinkedHashMap：LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈式散列結構即由數組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結構的基礎上，增加了一條雙向鏈表，使得上面的結構可以保持鍵值對的插入順序。同時通過對鏈表進行相應的操作，實現了訪問順序相關邏輯。
HashTable： 數組+鏈表組成的，數組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的
TreeMap： 紅黑樹（自平衡的排序二叉樹）
哪些集合類是線程安全的？
vector：就比arraylist多了個同步化機制（線程安全），因為效率較低，現在已經不太建議使用。在web應用中，特別是前臺頁面，往往效率（頁面響應速度）是優(yōu)先考慮的。
statck：堆棧類，先進后出。
hashtable：就比hashmap多了個線程安全。
enumeration：枚舉，相當于迭代器。
Java集合的快速失敗機制 “fail-fast”？
是java集合的一種錯誤檢測機制，當多個線程對集合進行結構上的改變的操作時，有可能會產生 fail-fast 機制。

例如：假設存在兩個線程（線程1、線程2），線程1通過Iterator在遍歷集合A中的元素，在某個時候線程2修改了集合A的結構（是結構上面的修改，而不是簡單的修改集合元素的內容），那么這個時候程序就會拋出 ConcurrentModificationException 異常，從而產生fail-fast機制。

原因：迭代器在遍歷時直接訪問集合中的內容，并且在遍歷過程中使用一個 modCount 變量。集合在被遍歷期間如果內容發(fā)生變化，就會改變modCount的值。每當迭代器使用hashNext()/next()遍歷下一個元素之前，都會檢測modCount變量是否為expectedmodCount值，是的話就返回遍歷；否則拋出異常，終止遍歷。

解決辦法：

在遍歷過程中，所有涉及到改變modCount值得地方全部加上synchronized。

使用CopyOnWriteArrayList來替換ArrayList

怎么確保一個集合不能被修改？
可以使用 Collections. unmodifiableCollection(Collection c) 方法來創(chuàng)建一個只讀集合，這樣改變集合的任何操作都會拋出 Java. lang. UnsupportedOperationException 異常。

image.png

迭代器 Iterator 是什么？
Iterator 接口提供遍歷任何 Collection 的接口。我們可以從一個 Collection 中使用迭代器方法來獲取迭代器實例。迭代器取代了 Java 集合框架中的 Enumeration，迭代器允許調用者在迭代過程中移除元素。

Iterator 怎么使用？有什么特點？

image.png

如何邊遍歷邊移除 Collection 中的元素？

image.png

image.png

運行以上錯誤代碼會報 ConcurrentModificationException 異常。這是因為當使用 foreach(for(Integer i : list)) 語句時，會自動生成一個iterator 來遍歷該 list，但同時該 list 正在被 Iterator.remove() 修改。Java 一般不允許一個線程在遍歷 Collection 時另一個線程修改它。

Iterator 和 ListIterator 有什么區(qū)別？
Iterator 可以遍歷 Set 和 List 集合，而 ListIterator 只能遍歷 List。
Iterator 只能單向遍歷，而 ListIterator 可以雙向遍歷（向前/后遍歷）。
ListIterator 實現 Iterator 接口，然后添加了一些額外的功能，比如添加一個元素、替換一個元素、獲取前面或后面元素的索引位置。
遍歷一個 List 有哪些不同的方式？每種方法的實現原理是什么？Java 中 List 遍歷的最佳實踐是什么？
遍歷方式有以下幾種：

for 循環(huán)遍歷，基于計數器。在集合外部維護一個計數器，然后依次讀取每一個位置的元素，當讀取到最后一個元素后停止。

迭代器遍歷，Iterator。Iterator 是面向對象的一個設計模式，目的是屏蔽不同數據集合的特點，統(tǒng)一遍歷集合的接口。Java 在 Collections 中支持了 Iterator 模式。

foreach 循環(huán)遍歷。foreach 內部也是采用了 Iterator 的方式實現，使用時不需要顯式聲明 Iterator 或計數器。優(yōu)點是代碼簡潔，不易出錯；缺點是只能做簡單的遍歷，不能在遍歷過程中操作數據集合，例如刪除、替換。

最佳實踐：Java Collections 框架中提供了一個 RandomAccess 接口，用來標記 List 實現是否支持 Random Access。

如果一個數據集合實現了該接口，就意味著它支持 Random Access，按位置讀取元素的平均時間復雜度為 O(1)，如ArrayList。
如果沒有實現該接口，表示不支持 Random Access，如LinkedList。
推薦的做法就是，支持 Random Access 的列表可用 for 循環(huán)遍歷，否則建議用 Iterator 或 foreach 遍歷。
說一下 ArrayList 的優(yōu)缺點
ArrayList的優(yōu)點如下：

ArrayList 底層以數組實現，是一種隨機訪問模式。ArrayList 實現了 RandomAccess 接口，因此查找的時候非?？臁?br> ArrayList 在順序添加一個元素的時候非常方便。
ArrayList 的缺點如下：

刪除元素的時候，需要做一次元素復制操作。如果要復制的元素很多，那么就會比較耗費性能。
插入元素的時候，也需要做一次元素復制操作，缺點同上。
ArrayList 比較適合順序添加、隨機訪問的場景。

如何實現數組和 List 之間的轉換？
數組轉 List：使用 Arrays. asList(array) 進行轉換。
List 轉數組：使用 List 自帶的 toArray() 方法。

image.png

增加和刪除效率：在非首尾的增加和刪除操作，LinkedList 要比 ArrayList 效率要高，因為 ArrayList 增刪操作要影響數組內的其他數據的下標。
內存空間占用：LinkedList 比 ArrayList 更占內存，因為 LinkedList 的節(jié)點除了存儲數據，還存儲了兩個引用，一個指向前一個元素，一個指向后一個元素。
線程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；
綜合來說，在需要頻繁讀取集合中的元素時，更推薦使用 ArrayList，而在插入和刪除操作較多時，更推薦使用 LinkedList。

補充：數據結構基礎之雙向鏈表

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。
ArrayList 和 Vector 的區(qū)別是什么？
這兩個類都實現了 List 接口（List 接口繼承了 Collection 接口），他們都是有序集合

線程安全：Vector 使用了 Synchronized 來實現線程同步，是線程安全的，而 ArrayList 是非線程安全的。
性能：ArrayList 在性能方面要優(yōu)于 Vector。
擴容：ArrayList 和 Vector 都會根據實際的需要動態(tài)的調整容量，只不過在 Vector 擴容每次會增加 1 倍，而 ArrayList 只會增加 50%。
Vector類的所有方法都是同步的?？梢杂蓛蓚€線程安全地訪問一個Vector對象、但是一個線程訪問Vector的話代碼要在同步操作上耗費大量的時間。

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

插入數據時，ArrayList、LinkedList、Vector誰速度較快？闡述 ArrayList、Vector、LinkedList 的存儲性能和特性？
ArrayList、LinkedList、Vector 底層的實現都是使用數組方式存儲數據。數組元素數大于實際存儲的數據以便增加和插入元素，它們都允許直接按序號索引元素，但是插入元素要涉及數組元素移動等內存操作，所以索引數據快而插入數據慢。

Vector 中的方法由于加了 synchronized 修飾，因此 Vector 是線程安全容器，但性能上較ArrayList差。

LinkedList 使用雙向鏈表實現存儲，按序號索引數據需要進行前向或后向遍歷，但插入數據時只需要記錄當前項的前后項即可，所以 LinkedList 插入速度較快。

多線程場景下如何使用 ArrayList？
ArrayList 不是線程安全的，如果遇到多線程場景，可以通過 Collections 的 synchronizedList 方法將其轉換成線程安全的容器后再使用。例如像下面這樣：

image.png

為什么 ArrayList 的 elementData 加上 transient 修飾？

image.png

image.png

image.png

每次序列化時，先調用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后遍歷 elementData，只序列化已存入的元素，這樣既加快了序列化的速度，又減小了序列化之后的文件大小。

List 和 Set 的區(qū)別
List , Set 都是繼承自Collection 接口

List 特點：一個有序（元素存入集合的順序和取出的順序一致）容器，元素可以重復，可以插入多個null元素，元素都有索引。常用的實現類有 ArrayList、LinkedList 和 Vector。

Set 特點：一個無序（存入和取出順序有可能不一致）容器，不可以存儲重復元素，只允許存入一個null元素，必須保證元素唯一性。Set 接口常用實現類是 HashSet、LinkedHashSet 以及 TreeSet。

另外 List 支持for循環(huán)，也就是通過下標來遍歷，也可以用迭代器，但是set只能用迭代，因為他無序，無法用下標來取得想要的值。

Set和List對比

Set：檢索元素效率低下，刪除和插入效率高，插入和刪除不會引起元素位置改變。
List：和數組類似，List可以動態(tài)增長，查找元素效率高，插入刪除元素效率低，因為會引起其他元素位置改變

Set接口
說一下 HashSet 的實現原理？
HashSet 是基于 HashMap 實現的，HashSet的值存放于HashMap的key上，HashMap的value統(tǒng)一為PRESENT，因此 HashSet 的實現比較簡單，相關 HashSet 的操作，基本上都是直接調用底層 HashMap 的相關方法來完成，HashSet 不允許重復的值。

HashSet如何檢查重復？HashSet是如何保證數據不可重復的？
向HashSet 中add ()元素時，判斷元素是否存在的依據，不僅要比較hash值，同時還要結合equles 方法比較。
HashSet 中的add ()方法會使用HashMap 的put()方法。

HashMap 的 key 是唯一的，由源碼可以看出 HashSet 添加進去的值就是作為HashMap 的key，并且在HashMap中如果K/V相同時，會用新的V覆蓋掉舊的V，然后返回舊的V。所以不會重復（ HashMap 比較key是否相等是先比較hashcode 再比較equals ）。

image.png

hashCode（）與equals（）的相關規(guī)定：

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

==是判斷兩個變量或實例是不是指向同一個內存空間 equals是判斷兩個變量或實例所指向的內存空間的值是不是相同
==是指對內存地址進行比較 equals()是對字符串的內容進行比較3.==指引用是否相同 equals()指的是值是否相同

image.png

Java.util.concurrent.BlockingQueue是一個隊列，在進行檢索或移除一個元素的時候，它會等待隊列變?yōu)榉强?；當在添加一個元素時，它會等待隊列中的可用空間。BlockingQueue接口是Java集合框架的一部分，主要用于實現生產者-消費者模式。我們不需要擔心等待生產者有可用的空間，或消費者有可用的對象，因為它都在BlockingQueue的實現類中被處理了。Java提供了集中BlockingQueue的實現，比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。

在 Queue 中 poll()和 remove()有什么區(qū)別？
相同點：都是返回第一個元素，并在隊列中刪除返回的對象。
不同點：如果沒有元素 poll()會返回 null，而 remove()會直接拋出 NoSuchElementException 異常。

image.png

HashMap的數據結構： 在Java編程語言中，最基本的結構就是兩種，一個是數組，另外一個是模擬指針（引用），所有的數據結構都可以用這兩個基本結構來構造的，HashMap也不例外。HashMap實際上是一個“鏈表散列”的數據結構，即數組和鏈表的結合體。

HashMap 基于 Hash 算法實現的

1. 當我們往Hashmap中put元素時，利用key的hashCode重新hash計算出當前對象的元素在數組中的下標
2. 存儲時，如果出現hash值相同的key，此時有兩種情況。(1)如果key相同，則覆蓋原始值；(2)如果key不同（出現沖突），則將當前的key-value放入鏈表中
3. 獲取時，直接找到hash值對應的下標，在進一步判斷key是否相同，從而找到對應值。
4. 理解了以上過程就不難明白HashMap是如何解決hash沖突的問題，核心就是使用了數組的存儲方式，然后將沖突的key的對象放入鏈表中，一旦發(fā)現沖突就在鏈表中做進一步的對比。
   需要注意Jdk 1.8中對HashMap的實現做了優(yōu)化，當鏈表中的節(jié)點數據超過八個之后，該鏈表會轉為紅黑樹來提高查詢效率，從原來的O(n)到O(logn)

HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底層實現
在Java中，保存數據有兩種比較簡單的數據結構：數組和鏈表。數組的特點是：尋址容易，插入和刪除困難；鏈表的特點是：尋址困難，但插入和刪除容易；所以我們將數組和鏈表結合在一起，發(fā)揮兩者各自的優(yōu)勢，使用一種叫做拉鏈法的方式可以解決哈希沖突。

JDK1.8之前
JDK1.8之前采用的是拉鏈法。拉鏈法：將鏈表和數組相結合。也就是說創(chuàng)建一個鏈表數組，數組中每一格就是一個鏈表。若遇到哈希沖突，則將沖突的值加到鏈表中即可。

image.png

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

image.png

1. resize 擴容優(yōu)化
2. 引入了紅黑樹，目的是避免單條鏈表過長而影響查詢效率，紅黑樹算法請參考

3. 解決了多線程死循環(huán)問題，但仍是非線程安全的，多線程時可能會造成數據丟失問題。
   image.png
   
   

   HashMap的put方法的具體流程？
   當我們put的時候，首先計算 key的hash值，這里調用了 hash方法，hash方法實際是讓key.hashCode()與key.hashCode()>>>16進行異或操作，高16bit補0，一個數和0異或不變，所以 hash 函數大概的作用就是：高16bit不變，低16bit和高16bit做了一個異或，目的是減少碰撞。按照函數注釋，因為bucket數組大小是2的冪，計算下標index = (table.length - 1) & hash，如果不做 hash 處理，相當于散列生效的只有幾個低 bit 位，為了減少散列的碰撞，設計者綜合考慮了速度、作用、質量之后，使用高16bit和低16bit異或來簡單處理減少碰撞，而且JDK8中用了復雜度 O（logn）的樹結構來提升碰撞下的性能。

image.png

image.png

①.判斷鍵值對數組table[i]是否為空或為null，否則執(zhí)行resize()進行擴容；

②.根據鍵值key計算hash值得到插入的數組索引i，如果table[i]==null，直接新建節(jié)點添加，轉向⑥，如果table[i]不為空，轉向③；

③.判斷table[i]的首個元素是否和key一樣，如果相同直接覆蓋value，否則轉向④，這里的相同指的是hashCode以及equals；

④.判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向⑤；

⑤.遍歷table[i]，判斷鏈表長度是否大于8，大于8的話把鏈表轉換為紅黑樹，在紅黑樹中執(zhí)行插入操作，否則進行鏈表的插入操作；遍歷過程中若發(fā)現key已經存在直接覆蓋value即可；

⑥.插入成功后，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容。

HashMap的擴容操作是怎么實現的？
①.在jdk1.8中，resize方法是在hashmap中的鍵值對大于閥值時或者初始化時，就調用resize方法進行擴容；

②.每次擴展的時候，都是擴展2倍；

③.擴展后Node對象的位置要么在原位置，要么移動到原偏移量兩倍的位置。

image.png

HashMap是怎么解決哈希沖突的？
答：在解決這個問題之前，我們首先需要知道什么是哈希沖突，而在了解哈希沖突之前我們還要知道什么是哈希才行；

什么是哈希？
Hash，一般翻譯為“散列”，也有直接音譯為“哈?！钡?，這就是把任意長度的輸入通過散列算法，變換成固定長度的輸出，該輸出就是散列值（哈希值）；這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

所有散列函數都有如下一個基本特性：根據同一散列函數計算出的散列值如果不同，那么輸入值肯定也不同。但是，根據同一散列函數計算出的散列值如果相同，輸入值不一定相同。

什么是哈希沖突？
當兩個不同的輸入值，根據同一散列函數計算出相同的散列值的現象，我們就把它叫做碰撞（哈希碰撞）。

HashMap的數據結構

image.png

這樣我們就可以將擁有相同哈希值的對象組織成一個鏈表放在hash值所對應的bucket下，但相比于hashCode返回的int類型，我們HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要遠小于int類型的范圍，所以我們如果只是單純的用hashCode取余來獲取對應的bucket這將會大大增加哈希碰撞的概率，并且最壞情況下還會將HashMap變成一個單鏈表，所以我們還需要對hashCode作一定的優(yōu)化

hash()函數
上面提到的問題，主要是因為如果使用hashCode取余，那么相當于參與運算的只有hashCode的低位，高位是沒有起到任何作用的，所以我們的思路就是讓hashCode取值出的高位也參與運算，進一步降低hash碰撞的概率，使得數據分布更平均，我們把這樣的操作稱為擾動，在JDK 1.8中的hash()函數如下：

image.png

JDK1.8新增紅黑樹

image.png

通過上面的鏈地址法（使用散列表）和擾動函數我們成功讓我們的數據分布更平均，哈希碰撞減少，但是當我們的HashMap中存在大量數據時，加入我們某個bucket下對應的鏈表有n個元素，那么遍歷時間復雜度就為O(n)，為了針對這個問題，JDK1.8在HashMap中新增了紅黑樹的數據結構，進一步使得遍歷復雜度降低至O(logn)；

總結
簡單總結一下HashMap是使用了哪些方法來有效解決哈希沖突的：

1. 使用鏈地址法（使用散列表）來鏈接擁有相同hash值的數據；
2. 使用2次擾動函數（hash函數）來降低哈希沖突的概率，使得數據分布更平均；
3. 引入紅黑樹進一步降低遍歷的時間復雜度，使得遍歷更快；

能否使用任何類作為 Map 的 key？
可以使用任何類作為 Map 的 key，然而在使用之前，需要考慮以下幾點：

如果類重寫了 equals() 方法，也應該重寫 hashCode() 方法。

類的所有實例需要遵循與 equals() 和 hashCode() 相關的規(guī)則。

如果一個類沒有使用 equals()，不應該在 hashCode() 中使用它。

用戶自定義 Key 類最佳實踐是使之為不可變的，這樣 hashCode() 值可以被緩存起來，擁有更好的性能。不可變的類也可以確保 hashCode() 和 equals() 在未來不會改變，這樣就會解決與可變相關的問題了。

為什么HashMap中String、Integer這樣的包裝類適合作為K？
答：String、Integer等包裝類的特性能夠保證Hash值的不可更改性和計算準確性，能夠有效的減少Hash碰撞的幾率

都是final類型，即不可變性，保證key的不可更改性，不會存在獲取hash值不同的情況
內部已重寫了equals()、hashCode()等方法，遵守了HashMap內部的規(guī)范（不清楚可以去上面看看putValue的過程），不容易出現Hash值計算錯誤的情況；
如果使用Object作為HashMap的Key，應該怎么辦呢？
答：重寫hashCode()和equals()方法

重寫hashCode()是因為需要計算存儲數據的存儲位置，需要注意不要試圖從散列碼計算中排除掉一個對象的關鍵部分來提高性能，這樣雖然能更快但可能會導致更多的Hash碰撞；
重寫equals()方法，需要遵守自反性、對稱性、傳遞性、一致性以及對于任何非null的引用值x，x.equals(null)必須返回false的這幾個特性，目的是為了保證key在哈希表中的唯一性；
HashMap為什么不直接使用hashCode()處理后的哈希值直接作為table的下標？
答：hashCode()方法返回的是int整數類型，其范圍為-(2 ^ 31)~(2 ^ 31 - 1)，約有40億個映射空間，而HashMap的容量范圍是在16（初始化默認值）~2 ^ 30，HashMap通常情況下是取不到最大值的，并且設備上也難以提供這么多的存儲空間，從而導致通過hashCode()計算出的哈希值可能不在數組大小范圍內，進而無法匹配存儲位置；

那怎么解決呢？

HashMap自己實現了自己的hash()方法，通過兩次擾動使得它自己的哈希值高低位自行進行異或運算，降低哈希碰撞概率也使得數據分布更平均；
在保證數組長度為2的冪次方的時候，使用hash()運算之后的值與運算（&）（數組長度 - 1）來獲取數組下標的方式進行存儲，這樣一來是比取余操作更加有效率，二來也是因為只有當數組長度為2的冪次方時，h&(length-1)才等價于h%length，三來解決了“哈希值與數組大小范圍不匹配”的問題；
HashMap 的長度為什么是2的冪次方
為了能讓 HashMap 存取高效，盡量較少碰撞，也就是要盡量把數據分配均勻，每個鏈表/紅黑樹長度大致相同。這個實現就是把數據存到哪個鏈表/紅黑樹中的算法。

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

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

那為什么是兩次擾動呢？

答：這樣就是加大哈希值低位的隨機性，使得分布更均勻，從而提高對應數組存儲下標位置的隨機性&均勻性，最終減少Hash沖突，兩次就夠了，已經達到了高位低位同時參與運算的目的；

HashMap 與 HashTable 有什么區(qū)別？

1. 線程安全： HashMap 是非線程安全的，HashTable 是線程安全的；HashTable 內部的方法基本都經過 synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧?。?/li>
2. 效率： 因為線程安全的問題，HashMap 要比 HashTable 效率高一點。另外，HashTable 基本被淘汰，不要在代碼中使用它；
3. 對Null key 和Null value的支持： HashMap 中，null 可以作為鍵，這樣的鍵只有一個，可以有一個或多個鍵所對應的值為 null。但是在 HashTable 中 put 進的鍵值只要有一個 null，直接拋NullPointerException。
4. **初始容量大小和每次擴充容量大小的不同 **： ①創(chuàng)建時如果不指定容量初始值，Hashtable 默認的初始大小為11，之后每次擴充，容量變?yōu)樵瓉淼?n+1。HashMap 默認的初始化大小為16。之后每次擴充，容量變?yōu)樵瓉淼?倍。②創(chuàng)建時如果給定了容量初始值，那么 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充為2的冪次方大小。也就是說 HashMap 總是使用2的冪作為哈希表的大小，后面會介紹到為什么是2的冪次方。
5. 底層數據結構： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間。Hashtable 沒有這樣的機制。
6. 推薦使用：在 Hashtable 的類注釋可以看到，Hashtable 是保留類不建議使用，推薦在單線程環(huán)境下使用 HashMap 替代，如果需要多線程使用則用 ConcurrentHashMap 替代。
   如何決定使用 HashMap 還是 TreeMap？
   對于在Map中插入、刪除和定位元素這類操作，HashMap是最好的選擇。然而，假如你需要對一個有序的key集合進行遍歷，TreeMap是更好的選擇?；谀愕腸ollection的大小，也許向HashMap中添加元素會更快，將map換為TreeMap進行有序key的遍歷。

HashMap 和 ConcurrentHashMap 的區(qū)別

1. ConcurrentHashMap對整個桶數組進行了分割分段(Segment)，然后在每一個分段上都用lock鎖進行保護，相對于HashTable的synchronized鎖的粒度更精細了一些，并發(fā)性能更好，而HashMap沒有鎖機制，不是線程安全的。（JDK1.8之后ConcurrentHashMap啟用了一種全新的方式實現,利用CAS算法。）
2. HashMap的鍵值對允許有null，但是ConCurrentHashMap都不允許。
   ConcurrentHashMap 和 Hashtable 的區(qū)別？
   ConcurrentHashMap 和 Hashtable 的區(qū)別主要體現在實現線程安全的方式上不同。

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

image.png

image.png

image.png

ConcurrentHashMap 底層具體實現知道嗎？實現原理是什么？
JDK1.7

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

在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式進行實現，結構如下：

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

image.png

1. 該類包含兩個靜態(tài)內部類 HashEntry 和 Segment ；前者用來封裝映射表的鍵值對，后者用來充當鎖的角色；
2. Segment 是一種可重入的鎖 ReentrantLock，每個 Segment 守護一個HashEntry 數組里得元素，當對 HashEntry 數組的數據進行修改時，必須首先獲得對應的 Segment 鎖。
   JDK1.8

在JDK1.8中，放棄了Segment臃腫的設計，取而代之的是采用Node + CAS + Synchronized來保證并發(fā)安全進行實現，synchronized只鎖定當前鏈表或紅黑二叉樹的首節(jié)點，這樣只要hash不沖突，就不會產生并發(fā)，效率又提升N倍。

image.png

附加源碼，有需要的可以看看

插入元素過程（建議去看看源碼）：

image.png

如果相應位置的Node不為空，且當前該節(jié)點不處于移動狀態(tài)，則對該節(jié)點加synchronized鎖，如果該節(jié)點的hash不小于0，則遍歷鏈表更新節(jié)點或插入新節(jié)點；

image.png

1. 如果該節(jié)點是TreeBin類型的節(jié)點，說明是紅黑樹結構，則通過putTreeVal方法往紅黑樹中插入節(jié)點；如果binCount不為0，說明put操作對數據產生了影響，如果當前鏈表的個數達到8個，則通過treeifyBin方法轉化為紅黑樹，如果oldVal不為空，說明是一次更新操作，沒有對元素個數產生影響，則直接返回舊值；
2. 如果插入的是一個新節(jié)點，則執(zhí)行addCount()方法嘗試更新元素個數baseCount；
   輔助工具類
   Array 和 ArrayList 有何區(qū)別？
   Array 可以存儲基本數據類型和對象，ArrayList 只能存儲對象。
   Array 是指定固定大小的，而 ArrayList 大小是自動擴展的。
   Array 內置方法沒有 ArrayList 多，比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。
   對于基本類型數據，集合使用自動裝箱來減少編碼工作量。但是，當處理固定大小的基本數據類型的時候，這種方式相對比較慢。

如何實現 Array 和 List 之間的轉換？
Array 轉 List： Arrays. asList(array) ；
List 轉 Array：List 的 toArray() 方法。
comparable 和 comparator的區(qū)別？
comparable接口實際上是出自java.lang包，它有一個 compareTo(Object obj)方法用來排序
comparator接口實際上是出自 java.util 包，它有一個compare(Object obj1, Object obj2)方法用來排序
一般我們需要對一個集合使用自定義排序時，我們就要重寫compareTo方法或compare方法，當我們需要對某一個集合實現兩種排序方式，比如一個song對象中的歌名和歌手名分別采用一種排序方法的話，我們可以重寫compareTo方法和使用自制的Comparator方法或者以兩個Comparator來實現歌名排序和歌星名排序，第二種代表我們只能使用兩個參數版的Collections.sort().

Collection 和 Collections 有什么區(qū)別？
java.util.Collection 是一個集合接口（集合類的一個頂級接口）。它提供了對集合對象進行基本操作的通用接口方法。Collection接口在Java 類庫中有很多具體的實現。Collection接口的意義是為各種具體的集合提供了最大化的統(tǒng)一操作方式，其直接繼承接口有List與Set。
Collections則是集合類的一個工具類/幫助類，其中提供了一系列靜態(tài)方法，用于對集合中元素進行排序、搜索以及線程安全等各種操作。
TreeMap 和 TreeSet 在排序時如何比較元素？Collections 工具類中的 sort()方法如何比較元素？
TreeSet 要求存放的對象所屬的類必須實現 Comparable 接口，該接口提供了比較元素的 compareTo()方法，當插入元素時會回調該方法比較元素的大小。TreeMap 要求存放的鍵值對映射的鍵必須實現 Comparable 接口從而根據鍵對元素進 行排 序。

Collections 工具類的 sort 方法有兩種重載的形式，

第一種要求傳入的待排序容器中存放的對象比較實現 Comparable 接口以實現元素的比較；

第二種不強制性的要求容器中的元素必須可比較，但是要求傳入第二個參數，參數是Comparator 接口的子類型（需要重寫 compare 方法實現元素的比較），相當于一個臨時定義的排序規(guī)則，其實就是通過接口注入比較元素大小的算法，也是對回調模式的應用（Java 中對函數式編程的支持）。
看到這里也疲倦了，休息一下再看吧，更多的java學習資料可以添加我的java編程技術學習裙：1080621881 。更多面試題，開發(fā)工具，基礎學習資料和視頻教程自行下載。

文章鏈接：https://blog.csdn.net/ThinkWon/article/details/104588551?utm_medium=distribute.pc_category.none-task-blog-hot-6.nonecase&depth_1-utm_source=distribute.pc_category.none-task-blog-hot-6.nonecase&request_id=