今日招式：Java集合類面試題
Java集合類絕對(duì)是我們的老朋友了，Java技術(shù)江湖里，誰人不知，誰人不曉，它的使用率非常高，使用難度卻也不大，這也導(dǎo)致了很多人對(duì)它不屑一顧，殊不知其中卻暗藏玄機(jī)，今天我們不妨一起來破解一下Java集合類的面試題。
面試官常用招式：
只見面試官微微一笑，拔出長(zhǎng)劍，向你刺來，你趕緊拔劍相迎，幾招過后，你才意識(shí)到面試官使的都是虛招，只是試探你而已。
1.Java集合框架的基礎(chǔ)接口有哪些？
Collection為集合層級(jí)的根接口。一個(gè)集合代表一組對(duì)象，這些對(duì)象即為它的元素。Java平臺(tái)不提供這個(gè)接口任何直接的實(shí)現(xiàn)。
Set是一個(gè)不能包含重復(fù)元素的集合。這個(gè)接口對(duì)數(shù)學(xué)集合抽象進(jìn)行建模，被用來代表集合，就如一副牌。
List是一個(gè)有序集合，可以包含重復(fù)元素。你可以通過它的索引來訪問任何元素。List更像長(zhǎng)度動(dòng)態(tài)變換的數(shù)組。
Map是一個(gè)將key映射到value的對(duì)象.一個(gè)Map不能包含重復(fù)的key：每個(gè)key最多只能映射一個(gè)value。
一些其它的接口有Queue、Dequeue、SortedSet、SortedMap和ListIterator。
2.Iterater和ListIterator之間有什么區(qū)別？
（1）我們可以使用Iterator來遍歷Set和List集合，而ListIterator只能遍歷List。
（2）Iterator只可以向前遍歷，而LIstIterator可以雙向遍歷。
（3）ListIterator從Iterator接口繼承，然后添加了一些額外的功能，比如添加一個(gè)元素、替換一個(gè)元素、獲取前面或后面元素的索引位置。
3.遍歷一個(gè)List有哪些不同的方式？
List<String> strList = new ArrayList<>();
for(String obj : strList){? System.out.println(obj); }
Iterator<String> it = strList.iterator();
while(it.hasNext()){? String obj = it.next();? System.out.println(obj); }
使用迭代器更加線程安全，因?yàn)樗梢源_保，在當(dāng)前遍歷的集合元素被更改的時(shí)候，它會(huì)拋出ConcurrentModificationException。
4.在Java中，HashMap是如何工作的？
HashMap在Map.Entry靜態(tài)內(nèi)部類實(shí)現(xiàn)中存儲(chǔ)key-value對(duì)。HashMap使用哈希算法，在put和get方法中，它使用hashCode()和equals()方法。當(dāng)我們通過傳遞key-value對(duì)調(diào)用put方法的時(shí)候，HashMap使用Key hashCode()和哈希算法來找出存儲(chǔ)key-value對(duì)的索引。Entry存儲(chǔ)在LinkedList中，所以如果存在entry，它使用equals()方法來檢查傳遞的key是否已經(jīng)存在，如果存在，它會(huì)覆蓋value，如果不存在，它會(huì)創(chuàng)建一個(gè)新的entry然后保存。當(dāng)我們通過傳遞key調(diào)用get方法時(shí)，它再次使用hashCode()來找到數(shù)組中的索引，然后使用equals()方法找出正確的Entry，然后返回它的值。下面的圖片解釋了詳細(xì)內(nèi)容。
其它關(guān)于HashMap比較重要的問題是容量、負(fù)荷系數(shù)和閥值調(diào)整。HashMap默認(rèn)的初始容量是32，負(fù)荷系數(shù)是0.75。閥值是為負(fù)荷系數(shù)乘以容量，無論何時(shí)我們嘗試添加一個(gè)entry，如果map的大小比閥值大的時(shí)候，HashMap會(huì)對(duì)map的內(nèi)容進(jìn)行重新哈希，且使用更大的容量。容量總是2的冪，所以如果你知道你需要存儲(chǔ)大量的key-value對(duì)，比如緩存從數(shù)據(jù)庫(kù)里面拉取的數(shù)據(jù)，使用正確的容量和負(fù)荷系數(shù)對(duì)HashMap進(jìn)行初始化是個(gè)不錯(cuò)的做法。
5.hashCode()和equals()方法有何重要性？
HashMap使用Key對(duì)象的hashCode()和equals()方法去決定key-value對(duì)的索引。當(dāng)我們?cè)囍鴱腍ashMap中獲取值的時(shí)候，這些方法也會(huì)被用到。如果這些方法沒有被正確地實(shí)現(xiàn)，在這種情況下，兩個(gè)不同Key也許會(huì)產(chǎn)生相同的hashCode()和equals()輸出，HashMap將會(huì)認(rèn)為它們是相同的，然后覆蓋它們，而非把它們存儲(chǔ)到不同的地方。同樣的，所有不允許存儲(chǔ)重復(fù)數(shù)據(jù)的集合類都使用hashCode()和equals()去查找重復(fù)，所以正確實(shí)現(xiàn)它們非常重要。equals()和hashCode()的實(shí)現(xiàn)應(yīng)該遵循以下規(guī)則：
（1）如果o1.equals(o2)，那么o1.hashCode() == o2.hashCode()總是為true的。
（2）如果o1.hashCode() == o2.hashCode()，并不意味著o1.equals(o2)會(huì)為true。
6.我們能否使用任何類作為Map的key？
我們可以使用任何類作為Map的key，然而在使用它們之前，需要考慮以下幾點(diǎn)：
（1）如果類重寫了equals()方法，它也應(yīng)該重寫hashCode()方法。
（2）類的所有實(shí)例需要遵循與equals()和hashCode()相關(guān)的規(guī)則。請(qǐng)參考之前提到的這些規(guī)則。
（3）如果一個(gè)類沒有使用equals()，你不應(yīng)該在hashCode()中使用它。
（4）用戶自定義key類的最佳實(shí)踐是使之為不可變的，這樣，hashCode()值可以被緩存起來，擁有更好的性能。不可變的類也可以確保hashCode()和equals()在未來不會(huì)改變，這樣就會(huì)解決與可變相關(guān)的問題了。
比如，我有一個(gè)類MyKey，在HashMap中使用它。
//傳遞給MyKey的name參數(shù)被用于equals()和hashCode()中 MyKey key = new MyKey('Pankaj'); //assume hashCode=1234 myHashMap.put(key, 'Value'); // 以下的代碼會(huì)改變key的hashCode()和equals()值 key.setName('Amit'); //assume new hashCode=7890 //下面會(huì)返回null，因?yàn)镠ashMap會(huì)嘗試查找存儲(chǔ)同樣索引的key，而key已被改變了，匹配失敗，返回null myHashMap.get(new MyKey('Pankaj'));
那就是為何String和Integer被作為HashMap的key大量使用。
7.HashMap和HashTable有何不同？
（1）HashMap允許key和value為null，而HashTable不允許。
（2）HashTable是同步的，而HashMap不是。所以HashMap適合單線程環(huán)境，HashTable適合多線程環(huán)境。
（3）在Java1.4中引入了LinkedHashMap，HashMap的一個(gè)子類，假如你想要遍歷順序，你很容易從HashMap轉(zhuǎn)向LinkedHashMap，但是HashTable不是這樣的，它的順序是不可預(yù)知的。
（4）HashMap提供對(duì)key的Set進(jìn)行遍歷，因此它是fail-fast的，但HashTable提供對(duì)key的Enumeration進(jìn)行遍歷，它不支持fail-fast。
（5）HashTable被認(rèn)為是個(gè)遺留的類，如果你尋求在迭代的時(shí)候修改Map，你應(yīng)該使用CocurrentHashMap。
8.ArrayList和Vector有何異同點(diǎn)？
ArrayList和Vector在很多時(shí)候都很類似。
（1）兩者都是基于索引的，內(nèi)部由一個(gè)數(shù)組支持。
（2）兩者維護(hù)插入的順序，我們可以根據(jù)插入順序來獲取元素。
（3）ArrayList和Vector的迭代器實(shí)現(xiàn)都是fail-fast的。
（4）ArrayList和Vector兩者允許null值，也可以使用索引值對(duì)元素進(jìn)行隨機(jī)訪問。
以下是ArrayList和Vector的不同點(diǎn)。
（1）Vector是同步的，而ArrayList不是。然而，如果你尋求在迭代的時(shí)候?qū)α斜磉M(jìn)行改變，你應(yīng)該使用CopyOnWriteArrayList。
（2）ArrayList比Vector快，它因?yàn)橛型剑粫?huì)過載。
（3）ArrayList更加通用，因?yàn)槲覀兛梢允褂肅ollections工具類輕易地獲取同步列表和只讀列表。
9.Array和ArrayList有何區(qū)別？什么時(shí)候更適合用Array？
Array可以容納基本類型和對(duì)象，而ArrayList只能容納對(duì)象。
Array是指定大小的，而ArrayList大小是固定的。
Array沒有提供ArrayList那么多功能，比如addAll、removeAll和iterator等。盡管ArrayList明顯是更好的選擇，但也有些時(shí)候Array比較好用。
（1）如果列表的大小已經(jīng)指定，大部分情況下是存儲(chǔ)和遍歷它們。
（2）對(duì)于遍歷基本數(shù)據(jù)類型，盡管Collections使用自動(dòng)裝箱來減輕編碼任務(wù)，在指定大小的基本類型的列表上工作也會(huì)變得很慢。
（3）如果你要使用多維數(shù)組，使用[][]比List>更容易。
10.ArrayList和LinkedList有何區(qū)別？
ArrayList和LinkedList兩者都實(shí)現(xiàn)了List接口，但是它們之間有些不同。
（1）ArrayList是由Array所支持的基于一個(gè)索引的數(shù)據(jù)結(jié)構(gòu)，所以它提供對(duì)元素的隨機(jī)訪問，復(fù)雜度為O(1)，但LinkedList存儲(chǔ)一系列的節(jié)點(diǎn)數(shù)據(jù)，每個(gè)節(jié)點(diǎn)都與前一個(gè)和下一個(gè)節(jié)點(diǎn)相連接。所以，盡管有使用索引獲取元素的方法，內(nèi)部實(shí)現(xiàn)是從起始點(diǎn)開始遍歷，遍歷到索引的節(jié)點(diǎn)然后返回元素，時(shí)間復(fù)雜度為O(n)，比ArrayList要慢。
（2）與ArrayList相比，在LinkedList中插入、添加和刪除一個(gè)元素會(huì)更快，因?yàn)樵谝粋€(gè)元素被插入到中間的時(shí)候，不會(huì)涉及改變數(shù)組的大小，或更新索引。
（3）LinkedList比ArrayList消耗更多的內(nèi)存，因?yàn)長(zhǎng)inkedList中的每個(gè)節(jié)點(diǎn)存儲(chǔ)了前后節(jié)點(diǎn)的引用。
11.哪些集合類是線程安全的？
Vector、HashTable、Properties和Stack是同步類，所以它們是線程安全的，可以在多線程環(huán)境下使用。Java1.5并發(fā)API包括一些集合類，允許迭代時(shí)修改，因?yàn)樗鼈兌脊ぷ髟诩系目寺∩希运鼈冊(cè)诙嗑€程環(huán)境中是安全的。
12.Collections類是什么？
Java.util.Collections是一個(gè)工具類僅包含靜態(tài)方法，它們操作或返回集合。它包含操作集合的多態(tài)算法，返回一個(gè)由指定集合支持的新集合和其它一些內(nèi)容。這個(gè)類包含集合框架算法的方法，比如折半搜索、排序、混編和逆序等。
13.Comparable和Comparator接口有何區(qū)別？
Comparable和Comparator接口被用來對(duì)對(duì)象集合或者數(shù)組進(jìn)行排序。Comparable接口被用來提供對(duì)象的自然排序，我們可以使用它來提供基于單個(gè)邏輯的排序。
Comparator接口被用來提供不同的排序算法，我們可以選擇需要使用的Comparator來對(duì)給定的對(duì)象集合進(jìn)行排序。
14.我們?nèi)绾螌?duì)一組對(duì)象進(jìn)行排序？
如果我們需要對(duì)一個(gè)對(duì)象數(shù)組進(jìn)行排序，我們可以使用Arrays.sort()方法。如果我們需要排序一個(gè)對(duì)象列表，我們可以使用Collection.sort()方法。兩個(gè)類都有用于自然排序（使用Comparable）或基于標(biāo)準(zhǔn)的排序（使用Comparator）的重載方法sort()。Collections內(nèi)部使用數(shù)組排序方法，所有它們兩者都有相同的性能，只是Collections需要花時(shí)間將列表轉(zhuǎn)換為數(shù)組。
高手過招
面試官見你應(yīng)對(duì)自如，知道你也不是等閑之輩，于是眼神也變得專注起來，于是你們雙雙躍起，在空中展開廝斗，雖然面試官每一招都非常到位，但是你依然可以與之抗衡。
1、HashMap為什么不直接使用hashCode()處理后的哈希值直接作為table的下標(biāo)？
HashMap自己實(shí)現(xiàn)了自己的hash()方法，通過兩次擾動(dòng)使得它自己的哈希值高低位自行進(jìn)行異或運(yùn)算，降低哈希碰撞概率也使得數(shù)據(jù)分布更平均；
在保證數(shù)組長(zhǎng)度為2的冪次方的時(shí)候，使用hash()運(yùn)算之后的值與運(yùn)算（&）（數(shù)組長(zhǎng)度 - 1）來獲取數(shù)組下標(biāo)的方式進(jìn)行存儲(chǔ)，這樣一來是比取余操作更加有效率，二來也是因?yàn)橹挥挟?dāng)數(shù)組長(zhǎng)度為2的冪次方時(shí)，h&(length-1)才等價(jià)于h%length，三來解決了“哈希值與數(shù)組大小范圍不匹配”的問題；
2、為什么數(shù)組長(zhǎng)度要保證為2的冪次方呢？
只有當(dāng)數(shù)組長(zhǎng)度為2的冪次方時(shí)，h&(length-1)才等價(jià)于h%length，即實(shí)現(xiàn)了key的定位，2的冪次方也可以減少?zèng)_突次數(shù)，提高HashMap的查詢效率；
如果 length 為 2 的次冪 則 length-1 轉(zhuǎn)化為二進(jìn)制必定是 11111……的形式，在于 h 的二進(jìn)制與操作效率會(huì)非常的快，而且空間不浪費(fèi)；如果 length 不是 2 的次冪，比如 length 為 15，則 length - 1 為 14，對(duì)應(yīng)的二進(jìn)制為 1110，在于 h 與操作，最后一位都為 0 ，而 0001，0011，0101，1001，1011，0111，1101 這幾個(gè)位置永遠(yuǎn)都不能存放元素了，空間浪費(fèi)相當(dāng)大，更糟的是這種情況中，數(shù)組可以使用的位置比數(shù)組長(zhǎng)度小了很多，這意味著進(jìn)一步增加了碰撞的幾率，減慢了查詢的效率！這樣就會(huì)造成空間的浪費(fèi)。
3、HashMap的put方法的具體流程？
4、ConcurrentHashMap的具體實(shí)現(xiàn)知道嗎？
答：在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式進(jìn)行實(shí)現(xiàn)，結(jié)構(gòu)如下：
該類包含兩個(gè)靜態(tài)內(nèi)部類 HashEntry 和 Segment ；前者用來封裝映射表的鍵值對(duì)，后者用來充當(dāng)鎖的角色；
Segment 是一種可重入的鎖 ReentrantLock，每個(gè) Segment 守護(hù)一個(gè)HashEntry 數(shù)組里得元素，當(dāng)對(duì) HashEntry 數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)，必須首先獲得對(duì)應(yīng)的 Segment 鎖。
在JDK1.8中，放棄了Segment臃腫的設(shè)計(jì)，取而代之的是采用Node + CAS + Synchronized來保證并發(fā)安全進(jìn)行實(shí)現(xiàn)，結(jié)構(gòu)如下：
插入元素過程（建議去看看源碼）：
如果相應(yīng)位置的Node還沒有初始化，則調(diào)用CAS插入相應(yīng)的數(shù)據(jù)；
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
? ? if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
? ? ? ? break;? ? ? ? ? ? ? ? ? // no lock when adding to empty bin
}
如果相應(yīng)位置的Node不為空，且當(dāng)前該節(jié)點(diǎn)不處于移動(dòng)狀態(tài)，則對(duì)該節(jié)點(diǎn)加synchronized鎖，如果該節(jié)點(diǎn)的hash不小于0，則遍歷鏈表更新節(jié)點(diǎn)或插入新節(jié)點(diǎn)；
if (fh >= 0) {
? ? binCount = 1;
? ? for (Node<K,V> e = f;; ++binCount) {
? ? ? ? K ek;
? ? ? ? if (e.hash == hash &&
? ? ? ? ? ? ((ek = e.key) == key ||
? ? ? ? ? ? (ek != null && key.equals(ek)))) {
? ? ? ? ? ? oldVal = e.val;
? ? ? ? ? ? if (!onlyIfAbsent)
? ? ? ? ? ? ? ? e.val = value;
? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? Node<K,V> pred = e;
? ? ? ? if ((e = e.next) == null) {
? ? ? ? ? ? pred.next = new Node<K,V>(hash, key, value, null);
? ? ? ? ? ? break;
? ? ? ? }
? ? }
}
如果該節(jié)點(diǎn)是TreeBin類型的節(jié)點(diǎn)，說明是紅黑樹結(jié)構(gòu)，則通過putTreeVal方法往紅黑樹中插入節(jié)點(diǎn)；如果binCount不為0，說明put操作對(duì)數(shù)據(jù)產(chǎn)生了影響，如果當(dāng)前鏈表的個(gè)數(shù)達(dá)到8個(gè)，則通過treeifyBin方法轉(zhuǎn)化為紅黑樹，如果oldVal不為空，說明是一次更新操作，沒有對(duì)元素個(gè)數(shù)產(chǎn)生影響，則直接返回舊值；
如果插入的是一個(gè)新節(jié)點(diǎn)，則執(zhí)行addCount()方法嘗試更新元素個(gè)數(shù)baseCount；
5、HashMap的擴(kuò)容操作是怎么實(shí)現(xiàn)的？
答：通過分析源碼我們知道了HashMap通過resize()方法進(jìn)行擴(kuò)容或者初始化的操作，下面是對(duì)源碼進(jìn)行的一些簡(jiǎn)單分析：
/**
* 該函數(shù)有2中使用情況：1.初始化哈希表；2.當(dāng)前數(shù)組容量過小，需要擴(kuò)容
*/
final Node<K,V>[] resize() {
? ? Node<K,V>[] oldTab = table;// 擴(kuò)容前的數(shù)組（當(dāng)前數(shù)組）
? ? int oldCap = (oldTab == null) ? 0 : oldTab.length;// 擴(kuò)容前的數(shù)組容量（數(shù)組長(zhǎng)度）
? ? int oldThr = threshold;// 擴(kuò)容前數(shù)組的閾值
? ? int newCap, newThr = 0;
? ? if (oldCap > 0) {
? ? ? ? // 針對(duì)情況2：若擴(kuò)容前的數(shù)組容量超過最大值，則不再擴(kuò)容
? ? ? ? if (oldCap >= MAXIMUM_CAPACITY) {
? ? ? ? ? ? threshold = Integer.MAX_VALUE;
? ? ? ? ? ? return oldTab;
? ? ? ? }
? ? ? ? // 針對(duì)情況2：若沒有超過最大值，就擴(kuò)容為原來的2倍（左移1位）
? ? ? ? else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
? ? ? ? ? ? ? ? oldCap >= DEFAULT_INITIAL_CAPACITY)
? ? ? ? ? ? newThr = oldThr << 1; // double threshold
? ? }
? ? // 針對(duì)情況1：初始化哈希表（采用指定或者使用默認(rèn)值的方式）
? ? else if (oldThr > 0) // initial capacity was placed in threshold
? ? ? ? newCap = oldThr;
? ? else {? ? ? ? ? ? ? // zero initial threshold signifies using defaults
? ? ? ? newCap = DEFAULT_INITIAL_CAPACITY;
? ? ? ? newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
? ? }
? ? // 計(jì)算新的resize上限
? ? if (newThr == 0) {
? ? ? ? float ft = (float)newCap * loadFactor;
? ? ? ? newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
? ? ? ? ? ? ? ? (int)ft : Integer.MAX_VALUE);
? ? }
? ? threshold = newThr;
? ? @SuppressWarnings({"rawtypes","unchecked"})
? ? Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
? ? table = newTab;
? ? if (oldTab != null) {
? ? ? ? // 把每一個(gè)bucket都移動(dòng)到新的bucket中去
? ? ? ? for (int j = 0; j < oldCap; ++j) {
? ? ? ? ? ? Node<K,V> e;
? ? ? ? ? ? if ((e = oldTab[j]) != null) {
? ? ? ? ? ? ? ? oldTab[j] = null;
? ? ? ? ? ? ? ? if (e.next == null)
? ? ? ? ? ? ? ? ? ? newTab[e.hash & (newCap - 1)] = e;
? ? ? ? ? ? ? ? else if (e instanceof TreeNode)
? ? ? ? ? ? ? ? ? ? ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
? ? ? ? ? ? ? ? else { // preserve order
? ? ? ? ? ? ? ? ? ? Node<K,V> loHead = null, loTail = null;
? ? ? ? ? ? ? ? ? ? Node<K,V> hiHead = null, hiTail = null;
? ? ? ? ? ? ? ? ? ? Node<K,V> next;
? ? ? ? ? ? ? ? ? ? do {
? ? ? ? ? ? ? ? ? ? ? ? next = e.next;
? ? ? ? ? ? ? ? ? ? ? ? if ((e.hash & oldCap) == 0) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? if (loTail == null)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loHead = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail.next = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail = e;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? else {
? ? ? ? ? ? ? ? ? ? ? ? ? ? if (hiTail == null)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hiHead = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hiTail.next = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? hiTail = e;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? } while ((e = next) != null);
? ? ? ? ? ? ? ? ? ? if (loTail != null) {
? ? ? ? ? ? ? ? ? ? ? ? loTail.next = null;
? ? ? ? ? ? ? ? ? ? ? ? newTab[j] = loHead;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? if (hiTail != null) {
? ? ? ? ? ? ? ? ? ? ? ? hiTail.next = null;
? ? ? ? ? ? ? ? ? ? ? ? newTab[j + oldCap] = hiHead;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return newTab;
}
武學(xué)根基
雖然剛剛的打斗確實(shí)激烈，招式也十分好看，但是背后隱藏著的武學(xué)基礎(chǔ)卻是有共同之處的。在本篇里指的便是Java集合類的基礎(chǔ)知識(shí)點(diǎn)。
其實(shí)Java集合類的面試題遠(yuǎn)不止如此，面試官可能會(huì)問你每個(gè)實(shí)現(xiàn)細(xì)節(jié)，所以即使你見過了所有的面試題型，并且都牢牢記住，那又有什么用呢，不能理解其原理，光會(huì)表面招式，最后就會(huì)被輕易擊敗。
下面我們不妨就見招拆招，說Java集合類里的那些基礎(chǔ)、門道以及正確掌握這部分內(nèi)容的方法。
初來乍到
第一次接觸集合類，遇到的是ArrayList，當(dāng)時(shí)連<>代表泛型都不知道，讓我new一個(gè)ArrayList對(duì)象都不利索，直到開始了解到它的api，才感覺其實(shí)這個(gè)玩意也并不是很復(fù)雜呀，不就是put，get等一些看起來就很簡(jiǎn)單的方法嗎。
小試牛刀
抱著這樣的想法，我開始在一些項(xiàng)目和練習(xí)題中使用ArrayList，用法確實(shí)不難，正常情況我們只需要使用put，get，remove等方法，不過有時(shí)候也會(huì)遇到一些問題，比如你在用for循環(huán)刪除ArrayList的元素時(shí)，就會(huì)發(fā)現(xiàn)，如果你按照下標(biāo)來刪除，是會(huì)報(bào)錯(cuò)的，這就讓我很頭大了，不理解其實(shí)現(xiàn)原理，光會(huì)用api，看來還是不行啊。
漸入佳境
我一直認(rèn)為，面試是學(xué)習(xí)的一大動(dòng)力，當(dāng)時(shí)為了面試大廠，確實(shí)也看了很多面試題，集合類是跨不過去的一道坎，并且需要深入到源碼里去理解，比如hashmap的底層原理，絕對(duì)是大場(chǎng)面試中最愛考的一道題目，于是我跟著幾位大牛的博客（后面有推薦）復(fù)習(xí)了一整遍hashmap的實(shí)現(xiàn)原理，理解了80%左右的內(nèi)容，這才能夠應(yīng)付大廠的面試題。
學(xué)有所成
當(dāng)你理解了整個(gè)hashmap的實(shí)現(xiàn)原理之后，你就會(huì)發(fā)現(xiàn)大部分面試題都難不倒你了。我自己做了一個(gè)總結(jié)，每當(dāng)面試官問我“JDK里的hashmap是怎么實(shí)現(xiàn)的”我基本上都會(huì)用以下內(nèi)容做回答。
當(dāng)然，這僅供參考，切不可死記硬背，畢竟這只是我自己理解后整理出來的東西。
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次方。
hashmap的默認(rèn)負(fù)載因子是0.75，閾值是16 * 0.75 = 12；初始長(zhǎng)度為16；
hashmap的增刪改查方式比較簡(jiǎn)單，都是遍歷，替換。有一點(diǎn)要注意的是key相等時(shí)，替換元素，不相等時(shí)連成鏈表。
除此之外，1.8jdk改進(jìn)了hashmap，當(dāng)鏈表上的元素個(gè)數(shù)超過8個(gè)時(shí)自動(dòng)轉(zhuǎn)化成紅黑樹，節(jié)點(diǎn)變成樹節(jié)點(diǎn)，以提高搜索效率和插入效率到logn。
還有一點(diǎn)值得一提的是，hashmap的擴(kuò)容操作，由于hashmap非線程安全，擴(kuò)容時(shí)如果多線程并發(fā)進(jìn)行操作，則可能有兩個(gè)線程分別操作新表和舊表，導(dǎo)致節(jié)點(diǎn)成環(huán)，查詢時(shí)會(huì)形成死鎖。chm避免了這個(gè)問題。
另外，擴(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è)位置即可，是不是很酷。
最后有一個(gè)比較冷門的知識(shí)點(diǎn)，hashmap1.7版本鏈表使用的是節(jié)點(diǎn)的頭插法，擴(kuò)容時(shí)轉(zhuǎn)移鏈表仍然使用頭插法，這樣的結(jié)果就是擴(kuò)容后鏈表會(huì)倒置，而hashmap.1.8在插入時(shí)使用尾插法，擴(kuò)容時(shí)使用頭插法，這樣可以保證順序不變。
