Java集合 - 簡書

本文很多知識點(diǎn)源自《JavaGuide ?試突擊版》结澄。

1.List赞辩、Set、Map的區(qū)別

List：保證數(shù)據(jù)存放有序猜谚、可以存儲重復(fù)元素败砂、可以通過下標(biāo)操作元素。
Set：無序魏铅、不能存儲重復(fù)元素
Map：使用鍵值對來存儲昌犹。Map會維護(hù)與key有關(guān)聯(lián)的值。鍵不能重復(fù)览芳，值可以重復(fù)斜姥。

2.ArrayList和LinkedList的區(qū)別？

ArrayList：底層是由數(shù)組實(shí)現(xiàn)，初始容量為10铸敏，底層是根據(jù)右移運(yùn)算進(jìn)行擴(kuò)容缚忧，每次擴(kuò)容是在原容量的基礎(chǔ)上增加一半，增刪效率較低搞坝、查詢效率較高搔谴，線程不安全的集合。
LinkedList：底層是基于基金二點(diǎn)來存儲數(shù)據(jù)桩撮，通過地址值的指向來維系節(jié)點(diǎn)敦第，內(nèi)存不連續(xù)，不需要擴(kuò)容店量，增刪效率較高芜果、查詢效率較低，線程不安全的集合融师。

3.ArrayList 與 Vector 區(qū)別呢?為什么要用Arraylist取代Vector呢右钾？

Vector是最早的集合類，底層基于數(shù)組實(shí)現(xiàn)存儲旱爆，默認(rèn)初始容量為10舀射，底層是根據(jù)三目運(yùn)算符進(jìn)行擴(kuò)容，如果增量大于0怀伦，每次擴(kuò)容的值就是增量的值脆烟，如果增量的值不大于0，每次擴(kuò)容的值就是原容量的值房待，是線程安全的集合邢羔。
由于Vector類的所有方法都是同步的，可以由兩個(gè)線程安全地訪問一個(gè)Vector對象桑孩，但是一個(gè)線程安全的訪問Vector的代碼在同步上將會耗費(fèi)大量時(shí)間拜鹤。
而ArrayList不是同步的，所以在不需要保證線程安全時(shí)建議使用ArrayList.

4.ArrayList的擴(kuò)容機(jī)制流椒。

擴(kuò)容調(diào)用的是grow()方法敏簿，根據(jù)右移運(yùn)算進(jìn)行擴(kuò)容，每次擴(kuò)容是在原容量的基礎(chǔ)上增加一半宣虾，之后通過grow()方法中調(diào)用的Arrays.copyof()方法進(jìn)行對原數(shù)組的復(fù)制惯裕。

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

HashMap:
1）底層基于數(shù)組+鏈表存儲數(shù)據(jù)
2）不能重復(fù)且不能保證順序恒久不變
3）允許存儲null鍵和null值
4）默認(rèn)初始長度為16，默認(rèn)加載因子為0.75安岂，默認(rèn)的擴(kuò)容是在原來的基礎(chǔ)上增加一倍。
5）當(dāng)給定初始容量時(shí)(2^n~2(n+1)),底層真實(shí)容量就是2^(n+1) 值（如果創(chuàng)建時(shí)給定了初始容量帆吻，底層將會將其擴(kuò)充為2的冪次方大杏蚰恰）
6）異步式線程不安全的映射
7)JDK1.8 以后的 HashMap 在解決哈希沖突時(shí)有了較?的變化，當(dāng)鏈表?度?于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅?樹次员，以減少搜索時(shí)間败许。Hashtable 沒有這樣的機(jī)制。
Hashtable:
1）最早的映射類
2）鍵和值都不能為null
3）默認(rèn)初始容量為11淑蔚，默認(rèn)加載因子為0.75市殷，默認(rèn)擴(kuò)容是在原來的基礎(chǔ)上增加一倍再加1
4）指定初始容量為多少底層真實(shí)的初始容量就為多少
5）同步式線程安全的映射

6.HashMap 和 HashSet區(qū)別

HashSet底層是基于HashMap實(shí)現(xiàn)的（除了 clone() 、writeObject() 刹衫、 readObject() 是HashSet 自己實(shí)現(xiàn)之外醋寝，其他方法都是直接調(diào)用 HashMap 中的方法。）

image.png

7.HashSet如何檢查重復(fù)带迟。

當(dāng)把對象加入到HashSet中時(shí)音羞，HashSet會先計(jì)算出對象的hashcode值，對哈希碼值進(jìn)行二次計(jì)算保證落在某個(gè)桶中仓犬，拿著新對象和對應(yīng)桶上的所有對象進(jìn)行equals比較嗅绰，如果為true,就說明對象有重復(fù)。

8.HashMap的底層實(shí)現(xiàn)

