亚洲欧美日韩综合系列在线_91精品人妻一区二区_欧美大肥婆一级特大AA片_九色91视频免费观看_亚洲综合国产精品_av中文字幕在线不卡_久久精品色综合网_看黄色视频的软件_无卡无码高清中文字幕码2024_亚洲欧美日韩天堂网

本文是“最最最常見Java面試題總結(jié)”系列第三周的文章。
主要內(nèi)容：

1. Arraylist 與 LinkedList 異同

2. ArrayList 與 Vector 區(qū)別

3. HashMap的底層實現(xiàn)

4. HashMap 和 Hashtable 的區(qū)別

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

6. HashSet 和 HashMap 區(qū)別

7. ConcurrentHashMap 和 Hashtable 的區(qū)別

8. ConcurrentHashMap線程安全的具體實現(xiàn)方式/底層具體實現(xiàn)

9. 集合框架底層數(shù)據(jù)結(jié)構(gòu)總結(jié)

本文會同步更新在我開源的Java學習指南倉庫 Java-Guide (一份涵蓋大部分Java程序員所需要掌握的核心知識，正在一步一步慢慢完善，期待您的參與)中，地址：https://github.com/Snailclimb/Java-Guide,歡迎star、issue、pr。

Arraylist 與 LinkedList 異同

• 1. 是否保證線程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；

• 2. 底層數(shù)據(jù)結(jié)構(gòu)： Arraylist 底層使用的是Object數(shù)組；LinkedList 底層使用的是雙向循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)；

• 3. 插入和刪除是否受元素位置的影響： ① ArrayList 采用數(shù)組存儲，所以插入和刪除元素的時間復雜度受元素位置的影響。 比如：執(zhí)行add(E e) 方法的時候， ArrayList 會默認在將指定的元素追加到此列表的末尾，這種情況時間復雜度就是O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element) ）時間復雜度就為 O(n-i)。因為在進行上述操作的時候集合中第 i 和第 i 個元素之后的(n-i)個元素都要執(zhí)行向后位/向前移一位的操作。 ② LinkedList 采用鏈表存儲，所以插入，刪除元素時間復雜度不受元素位置的影響，都是近似 O（1）而數(shù)組為近似 O（n）。

• 4. 是否支持快速隨機訪問： LinkedList 不支持高效的隨機元素訪問，而ArrayList 實現(xiàn)了RandmoAccess 接口，所以有隨機訪問功能?？焖匐S機訪問就是通過元素的序號快速獲取元素對象(對應于get(int index) 方法)。

• 5. 內(nèi)存空間占用： ArrayList的空 間浪費主要體現(xiàn)在在list列表的結(jié)尾會預留一定的容量空間，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放直接后繼和直接前驅(qū)以及數(shù)據(jù)）。

補充：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之雙向鏈表

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。一般我們都構(gòu)造雙向循環(huán)鏈表，如下圖所示，同時下圖也是LinkedList 底層使用的是雙向循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)。

ArrayList 與 Vector 區(qū)別

Vector類的所有方法都是同步的?？梢杂蓛蓚€線程安全地訪問一個Vector對象、但是一個線程訪問Vector的話代碼要在同步操作上耗費大量的時間。

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

HashMap的底層實現(xiàn)

JDK1.8之前

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

所謂 “拉鏈法” 就是將鏈表和數(shù)組相結(jié)合。也就是說創(chuàng)建一個鏈表數(shù)組，數(shù)組中每一格就是一個鏈表。若遇到哈希沖突，則將沖突的值加到鏈表中即可。

JDK1.8之后

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

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

推薦閱讀：

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

HashMap 和 Hashtable 的區(qū)別

1. 線程是否安全： HashMap 是非線程安全的，HashTable 是線程安全的；HashTable 內(nèi)部的方法基本都經(jīng)過 synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧?。?；

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. 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間。Hashtable 沒有這樣的機制。

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

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

這個算法應該如何設(shè)計呢？

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

HashSet 和 HashMap 區(qū)別

ConcurrentHashMap 和 Hashtable 的區(qū)別

ConcurrentHashMap 和 Hashtable 的區(qū)別主要體現(xiàn)在實現(xiàn)線程安全的方式上不同。

• 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.7的 ConcurrentHashMap 底層采用 分段的數(shù)組+鏈表 實現(xiàn)，JDK1.8 采用的數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)一樣，數(shù)組+鏈表/紅黑二叉樹。Hashtable 和 JDK1.8 之前的 HashMap 的底層數(shù)據(jù)結(jié)構(gòu)類似都是采用 數(shù)組+鏈表 的形式，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的；

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

兩者的對比圖：

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

HashTable:

JDK1.7的ConcurrentHashMap：

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

ConcurrentHashMap線程安全的具體實現(xiàn)方式/底層具體實現(xiàn)

JDK1.7（上面有示意圖）

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

ConcurrentHashMap 是由 Segment 數(shù)組結(jié)構(gòu)和 HahEntry 數(shù)組結(jié)構(gòu)組成。

Segment 實現(xiàn)了 ReentrantLock,所以 Segment 是一種可重入鎖，扮演鎖的角色。HashEntry 用于存儲鍵值對數(shù)據(jù)。

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

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

JDK1.8 （上面有示意圖）

ConcurrentHashMap取消了Segment分段鎖，采用CAS和synchronized來保證并發(fā)安全。數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)類似，數(shù)組+鏈表/紅黑二叉樹。

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

集合框架底層數(shù)據(jù)結(jié)構(gòu)總結(jié)

Collection

1. List

• Arraylist： Object數(shù)組

• Vector： Object數(shù)組

• LinkedList： 雙向循環(huán)鏈表

2. Set

• HashSet（無序，唯一）: 基于 HashMap 實現(xiàn)的，底層采用 HashMap 來保存元素

• LinkedHashSet： LinkedHashSet 繼承與 HashSet，并且其內(nèi)部是通過 LinkedHashMap 來實現(xiàn)的。有點類似于我們之前說的LinkedHashMap 其內(nèi)部是基于 Hashmap 實現(xiàn)一樣，不過還是有一點點區(qū)別的。

• TreeSet（有序，唯一）： 紅黑樹(自平衡的排序二叉樹。)

Map

• HashMap： JDK1.8之前HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8以后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間

• LinkedHashMap: LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈式散列結(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結(jié)構(gòu)的基礎(chǔ)上，增加了一條雙向鏈表，使得上面的結(jié)構(gòu)可以保持鍵值對的插入順序。同時通過對鏈表進行相應的操作，實現(xiàn)了訪問順序相關(guān)邏輯。詳細可以查看：《LinkedHashMap 源碼詳細分析（JDK1.8）》

• HashTable: 數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的

• TreeMap: 紅黑樹（自平衡的排序二叉樹）

推薦閱讀：

• jdk1.8中ConcurrentHashMap的實現(xiàn)原理

• HashMap? ConcurrentHashMap? 相信看完這篇沒人能難住你！

• HASHMAP、HASHTABLE、CONCURRENTHASHMAP的原理與區(qū)別

• ConcurrentHashMap實現(xiàn)原理及源碼分析

• java-并發(fā)-ConcurrentHashMap高并發(fā)機制-jdk1.8