這篇總結(jié)是基于之前博客內(nèi)容的一個(gè)整理和回顧。
這里先簡(jiǎn)單地總結(jié)一下，更多詳細(xì)內(nèi)容請(qǐng)參考我的專欄：深入淺出Java核心技術(shù)?
https://blog.csdn.net/column/details/21930.html
里面有包括Java集合類在內(nèi)的眾多Java核心技術(shù)系列文章。
以下總結(jié)不保證全對(duì)，如有錯(cuò)誤，還望能夠指出，謝謝。
最后，如果想要更好地完成這部分內(nèi)容的學(xué)習(xí)，建議大家還是去看一下原文。
Colletion，iterator，comparable
一般認(rèn)為Collection是最上層接口，但是hashmap實(shí)際上實(shí)現(xiàn)的是Map接口。iterator是迭代器，是實(shí)現(xiàn)iterable接口的類必須要提供的一個(gè)東西，能夠使用for(i : A) 這種方式實(shí)現(xiàn)的類型能提供迭代器，以前有一個(gè)enumeration，現(xiàn)在早棄用了。
List接口下的實(shí)現(xiàn)類有ArrayList，linkedlist，vector等等，一般就是用這兩個(gè)，用法不多說，老生常談。
ArrayList的擴(kuò)容方式是1.5倍擴(kuò)容，這樣擴(kuò)容避免2倍擴(kuò)容可能浪費(fèi)空間，是一種折中的方案。 另外他不是線程安全，vector則是線程安全的，它是兩倍擴(kuò)容的。
linkedlist是雙鏈表，并且很坑的一點(diǎn)是，Java里的linkedlist自帶按索引訪問的api，結(jié)果我沒用過，面試的時(shí)候被問到答錯(cuò)了，導(dǎo)致我美團(tuán)直接涼涼= =。
除此之外還有一個(gè)copyonwritelist，用于線程安全的場(chǎng)景。
map永遠(yuǎn)都是重頭戲。
1 hashmap是數(shù)組和鏈表的組合結(jié)構(gòu)，數(shù)組是一個(gè)Entry數(shù)組，entry是k-V鍵值對(duì)類型，所以一個(gè)entry數(shù)組存著很entry節(jié)點(diǎn)，一個(gè)entry的位置通過key的hashcode方法，再進(jìn)行hash（移位等操作），最后與表長(zhǎng)-1進(jìn)行相與操作，其實(shí)就是取hash值到的后n - 1位，n代表表長(zhǎng)是2的n次方。
2 hashmap的默認(rèn)負(fù)載因子是0.75，閾值是16 * 0.75 = 12；初始長(zhǎng)度為16；
3 hashmap的增刪改查方式比較簡(jiǎn)單，都是遍歷，替換。有一點(diǎn)要注意的是key相等時(shí)，替換元素，不相等時(shí)連成鏈表。
4 除此之外，1.8jdk改進(jìn)了hashmap，當(dāng)鏈表上的元素個(gè)數(shù)超過8個(gè)時(shí)自動(dòng)轉(zhuǎn)化成紅黑樹，節(jié)點(diǎn)變成樹節(jié)點(diǎn)，以提高搜索效率和插入效率到logn。
5 還有一點(diǎn)值得一提的是，hashmap的擴(kuò)容操作，由于hashmap非線程安全，擴(kuò)容時(shí)如果多線程并發(fā)進(jìn)行操作，則可能有兩個(gè)線程分別操作新表和舊表，導(dǎo)致節(jié)點(diǎn)成環(huán)，查詢時(shí)會(huì)形成死鎖。chm避免了這個(gè)問題。
6 另外，擴(kuò)容時(shí)會(huì)將舊表元素移到新表，原來的版本移動(dòng)時(shí)會(huì)有rehash操作，每個(gè)節(jié)點(diǎn)都要rehash，非常不方便，而1.8改成另一種方式，對(duì)于同一個(gè)index下的鏈表元素，由于一個(gè)元素的hash值在擴(kuò)容后只有兩種情況，要么是hash值不變，要么是hash值變?yōu)樵瓉碇?2^n次方，這是因?yàn)楸黹L(zhǎng)翻倍，所以hash值取后n位，第一位要么是0要么是1，所以hash值也只有兩種情況。這兩種情況的元素分別加到兩個(gè)不同的鏈表。這兩個(gè)鏈表也只需要分別放到新表的兩個(gè)位置即可，是不是很酷。
7 最后有一個(gè)比較冷門的知識(shí)點(diǎn)，hashmap1.7版本鏈表使用的是節(jié)點(diǎn)的頭插法，擴(kuò)容時(shí)轉(zhuǎn)移鏈表仍然使用頭插法，這樣的結(jié)果就是擴(kuò)容后鏈表會(huì)倒置，而hashmap.1.8在插入時(shí)使用尾插法，擴(kuò)容時(shí)使用頭插法，這樣可以保證順序不變。
concurrenthashmap也稍微提一下把，chm1.7使用分段鎖來控制并發(fā)，每個(gè)segment對(duì)應(yīng)一個(gè)segmentmask，通過key的hash值相與這個(gè)segmentmask得到segment位置，然后在找到具體的entry數(shù)組下標(biāo)。
所以chm需要維護(hù)多個(gè)segment，每個(gè)segment對(duì)應(yīng)一段數(shù)組。分段鎖使用的是reetreetlock可重入鎖實(shí)現(xiàn)，查詢時(shí)不加鎖。
1.8則放棄使用分段鎖，改用cas+synchronized方式實(shí)現(xiàn)并發(fā)控制，查詢時(shí)不加鎖，插入時(shí)如果沒有沖突直接cas到成功為止，有沖突則使用synchronized插入。
set就是hashmap將value固定為一個(gè)object，只存key元素，包裝成一個(gè)entry即可，其他不變。
在原來hashmap基礎(chǔ)上將所有的節(jié)點(diǎn)依據(jù)插入的次序另外連成一個(gè)鏈表。用來保持順序，可以使用它實(shí)現(xiàn)lru緩存，當(dāng)訪問命中時(shí)將節(jié)點(diǎn)移到隊(duì)頭，當(dāng)插入元素超過長(zhǎng)度時(shí)，刪除隊(duì)尾元素即可。
使用的時(shí)候先繼承l(wèi)inkedhashmap或者直接使用linkedhashmap作為成員變量，然后重寫removeEldestEntry方法即可，注意傳入size參數(shù)，判斷當(dāng)元素個(gè)數(shù)超過size時(shí)返回true，表示可以刪除就行了。
兩個(gè)工具類分別操作集合和數(shù)組，可以進(jìn)行常用的排序，合并等操作。
實(shí)現(xiàn)comparable接口可以讓一個(gè)類的實(shí)例互相使用compareTo方法進(jìn)行比較大小，可以自定義比較規(guī)則，comparator則是一個(gè)通用的比較器，比較指定類型的兩個(gè)元素之間的大小關(guān)系。
這個(gè)東西還是很好用的，做算法題的時(shí)候經(jīng)常會(huì)用到自定義的排序方式。
主要是基于紅黑樹實(shí)現(xiàn)的兩個(gè)數(shù)據(jù)結(jié)構(gòu)，可以保證key序列是有序的，獲取sortedset就可以順序打印key值了。其中涉及到紅黑樹的插入和刪除，調(diào)整等操作，比較復(fù)雜，這里就不細(xì)說了。
另外我們也可以獲取逆序的set集合。
集合類要學(xué)的東西其實(shí)還很多，但是面試的東西可能就這么多了把。當(dāng)然可能還有一些遺漏，但是大部分我在面試中能遇到的問題都已經(jīng)包含進(jìn)去了。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
重慶分公司
重慶分公司