jdk1.8之前：
?HashMap底層是基于數(shù)組+鏈表實(shí)現(xiàn)的搀继。
?HashMap在進(jìn)行對象存儲時(shí)窘面，會先計(jì)算出對象的哈希碼值，對哈希碼值進(jìn)行二次計(jì)算保證對象能夠落在某個(gè)桶中叽躯，拿著新對象和對應(yīng)桶上所有對象進(jìn)行equals比較财边，如果為true(說明有重復(fù)對象)就舍棄新對象不存儲，如果全部比較完都是false則存在所有對象的最前面形成---鏈?zhǔn)綏＝Y(jié)構(gòu).
?擴(kuò)容機(jī)制：當(dāng)時(shí)用的桶數(shù)/總桶數(shù)大于加載因子（默認(rèn)0.75）進(jìn)行擴(kuò)容险毁，每次擴(kuò)容是在原來的基礎(chǔ)上增加一倍制圈。而在擴(kuò)容之后需要把已經(jīng)存儲元素對象重新進(jìn)行二次運(yùn)算，這個(gè)過程稱為rehash畔况。
在jdk1.8之后鲸鹦，在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長度大于閾值（默認(rèn)為8）時(shí)跷跪，將鏈表轉(zhuǎn)為紅黑樹馋嗜，以減少搜索時(shí)間。
TreeMap吵瞻、TreeSet以及JDK1.8之后的HashMap底層都用到了紅黑樹葛菇。紅黑樹就是為了解決?叉查找樹的缺陷，因?yàn)?叉查找樹在某些情況下會退化成?個(gè)線性結(jié)構(gòu)橡羞。

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

為了能夠讓HashMap存取高效眯停，盡量較少的碰撞，也就是要盡量把數(shù)據(jù)分配均勻卿泽。hash值的范圍-2147483648到2147483647莺债，前后加起來大概40億的映射空間，只要哈希函數(shù)映射得比較均勻松散，?般應(yīng)?是很難出現(xiàn)碰撞的齐邦。但是一個(gè)40億長度的數(shù)組椎侠，內(nèi)存是放不下的。所以需要?之前還要先做對數(shù)組的?度取模運(yùn)算措拇，得到的余數(shù)才能?來要存放的位置也就是對應(yīng)的數(shù)組下標(biāo)我纪。這個(gè)數(shù)組下標(biāo)的計(jì)算?法是“ (n - 1) & hash ”。（n代表數(shù)組?度）丐吓。這也就解釋了 HashMap 的?度為什么是2的冪次?浅悉。
這個(gè)算法應(yīng)該如何設(shè)計(jì)呢？
?我們?先可能會想到采?%取余的操作來實(shí)現(xiàn)汰蜘。但是仇冯，重點(diǎn)來了：“取余(%)操作中如果除數(shù)是2的冪次則等價(jià)于與其除數(shù)減?的與(&)操作（也就是說 hash%lengthdehash&(length-1)的前提是 length 是2的n 次?；）族操】良幔” 并且采用?進(jìn)制位操作 &，相對于%能夠提?運(yùn)算效率色难，這就解釋了 HashMap 的?度為什么是2的冪次方

10.HashMap 多線程操作導(dǎo)致死循環(huán)問題

主要原因在于并發(fā)下的rehash會造成元素之間形成一個(gè)循環(huán)鏈表泼舱，不過，jdk1.8之后解決了這個(gè)問題枷莉，但還是不建議在多線程下使用HashMap,因?yàn)槎嗑€程下使用HashMap還是會存在其他問題娇昙，比如說數(shù)據(jù)丟失。并發(fā)環(huán)境下推薦使用ConcurrentHashMap.
詳情請查看：https://coolshell.cn/articles/9606.html

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

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

底層數(shù)據(jù)結(jié)構(gòu)：jdk1.7的ConcurrentHashMap底層采用的數(shù)據(jù)結(jié)構(gòu)和hashMap1.8一樣冒掌，數(shù)組+鏈表/紅黑二叉樹。hashtable和jdk1.8之前的hashMap的底層數(shù)據(jù)結(jié)構(gòu)類似都是采用數(shù)組+鏈表的形式蹲盘，數(shù)組時(shí)hashtable的主體股毫，鏈表則是為了解決哈希沖突而存在的
實(shí)現(xiàn)線程安全的方式（重要）：
1）在jdk1.7之前，ConcurrentHashMap（分段鎖）對整個(gè)桶數(shù)據(jù)進(jìn)行了分段分割召衔，每一把鎖只鎖容器的一部分?jǐn)?shù)據(jù)铃诬，多線程訪問容器里的不同數(shù)據(jù)段的數(shù)據(jù)，不會存在鎖競爭苍凛，提高并發(fā)訪問率趣席。到了 JDK1.8 的時(shí)候已經(jīng)摒棄了Segment的
概念，而是直接用 Node 數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)醇蝴，并發(fā)控制使用 synchronized 和
CAS 來操作宣肚。
2）hashtable(同一把鎖)：使用synchronized 來保證線程安全，效率非常低下悠栓。當(dāng)?個(gè)線程訪問同步方法時(shí)霉涨，其他線程也訪問同步方法弧呐，可能會進(jìn)?阻塞或輪詢狀態(tài)，如使? put 添加元素嵌纲，另?個(gè)線程不能使用 put 添加元素，也不能使? get腥沽，競爭會越來越激烈效率越低逮走。

12. ConcurrentHashMap線程安全的具體實(shí)現(xiàn)?式/底層具體實(shí)現(xiàn).

見知識點(diǎn)11。

13.comparable和Comparator的區(qū)別

comparable接口實(shí)際上來自java.lang包今阳，他有一個(gè)compareTo(Object obj)方法來排序
Comparator接口上出自java.util包师溅，他有一個(gè)compare(Object obj1,Object obj2)方法用來排序。
一般需要對一個(gè)集合使用自定義排序時(shí)盾舌，我們重寫compareTo()方法或compare()方法墓臭；當(dāng)我們需要對某一個(gè)集合實(shí)現(xiàn)兩種排序方式，比如?個(gè)song對象中的歌名和歌手名分別采用?種排序方
法的話妖谴，我們可以重寫 compareTo() ?法和使?自制的Comparator?法或者以兩個(gè)Comparator來實(shí)現(xiàn)歌名排序和歌星名排序窿锉。