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

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

• List：保證數(shù)據(jù)存放有序、可以存儲(chǔ)重復(fù)元素、可以通過(guò)下標(biāo)操作元素。
• Set：無(wú)序、不能存儲(chǔ)重復(fù)元素
• Map：使用鍵值對(duì)來(lái)存儲(chǔ)。Map會(huì)維護(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)來(lái)存儲(chǔ)數(shù)據(jù)，通過(guò)地址值的指向來(lái)維系節(jié)點(diǎn)，內(nèi)存不連續(xù)，不需要擴(kuò)容，增刪效率較高、查詢效率較低，線程不安全的集合。

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

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

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

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

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

• HashMap:
  1）底層基于數(shù)組+鏈表存儲(chǔ)數(shù)據(jù)
  2）不能重復(fù)且不能保證順序恒久不變
  3）允許存儲(chǔ)null鍵和null值
  4）默認(rèn)初始長(zhǎng)度為16，默認(rèn)加載因子為0.75，默認(rèn)的擴(kuò)容是在原來(lái)的基礎(chǔ)上增加一倍。
  5）當(dāng)給定初始容量時(shí)(2^n~2(n+1)),底層真實(shí)容量就是2^(n+1) 值（如果創(chuàng)建時(shí)給定了初始容量，底層將會(huì)將其擴(kuò)充為2的冪次方大?。?br> 6）異步式線程不安全的映射
  7)JDK1.8 以后的 HashMap 在解決哈希沖突時(shí)有了較?的變化，當(dāng)鏈表?度?于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅?樹(shù)，以減少搜索時(shí)間。Hashtable 沒(méi)有這樣的機(jī)制。
• Hashtable:
  1）最早的映射類
  2）鍵和值都不能為null
  3）默認(rèn)初始容量為11，默認(rèn)加載因子為0.75，默認(rèn)擴(kuò)容是在原來(lái)的基礎(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)把對(duì)象加入到HashSet中時(shí)，HashSet會(huì)先計(jì)算出對(duì)象的hashcode值，對(duì)哈希碼值進(jìn)行二次計(jì)算保證落在某個(gè)桶中，拿著新對(duì)象和對(duì)應(yīng)桶上的所有對(duì)象進(jìn)行equals比較，如果為true,就說(shuō)明對(duì)象有重復(fù)。

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

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

9.HashMap 的長(zhǎng)度為什么是2的冪次方

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

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

主要原因在于并發(fā)下的rehash會(huì)造成元素之間形成一個(gè)循環(huán)鏈表，不過(guò)，jdk1.8之后解決了這個(gè)問(wèn)題，但還是不建議在多線程下使用HashMap,因?yàn)槎嗑€程下使用HashMap還是會(huì)存在其他問(wèn)題，比如說(shuō)數(shù)據(jù)丟失。并發(fā)環(huán)境下推薦使用ConcurrentHashMap.
詳情請(qǐng)查看：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ù)組+鏈表/紅黑二叉樹(shù)。hashtable和jdk1.8之前的hashMap的底層數(shù)據(jù)結(jié)構(gòu)類似都是采用數(shù)組+鏈表的形式，數(shù)組時(shí)hashtable的主體，鏈表則是為了解決哈希沖突而存在的
• 實(shí)現(xiàn)線程安全的方式（重要）：
  1）在jdk1.7之前，ConcurrentHashMap（分段鎖）對(duì)整個(gè)桶數(shù)據(jù)進(jìn)行了分段分割，每一把鎖只鎖容器的一部分?jǐn)?shù)據(jù)，多線程訪問(wèn)容器里的不同數(shù)據(jù)段的數(shù)據(jù)，不會(huì)存在鎖競(jìng)爭(zhēng)，提高并發(fā)訪問(wèn)率。 到了 JDK1.8 的時(shí)候已經(jīng)摒棄了Segment的
  概念，而是直接用 Node 數(shù)組+鏈表+紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，并發(fā)控制使用 synchronized 和
  CAS 來(lái)操作。
  2）hashtable(同一把鎖)：使用synchronized 來(lái)保證線程安全，效率非常低下。當(dāng)?個(gè)線程訪問(wèn)同步方法時(shí)，其他線程也訪問(wèn)同步方法，可能會(huì)進(jìn)?阻塞或輪詢狀態(tài)，如使? put 添加元素，另?個(gè)線程不能使用 put 添加元素，也不能使? get，競(jìng)爭(zhēng)會(huì)越來(lái)越激烈效率越低。

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

見(jiàn)知識(shí)點(diǎn)11。

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

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