這幾道Java集合框架面試題在面試中幾乎必問

  • 2019 年 10 月 6 日
  • 筆記

  1. Arraylist 與 LinkedList 異同
  2. ArrayList 與 Vector 區別
  3. HashMap的底層實現
  4. HashMap 和 Hashtable 的區別
  5. HashMap 的長度為什麼是2的冪次方
  6. HashSet 和 HashMap 區別
  7. ConcurrentHashMap 和 Hashtable 的區別
  8. ConcurrentHashMap執行緒安全的具體實現方式/底層具體實現
  9. 集合框架底層數據結構總結

Arraylist 與 LinkedList 異同

  • 1. 是否保證執行緒安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證執行緒安全；
  • 2. 底層數據結構： Arraylist 底層使用的是Object數組；LinkedList 底層使用的是雙向循環鏈表數據結構；
  • 3. 插入和刪除是否受元素位置的影響： ① ArrayList 採用數組存儲，所以插入和刪除元素的時間複雜度受元素位置的影響。 比如：執行 add(E e)方法的時候， ArrayList 會默認在將指定的元素追加到此列表的末尾，這種情況時間複雜度就是O(1)。但是如果要在指定位置 i 插入和刪除元素的話（ add(intindex,E element)）時間複雜度就為 O(n-i)。因為在進行上述操作的時候集合中第 i 和第 i 個元素之後的(n-i)個元素都要執行向後位/向前移一位的操作。 ②LinkedList 採用鏈表存儲，所以插入，刪除元素時間複雜度不受元素位置的影響，都是近似 O（1）而數組為近似 O（n）。
  • 4. 是否支援快速隨機訪問： LinkedList 不支援高效的隨機元素訪問，而ArrayList 實現了RandmoAccess 介面，所以有隨機訪問功能。快速隨機訪問就是通過元素的序號快速獲取元素對象(對應於 get(intindex)方法)。
  • 5. 記憶體空間佔用： ArrayList的空 間浪費主要體現在在list列表的結尾會預留一定的容量空間，而LinkedList的空間花費則體現在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放直接後繼和直接前驅以及數據）。

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

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。一般我們都構造雙向循環鏈表，如下圖所示，同時下圖也是LinkedList 底層使用的是雙向循環鏈表數據結構。

ArrayList 與 Vector 區別

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

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

HashMap的底層實現

JDK1.8之前

JDK1.8 之前 HashMap 由 數組+鏈表 組成的（「鏈表散列」 即數組和鏈表的結合體），數組是 HashMap 的主體，鏈表則是主要為了解決哈希衝突而存在的（HashMap 採用 「拉鏈法也就是鏈地址法」 解決衝突），如果定位到的數組位置不含鏈表（當前 entry 的 next 指向 null ）,那麼對於查找，添加等操作很快，僅需一次定址即可；如果定位到的數組包含鏈表，對於添加操作，其時間複雜度依然為 O(1)，因為最新的 Entry 會插入鏈表頭部，即需要簡單改變引用鏈即可，而對於查找操作來講，此時就需要遍歷鏈表，然後通過 key 對象的 equals 方法逐一比對查找.

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

JDK1.8之後

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

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

推薦閱讀：

  • 《Java 8系列之重新認識HashMap》 ：https://zhuanlan.zhihu.com/p/21673805

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 總是使用2的冪次方作為哈希表的大小,後面會介紹到為什麼是2的冪次方。
  5. 底層數據結構： JDK1.8 以後的 HashMap 在解決哈希衝突時有了較大的變化，當鏈表長度大於閾值（默認為8）時，將鏈錶轉化為紅黑樹，以減少搜索時間。Hashtable 沒有這樣的機制。

HashMap 的長度為什麼是2的冪次方

為了能讓 HashMap 存取高效，盡量較少碰撞，也就是要盡量把數據分配均勻，每個鏈表/紅黑樹長度大致相同。這個實現就是把數據存到哪個鏈表/紅黑樹中的演算法。

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

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

HashSet 和 HashMap 區別

ConcurrentHashMap 和 Hashtable 的區別

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

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

兩者的對比圖：

圖片來源：http://www.cnblogs.com/chengxiao/p/6842045.html

HashTable:

JDK1.7的ConcurrentHashMap：

JDK1.8的ConcurrentHashMap（TreeBin: 紅黑二叉樹節點；Node: 鏈表節點）：

ConcurrentHashMap執行緒安全的具體實現方式/底層具體實現

JDK1.7（上面有示意圖）

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

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

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

static class Segment<K,V> extends ReentrantLock implements Serializable {  }

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

JDK1.8 （上面有示意圖）

ConcurrentHashMap取消了Segment分段鎖，採用CAS和synchronized來保證並發安全。數據結構跟HashMap1.8的結構類似，數組+鏈表/紅黑二叉樹。

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

集合框架底層數據結構總結

Collection

1. List

  • Arraylist： Object數組
  • Vector： Object數組
  • LinkedList： 雙向循環鏈表

2. Set

  • HashSet（無序，唯一）: 基於 HashMap 實現的，底層採用 HashMap 來保存元素。HashMap底層數據結構見下。
  • LinkedHashSet： LinkedHashSet 繼承與 HashSet，並且其內部是通過 LinkedHashMap 來實現的。有點類似於我們之前說的LinkedHashMap 其內部是基於 Hashmap 實現一樣，不過還是有一點點區別的。
  • TreeSet（有序，唯一）： 紅黑樹(自平衡的排序二叉樹。)

Map

  • HashMap： JDK1.8之前HashMap由數組+鏈表組成的，數組是HashMap的主體，鏈表則是主要為了解決哈希衝突而存在的（「拉鏈法」解決衝突）.JDK1.8以後在解決哈希衝突時有了較大的變化，當鏈表長度大於閾值（默認為8）時，將鏈錶轉化為紅黑樹，以減少搜索時間
  • LinkedHashMap: LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基於拉鏈式散列結構即由數組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結構的基礎上，增加了一條雙向鏈表，使得上面的結構可以保持鍵值對的插入順序。同時通過對鏈表進行相應的操作，實現了訪問順序相關邏輯。詳細可以查看：《LinkedHashMap 源碼詳細分析（JDK1.8）》：https://www.imooc.com/article/22931
  • HashTable: 數組+鏈表組成的，數組是 HashMap 的主體，鏈表則是主要為了解決哈希衝突而存在的
  • TreeMap: 紅黑樹（自平衡的排序二叉樹）

相關閱讀：

  • jdk1.8中ConcurrentHashMap的實現原理：https://blog.csdn.net/fjse51/article/details/55260493
  • HashMap? ConcurrentHashMap? 相信看完這篇沒人能難住你！：https://crossoverjie.top/2018/07/23/java-senior/ConcurrentHashMap/
  • HASHMAP、HASHTABLE、CONCURRENTHASHMAP的原理與區別：http://www.yuanrengu.com/index.php/2017-01-17.html
  • ConcurrentHashMap實現原理及源碼分析：https://www.cnblogs.com/chengxiao/p/6842045.html
  • java-並發-ConcurrentHashMap高並發機制-jdk1.8：https://blog.csdn.net/jianghuxiaojin/article/details/52006118#commentBox

Tags:

VirMach 便宜 VPS