Java集合類常見面試知識點總結(jié)

Java集合類學(xué)習(xí)總結(jié)

這篇總結(jié)是基于之前博客內(nèi)容的一個整理和回顧。

這里先簡單地總結(jié)一下，更多詳細(xì)內(nèi)容請參考我的專欄：深入淺出Java核心技術(shù)?

https://blog.csdn.net/column/details/21930.html

里面有包括Java集合類在內(nèi)的眾多Java核心技術(shù)系列文章。

以下總結(jié)不保證全對，如有錯誤，還望能夠指出，謝謝。

最后，如果想要更好地完成這部分內(nèi)容的學(xué)習(xí)，建議大家還是去看一下原文。

Colletion，iterator，comparable

一般認(rèn)為Collection是最上層接口，但是hashmap實際上實現(xiàn)的是Map接口。iterator是迭代器，是實現(xiàn)iterable接口的類必須要提供的一個東西，能夠使用for(i : A) 這種方式實現(xiàn)的類型能提供迭代器，以前有一個enumeration，現(xiàn)在早棄用了。

List

List接口下的實現(xiàn)類有ArrayList，linkedlist，vector等等，一般就是用這兩個，用法不多說，老生常談。

ArrayList的擴(kuò)容方式是1.5倍擴(kuò)容，這樣擴(kuò)容避免2倍擴(kuò)容可能浪費空間，是一種折中的方案。 另外他不是線程安全，vector則是線程安全的，它是兩倍擴(kuò)容的。

linkedlist是雙鏈表，并且很坑的一點是，Java里的linkedlist自帶按索引訪問的api，結(jié)果我沒用過，面試的時候被問到答錯了，導(dǎo)致我美團(tuán)直接涼涼= =。

除此之外還有一個copyonwritelist，用于線程安全的場景。

Map

map永遠(yuǎn)都是重頭戲。

1 hashmap是數(shù)組和鏈表的組合結(jié)構(gòu)，數(shù)組是一個Entry數(shù)組，entry是k-V鍵值對類型，所以一個entry數(shù)組存著很entry節(jié)點，一個entry的位置通過key的hashcode方法，再進(jìn)行hash（移位等操作），最后與表長-1進(jìn)行相與操作，其實就是取hash值到的后n - 1位，n代表表長是2的n次方。

2 hashmap的默認(rèn)負(fù)載因子是0.75，閾值是16 * 0.75 = 12；初始長度為16；

3 hashmap的增刪改查方式比較簡單，都是遍歷，替換。有一點要注意的是key相等時，替換元素，不相等時連成鏈表。

4 除此之外，1.8jdk改進(jìn)了hashmap，當(dāng)鏈表上的元素個數(shù)超過8個時自動轉(zhuǎn)化成紅黑樹，節(jié)點變成樹節(jié)點，以提高搜索效率和插入效率到logn。

5 還有一點值得一提的是，hashmap的擴(kuò)容操作，由于hashmap非線程安全，擴(kuò)容時如果多線程并發(fā)進(jìn)行操作，則可能有兩個線程分別操作新表和舊表，導(dǎo)致節(jié)點成環(huán)，查詢時會形成死鎖。chm避免了這個問題。

6 另外，擴(kuò)容時會將舊表元素移到新表，原來的版本移動時會有rehash操作，每個節(jié)點都要rehash，非常不方便，而1.8改成另一種方式，對于同一個index下的鏈表元素，由于一個元素的hash值在擴(kuò)容后只有兩種情況，要么是hash值不變，要么是hash值變?yōu)樵瓉碇?2^n次方，這是因為表長翻倍，所以hash值取后n位，第一位要么是0要么是1，所以hash值也只有兩種情況。這兩種情況的元素分別加到兩個不同的鏈表。這兩個鏈表也只需要分別放到新表的兩個位置即可，是不是很酷。

7 最后有一個比較冷門的知識點，hashmap1.7版本鏈表使用的是節(jié)點的頭插法，擴(kuò)容時轉(zhuǎn)移鏈表仍然使用頭插法，這樣的結(jié)果就是擴(kuò)容后鏈表會倒置，而hashmap.1.8在插入時使用尾插法，擴(kuò)容時使用頭插法，這樣可以保證順序不變。

CHM

concurrenthashmap也稍微提一下把，chm1.7使用分段鎖來控制并發(fā)，每個segment對應(yīng)一個segmentmask，通過key的hash值相與這個segmentmask得到segment位置，然后在找到具體的entry數(shù)組下標(biāo)。

所以chm需要維護(hù)多個segment，每個segment對應(yīng)一段數(shù)組。分段鎖使用的是reetreetlock可重入鎖實現(xiàn)，查詢時不加鎖。

1.8則放棄使用分段鎖，改用cas+synchronized方式實現(xiàn)并發(fā)控制，查詢時不加鎖，插入時如果沒有沖突直接cas到成功為止，有沖突則使用synchronized插入。

Set

set就是hashmap將value固定為一個object，只存key元素，包裝成一個entry即可，其他不變。

Linkedhashmap

在原來hashmap基礎(chǔ)上將所有的節(jié)點依據(jù)插入的次序另外連成一個鏈表。用來保持順序，可以使用它實現(xiàn)lru緩存，當(dāng)訪問命中時將節(jié)點移到隊頭，當(dāng)插入元素超過長度時，刪除隊尾元素即可。

使用的時候先繼承l(wèi)inkedhashmap或者直接使用linkedhashmap作為成員變量，然后重寫removeEldestEntry方法即可，注意傳入size參數(shù)，判斷當(dāng)元素個數(shù)超過size時返回true，表示可以刪除就行了。

collections和Arrays工具類

兩個工具類分別操作集合和數(shù)組，可以進(jìn)行常用的排序，合并等操作。

comparable和comparator

實現(xiàn)comparable接口可以讓一個類的實例互相使用compareTo方法進(jìn)行比較大小，可以自定義比較規(guī)則，comparator則是一個通用的比較器，比較指定類型的兩個元素之間的大小關(guān)系。

這個東西還是很好用的，做算法題的時候經(jīng)常會用到自定義的排序方式。

treemap和treeset

主要是基于紅黑樹實現(xiàn)的兩個數(shù)據(jù)結(jié)構(gòu)，可以保證key序列是有序的，獲取sortedset就可以順序打印key值了。其中涉及到紅黑樹的插入和刪除，調(diào)整等操作，比較復(fù)雜，這里就不細(xì)說了。

另外我們也可以獲取逆序的set集合。

其他

集合類要學(xué)的東西其實還很多，但是面試的東西可能就這么多了把。當(dāng)然可能還有一些遺漏，但是大部分我在面試中能遇到的問題都已經(jīng)包含進(jìn)去了。