java集合面試題

1. 什么是集合

1. 集合就是一個放數據的容器，準確的說是放數據對象引用的容器
2. 集合類存放的都是對象的引用，而不是對象的本身
3. 集合類型主要有3種：set(集）、list(列表）和map(映射)。

2 常用的集合類有哪些？

• Map接口和Collection接口是所有集合框架的父接口：
• Collection接口的子接口包括：Set接口和List接口

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

3.集合框架底層數據結構

List
* Arraylist： Object數組
* Vector： Object數組
* LinkedList： 雙向循環鏈表
Set
* HashSet（無序，唯一）：基于 HashMap 實現的，底層采用 HashMap 來保存元素
* LinkedHashSet： LinkedHashSet 繼承與 HashSet，并且其內部是通過 LinkedHashMap 來實現的。有點類似于我們之前說的LinkedHashMap 其內部是基于 Hashmap 實現一樣，不過還是有一點點區別的。
* TreeSet（有序，唯一）： 紅黑樹(自平衡的排序二叉樹。)
Map
HashMap： JDK1.8之前HashMap由數組+鏈表組成的，數組是HashMap的主體，鏈表則是
主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8以后在解決哈希沖突時有了較
大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間
LinkedHashMap：LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈式散
列結構即由數組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結構的基礎上，增加
了一條雙向鏈表，使得上面的結構可以保持鍵值對的插入順序。同時通過對鏈表進行相應的
操作，實現了訪問順序相關邏輯。
HashTable： 數組+鏈表組成的，數組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突
而存在的
TreeMap： 紅黑樹（自平衡的排序二叉樹）

 4.哪些集合類是線程安全的？

　　Vector：就比Arraylist多了個 synchronized （線程安全），因為效率較低，現在已經不太建議使用。
　　hashTable：就比hashMap多了個synchronized (線程安全)，不建議使用。
　　ConcurrentHashMap：是Java5中支持高并發、高吞吐量的線程安全HashMap實現。它由Segment數組結構和HashEntry數組結構組成。

 

5. 快速失敗機制 “fail-fast”？

　　是java集合的一種錯誤檢測機制，當多個線程對集合進行結構上的改變的操作時，有可能會產生
fail-fast 機制。
例如：假設存在兩個線程（線程1、線程2），線程1通過Iterator在遍歷集合A中的元素，在某個時
候線程2修改了集合A的結構（是結構上面的修改，而不是簡單的修改集合元素的內容），那么這
個時候程序就會拋出 ConcurrentModificationException 異常，從而產生fail-fast機制。
原因：迭代器在遍歷時直接訪問集合中的內容，并且在遍歷過程中使用一個 modCount 變量。集
合在被遍歷期間如果內容發生變化，就會改變modCount的值。每當迭代器使用hashNext()/next()
遍歷下一個元素之前，都會檢測modCount變量是否為expectedmodCount值，是的話就返回遍
歷；否則拋出異常，終止遍歷。

 6.遍歷一個 List 有哪些不同的方式？每種方法的實現原理是什么？Java 中 List遍歷的最佳實踐是什么？

遍歷方式有以下幾種：

1. for 循環遍歷，基于計數器。在集合外部維護一個計數器，然后依次讀取每一個位置的元素，當讀取到最后一個元素后停止。
2. 迭代器遍歷，Iterator。Iterator 是面向對象的一個設計模式，目的是屏蔽不同數據集合的特點，統一遍歷集合的接口。Java 在 Collections 中支持了 Iterator 模式。
3. foreach 循環遍歷。foreach 內部也是采用了 Iterator 的方式實現，使用時不需要顯式聲明Iterator 或計數器。優點是代碼簡潔，不易出錯；缺點是只能做簡單的遍歷，不能在遍歷過程中操作數據集合，例如刪除、替換。

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

如果一個數據集合實現了該接口，就意味著它支持 Random Access，按位置讀取元素的平均時間復雜度為 O(1)，如ArrayList。

如果沒有實現該接口，表示不支持 Random Access，如LinkedList。
推薦的做法就是，支持 Random Access 的列表可用 for 循環遍歷，否則建議用 Iterator 或foreach 遍歷。

 

7.說一下 ArrayList 的優缺點

ArrayList的優點如下：

• ArrayList 底層以數組實現，是一種隨機訪問模式。ArrayList 實現了 RandomAccess 接口，因此查找的時候非常快。
• ArrayList 在順序添加一個元素的時候非常方便。

ArrayList 的缺點如下：

• 刪除元素的時候，需要做一次元素復制操作。如果要復制的元素很多，那么就會比較耗費性能。
• 插入元素的時候，也需要做一次元素復制操作，缺點同上。

8.ArrayList 和 LinkedList 的區別是什么？

1. 數據結構實現：ArrayList 是動態數組的數據結構實現，而 LinkedList 是雙向鏈表的數據結構實現。
2. 隨機訪問效率：ArrayList 比 LinkedList 在隨機訪問的時候效率要高，因為 LinkedList 是線性的數據存儲方式，所以需要移動指針從前往后依次查找。
3. 增加和刪除效率：在非首尾的增加和刪除操作，LinkedList 要比 ArrayList 效率要高，因為ArrayList 增刪操作要影響數組內的其他數據的下標。
4. 內存空間占用：LinkedList 比 ArrayList 更占內存，因為 LinkedList 的節點除了存儲數據，還存儲了兩個引用，一個指向前一個元素，一個指向后一個元素。
5. 線程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；

綜合來說，在需要頻繁讀取集合中的元素時，更推薦使用 ArrayList，而在插入和刪除操作較多時，更推薦使用 LinkedList。

9.ArrayList 和 Vector 的區別是什么？

1. 線程安全：Vector 使用了 Synchronized 來實現線程同步，是線程安全的，而 ArrayList 是非線程安全的。
2. 性能：ArrayList 在性能方面要優于 Vector。
3. 擴容：ArrayList 和 Vector 都會根據實際的需要動態的調整容量，只不過在 Vector 擴容每次會增加 1 倍，而 ArrayList 只會增加 50%。

10.List 和 Set 的區別

• List 特點：一個有序（元素存入集合的順序和取出的順序一致）容器，元素可以重復，可以插入多個null元素，元素都有索引。
• Set 特點：一個無序（存入和取出順序有可能不一致）容器，不可以存儲重復元素，只允許存入一個null元素，必須保證元素唯一性。
• 另外 List 支持for循環，也就是通過下標來遍歷，也可以用迭代器，但是set只能用迭代，因為他無序，無法用下標來取得想要的值。

Set和List對比

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

 11.說一下 HashSet 的實現原理？

　　HashSet 是基于 HashMap 實現的，HashSet的值存放于HashMap的key上，HashMap的value統一為present，因此 HashSet 的實現比較簡單，

相關 HashSet 的操作，基本上都是直接調用底層HashMap 的相關方法來完成，HashSet 不允許重復的值。

12.HashSet如何檢查重復？HashSet是如何保證數據不可重復的？

1. 向HashSet 中add ()元素時，判斷元素是否存在的依據，不僅要比較hash值，同時還要結合equles 方法比較。
2. HashSet 中的add ()方法會使用HashMap 的put()方法。
3. HashMap 的 key 是唯一的，由源碼可以看出 HashSet 添加進去的值就是作為HashMap 的key，并且在HashMap中如果K/V相同時，會用新的V覆蓋掉舊的V，然后返回舊的V。所以不會重復（HashMap 比較key是否相等是先比較hashcode 再比較equals ）。

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

1. 如果兩個對象相等，則hashcode一定也是相同的
2. 兩個對象相等,對兩個equals方法返回true
3. 兩個對象有相同的hashcode值，它們也不一定是相等的

　　綜上，equals方法被覆蓋過，則hashCode方法也必須被覆蓋hashCode()的默認行為是對堆上的對象產生獨特值。如果沒有重寫hashCode()，則該class的兩個

對象無論如何都不會相等（即使這兩個對象指向相同的數據）。

 13.說一下HashMap的實現原理？

• HashMap概述： HashMap是基于哈希表的Map接口的非同步實現。此實現提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。
• HashMap的數據結構： 在Java編程語言中，最基本的結構就是兩種，一個是數組，另外一個是模擬指針（引用），所有的數據結構都可以用這兩個基本結構來構造的，HashMap也不例外。HashMap實際上是一個“鏈表散列”的數據結構，即數組和鏈表的結合體。
• HashMap 基于 Hash 算法實現:,當我們往HashMap中put元素時，利用key的hashCode重新hash計算出當前對象的元素在數組中的下標存儲時，如果出現hash值相同的key，此時有兩種情況。

　　　　(1)如果key相同，則覆蓋原始值；
　　　　(2)如果key不同（出現沖突），則將當前的key-value放入鏈表中獲取時，直接找到hash值對應的下標，在進一步判斷key是否相同，從而找到對應值。
HashMap是如何解決hash沖突的問題，核心就是使用了數組的存儲方式，然后將沖突的key的對象放入鏈表中，一旦發現沖突就在鏈表中做進一步的對比。

14.HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底層實現

JDK1.8主要解決或優化了一下問題：

1. resize 擴容優化
2. 引入了紅黑樹，目的是避免單條鏈表過長而影響查詢效率，紅黑樹算法請參考
3. 解決了多線程死循環問題，但仍是非線程安全的，多線程時可能會造成數據丟失問題。
• 存儲結構上：1.7是數組+鏈表，1.8是數組+鏈表+紅黑樹
• 初始化方式：1.7有單獨的初始化函數inflateTable()，而1.8則集成到擴容函數中
• hash值的計算方式：1.7是9次擾動，4次位運算+5次異或運算，而1.8是兩次擾動，1次位運算+1次異或運算
• 插入數據的方式：1.7是頭插法，而1.8是尾插法

15.什么是紅黑樹

什么是二叉樹

1. 二叉樹簡單來說就是 每一個節上可以關聯倆個子節點

紅黑樹是一種特殊的二叉查找樹。有一些特性

1. 紅黑樹的每個結點上都有存儲位表示結點的顏色，可以是紅(Red)或黑(Black)。
2. 根結點一定是黑色。
3. 每個葉子結點（葉子結點代表終結、結尾的節點）也是黑色
4. 如果一個結點是紅色的，則它的子結點必須是黑色的。

紅黑樹的基本操作是添加、刪除。在對紅黑樹進行添加或刪除之后，都會用到旋轉方法。為什么呢？道理很簡單，添加或刪除紅黑樹中的結點之后，紅黑樹的結構就發生了變化，可能不滿足上面三條性質，也就不再是一顆紅黑樹了，而是一顆普通的樹。而通過旋轉和變色，可以使這顆樹重新成為紅黑樹。簡單點說，旋轉和變色的目的是讓樹保持紅黑樹的特性。

 

16.（HashMap）為什么不用二叉樹？

　　紅黑樹是一種平衡的二叉樹，插入、刪除、查找的最壞時間復雜度都為 O(logn)，避免了二叉樹最壞情況下的O(n)時間復雜度。

 

17.HashMap的put方法的具體流程？

 

　　1、判斷鍵值對數組table[i]是否為空（null）或者length=0，是的話就執行resize()方法進行擴容。

　　2、不是就根據鍵值key計算hash值得到插入的數組索引i。

　　3、判斷table[i]==null，如果是true，直接新建節點進行添加，如果是false，判斷table[i]的首個元素是否和key一樣，一樣就直接覆蓋。

　　4、判斷table[i]是否為treenode，即判斷是否是紅黑樹，如果是紅黑樹，直接在樹中插入鍵值對。

　　5、如果不是treenode，開始遍歷鏈表，判斷鏈表長度是否大于8，如果大于8就轉成紅黑樹，在樹中執行插入操作，如果不是大于8，就在鏈表中執行插入；在遍歷過程中判斷key是否存在，存在就直接覆蓋對應的value值。

　　6、插入成功后，就需要判斷實際存在的鍵值對數量size是否超過了最大容量threshold，如果超過了，執行resize方法進行擴容。

18.HashMap的put方法的具體流程？

　　1. 通過 hash & (table.length - 1)獲取該key對應的數據節點的hash槽;
　　2. 判斷首節點是否為空, 為空則直接返回空;
　　3. 再判斷首節點.key 是否和目標值相同, 相同則直接返回(首節點不用區分鏈表還是紅黑樹);
　　4. 首節點.next為空, 則直接返回空;
　　5. 首節點是樹形節點, 則進入紅黑樹數的取值流程, 并返回結果;
　　6. 進入鏈表的取值流程, 并返回結果;

　　當我們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）的樹結構來提升碰撞下的性能。

 19.HashMap的擴容操作是怎么實現的？

1. 在jdk1.8中，resize方法是在hashmap中的鍵值對大于閥值時或者初始化時，就調用resize方法進行擴容；
2. 每次擴展的時候，都是擴展2倍；
3. 擴展后Node對象的位置要么在原位置，要么移動到原偏移量兩倍的位置。

20.HashMap是怎么解決哈希沖突的？

什么是哈希？

　　Hash，一般翻譯為“散列”，也有直接音譯為“哈希”的， Hash就是指使用哈希算法是指把任意長度
的二進制映射為固定長度的較小的二進制值，這個較小的二進制值叫做哈希值。

什么是哈希沖突？

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

 

HashMap的數據結構

　　在Java中，保存數據有兩種比較簡單的數據結構：數組和鏈表。

• 數組的特點是：尋址容易，插入和刪除困難；
• 鏈表的特點是：尋址困難，但插入和刪除容易；

所以我們將數組和鏈表結合在一起，發揮兩者各自的優勢，就可以使用倆種方式：鏈地址法和開放地址法可以解決哈希沖突：

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

hash()函數

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

21.能否使用任何類作為 Map 的 key？

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

• 如果類重寫了 equals() 方法，也應該重寫 hashCode() 方法。
• 類的所有實例需要遵循與 equals() 和 hashCode() 相關的規則。
• 如果一個類沒有使用 equals()，不應該在 hashCode() 中使用它。

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

22.為什么HashMap中String、Integer這樣的包裝類適合作為K？

1. String、Integer等包裝類的特性能夠保證Hash值的不可更改性和計算準確性，能夠有效的減少Hash碰撞的幾率
2. 都是final類型，即不可變性，保證key的不可更改性，不會存在獲取hash值不同的情況
3. 內部已重寫了 equals() 、 hashCode() 等方法，遵守了HashMap內部的規范（不清楚可以去上面看看putValue的過程），不容易出現Hash值計算錯誤的情況；

23.如果使用Object作為HashMap的Key，應該怎么辦呢？

　　重寫 hashCode() 和 equals() 方法

24.HashMap為什么不直接使用hashCode()處理后的哈希值直接作為table的下標？

　　hashCode() 方法返回的是int整數類型，其范圍為-(2 ^ 31)~(2 ^ 31 - 1)，約有40億個映射空
間，而HashMap的容量范圍是在16（初始化默認值）~2 ^ 30，HashMap通常情況下是取不到最
大值的，并且設備上也難以提供這么多的存儲空間，從而導致通過 hashCode() 計算出的哈希值可
能不在數組大小范圍內，進而無法匹配存儲位置；

25.HashMap 的長度為什么是2的冪次方?

　　為了能讓 HashMap 存取高效，盡量較少碰撞，也就是要盡量把數據分配均勻，每個鏈表/紅黑樹
長度大致相同。這個實現就是把數據存到哪個鏈表/紅黑樹中的算法。
這個算法應該如何設計呢？
　　我們首先可能會想到采用%取余的操作來實現。但是，重點來了：“取余(%)操作中如果除數是
2的冪次則等價于與其除數減一的與(&)操作（也就是說 hash%length==hash&(length-1)的
前提是 length 是2的 n 次方；）。” 并且 采用二進制位操作 &，相對于%能夠提高運算效
率，這就解釋了 HashMap 的長度為什么是2的冪次方。
那為什么是兩次擾動呢？
　　答：這樣就是加大哈希值低位的隨機性，使得分布更均勻，從而提高對應數組存儲下標位置
的隨機性&均勻性，最終減少Hash沖突，兩次就夠了，已經達到了高位低位同時參與運算的目的；

26.HashMap 與 HashTable 有什么區別？

1. 線程安全： HashMap 是非線程安全的，HashTable 是線程安全的；HashTable 內部的方法基本都經過 synchronized 修飾。
2. 效率： 因為線程安全的問題，HashMap 要比 HashTable 效率高一點。另外，HashTable 基本被淘汰，不要在代碼中使用它；
3. 對Null key 和Null value的支持： HashMap 中，null 可以作為鍵，這樣的鍵只有一個，可以有一個或多個鍵所對應的值為 null。但是在 HashTable 中 put 進的鍵值只要有一個 null，直接拋NullPointerException。
4. 初始容量大小和每次擴充容量大小的不同 ：創建時如果不指定容量初始值，Hashtable 默認的初始大小為11，之后每次擴充，容量變為原來的2n+1。HashMap 默認的初始化大小為16。之后每次擴充，容量變為原來的2倍。
5. 底層數據結構： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間。Hashtable 沒有這樣的機制。

27.什么是TreeMap 

1. TreeMap 是一個有序的key-value集合，它是通過紅黑樹實現的。
2. TreeMap基于紅黑樹（Red-Black tree）實現。該映射根據其鍵的自然順序進行排序，或者根據創建映射時提供的 Comparator 進行排序，具體取決于使用的構造方法。
3. TreeMap是線程非同步的。

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

JDK1.7

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

• 在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式進行實現，結構如下：一個 ConcurrentHashMap 里包含一個 Segment 數組。

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

• 該類包含兩個靜態內部類 HashEntry 和 Segment ；前者用來封裝映射表的鍵值對，后者用來充當鎖的角色；

• Segment 是一種可重入的鎖 ReentrantLock，每個 Segment 守護一個HashEntry 數組里得元
  素，當對 HashEntry 數組的數據進行修改時，必須首先獲得對應的 Segment 鎖。
  

JDK1.8

• 在JDK1.8中，放棄了Segment臃腫的設計，取而代之的是采用Node + CAS + Synchronized來保證并發安全進行實現，synchronized只鎖定當前鏈表或紅黑二叉樹的首節點，
  這樣只要hash不沖突，就不會產生并發，效率又提升N倍。
  
  
• 如果相應位置的Node還沒有初始化，則調用CAS插入相應的數據；
• 如果相應位置的Node不為空，且當前該節點不處于移動狀態，則對該節點加synchronized鎖，如果該節點的hash不小于0，則遍歷鏈表更新節點或插入新節點；

• 如果該節點是TreeBin類型的節點，說明是紅黑樹結構，則通過putTreeVal方法往紅黑樹中插入節
  點；如果binCount不為0，說明put操作對數據產生了影響，如果當前鏈表的個數達到8個，則通
  過treeifyBin方法轉化為紅黑樹，如果oldVal不為空，說明是一次更新操作，沒有對元素個數產生
  影響，則直接返回舊值；

• 如果插入的是一個新節點，則執行addCount()方法嘗試更新元素個數baseCount；

29.TreeMap 和 TreeSet 在排序時如何比較元素？Collections 工具類中的 sort()方法如何比較元素？

• TreeSet 要求存放的對象所屬的類必須實現 Comparable 接口，該接口提供了比較元素的compareTo()方法，當插入元素時會回調該方法比較元素的大小。
• TreeMap 要求存放的鍵值對映射的鍵必須實現 Comparable 接口從而根據鍵對元素進 行排 序。

Collections 工具類的 sort 方法有兩種重載的形式，
第一種要求傳入的待排序容器中存放的對象比較實現 Comparable 接口以實現元素的比較；
comparable接口實際上是出自java.lang包，它有一個 compareTo(Object obj)方法用來排序
comparator接口實際上是出自 java.util 包，它有一個compare(Object obj1, Object obj2)方法用來排序
一般我們需要對一個集合使用自定義排序時，我們就要重寫compareTo方法或compare方法，當我們需要對某一個集合實現兩種排序方式，比如一個song對象中的歌名和歌手名分別采用一種排序方法的話，我們可以重寫compareTo方法和使用自制的Comparator方法或者以兩個Comparator來實現歌名排序和歌星名排序，第二種代表我們只能使用兩個參數版的Collections.sort().

30.Java集合1-集合與數組的區別