1.關(guān)于map
首先，map是用來存儲鍵值對（以前我一直有一個(gè)認(rèn)知誤區(qū)佑钾，數(shù)組里存的是key,然后value掛在key后面西疤，形成鏈表），所以map的基本單位是Entity,那么Entity是從哪兒來的呢休溶？
interface Entry<K,V>
這是map的內(nèi)部接口代赁，也就是說我們用的put(key,value)會被內(nèi)部封裝成一個(gè)Entity存儲。兽掰，至于為什么不能有重復(fù)的key是因?yàn)閔ashcode()算法芭碍。下面是map的常見實(shí)現(xiàn)類：
linkedHashMap:記錄了插入順序，在用Iterator遍歷LinkedHashMap時(shí)孽尽，先得到的記錄肯 定是先插入的窖壕，也可以在構(gòu)造時(shí)帶參數(shù)，按照訪問次序排序杉女。
TreeMap:TreeMap實(shí)現(xiàn)SortedMap接口瞻讽，能夠把它保存的記錄根據(jù)鍵排序，默認(rèn)是按鍵值的升序排序熏挎，也可以指定排序的比較器速勇，當(dāng)用Iterator遍歷TreeMap時(shí)，得到的記錄是排過序的坎拐。如果使用排序的映射烦磁，建議使用TreeMap。在使用TreeMap時(shí)廉白，key必須實(shí)現(xiàn)Comparable接口或者在構(gòu)造TreeMap傳入自定義的Comparator个初，否則會在運(yùn)行時(shí)拋出java.lang.ClassCastException類型的異常乖寒。
HashMap:它根據(jù)鍵的hashCode值存儲數(shù)據(jù)猴蹂，大多數(shù)情況下可以直接定位到它的值，因而具有很快的訪問速度楣嘁，但遍歷順序卻是不確定的磅轻。 HashMap最多只允許一條記錄的鍵為null珍逸，允許多條記錄的值為null。HashMap非線程安全聋溜，即任一時(shí)刻可以有多個(gè)線程同時(shí)寫HashMap谆膳，可能會導(dǎo)致數(shù)據(jù)的不一致。如果需要滿足線程安全撮躁，可以用 Collections的synchronizedMap方法使HashMap具有線程安全的能力漱病，或者使用ConcurrentHashMap。
上面這些話是從別的地方引用的把曼，相信大多數(shù)人和我一樣：看不懂，記不住嗤军，不過沒關(guān)系，我把他們的特點(diǎn)總結(jié)了：
- Treemap有序叙赚，hashmap快
- hashmap線程不安全，hashtable線程安全（不過它太low了震叮，下面我會解釋）
- hashmap的鍵，值都可以為null
上面三句話只要談到map基本是必問的苇瓣，答不出來基本上就可以涼涼了
2.關(guān)于Hashmap
hashmap的考察點(diǎn)很多，但是基本繞不開3個(gè)點(diǎn)钓简，插入，擴(kuò)容外邓，線程安全，
3.hashmap的插入你知道嘛损话？
我看過很多講解侦啸，這是從美團(tuán)的技術(shù)博客中拿下來的一張圖，可以說非常完美的解釋了hashmap的存儲丧枪，結(jié)合源碼光涂，來一步一步看(調(diào)用put方法其實(shí)就是調(diào)用putVal(),這個(gè)方法可以說是HashMap存儲的精髓)：
/**
* Implements Map.put and related methods.
*
* @param hash key的hash值
* @param key key的真實(shí)值
* @param value value的真實(shí)值
* @param onlyIfAbsent 如果為true,就不修改已經(jīng)存在的value(默認(rèn)為false)
* @param evict 如果是false,就創(chuàng)建table（默認(rèn)傳true）
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//1.tab為空則創(chuàng)建(也就是說在第一次調(diào)用put()的時(shí)候它才創(chuàng)建table)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2.根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i，如果table[i]==null拧烦，直接新建節(jié)點(diǎn)添加
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果不是那么就在table[i]后面掛的鏈表中找
else {
Node<K,V> e; K k;
//3.如果key存在忘闻，那么直接覆蓋value(在table中判斷)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 4.判斷該節(jié)點(diǎn)是鏈表還是紅黑樹
else if (p instanceof TreeNode)
//如果是紅黑樹是就調(diào)用putTreeVal()
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 5.如果是鏈表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//鏈表長度大于8轉(zhuǎn)換為紅黑樹進(jìn)行處理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已經(jīng)存在直接覆蓋value（在鏈表中判斷）
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 6.超過最大容量 就擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
總結(jié)：
hashmap的存主要分為6步：
- 判斷table是否為null
- 根據(jù)key的hash值看table中是否存在相同的hash值，如果有就在鏈表里找恋博，如果沒有就新建一個(gè)節(jié)點(diǎn)在table里
- 判斷table[i]的首個(gè)元素是否和key一樣齐佳，如果相同直接覆蓋value私恬，如果不一樣就遍歷鏈表，遍歷完鏈表以后執(zhí)行插入邏輯（jdk1.7以前使用頭插炼吴，jdk1.8使用尾插）
- 判斷該節(jié)點(diǎn)是紅黑樹還是鏈表本鸣，如果是紅黑樹跳轉(zhuǎn)至putTreeVal()處理，否則硅蹦，按鏈表處理
- 遍歷鏈表并記錄鏈表長度荣德，如果鏈表長度大于8,就樹化。
- 查看存在的鍵值對是否數(shù)量過多童芹，如果過多就擴(kuò)容
4.你了解hashmap的擴(kuò)容機(jī)制嘛命爬？
擴(kuò)容這個(gè)過程，我看網(wǎng)上很少有講擴(kuò)容源碼的辐脖，大部分是講擴(kuò)容的方法饲宛，這里總結(jié)一下擴(kuò)容的方法：
一個(gè)關(guān)于擴(kuò)容的小故事：
那時(shí)候我還在學(xué)C語言，給我講哈希的陳老師問我們：“hash有一個(gè)致命的缺點(diǎn)就是hash沖突嗜价，如果hash沖突過多了怎么辦艇抠？”
“擴(kuò)容”
”那么擴(kuò)容怎么擴(kuò)？“
“......”
"把所有的數(shù)據(jù)拿出來久锥，重新hash一遍"
“怎么會有這么煞筆的算法”
這段簡短的對話在后期解決了我的很多疑惑家淤。
hash擴(kuò)容的關(guān)鍵就是“怎么擴(kuò)”和“什么時(shí)候擴(kuò)”
-
關(guān)于“怎么擴(kuò)“
把hash的數(shù)據(jù)全部拿出來，重新hash一遍瑟由。
但是這個(gè)前提下我們可以優(yōu)化整個(gè)過程絮重，這里非常敬佩寫hashmap的大神，真的牛批歹苦，難怪都愛考1.8的hashmap青伤，這個(gè)hashmap的寫法是真的是相當(dāng)?shù)膬?yōu)秀，簡直讓人......(此處略卻10000字贊嘆只留下一句“臥槽”)殴瘦，跪舔結(jié)束狠角，來看下真正的王者編碼
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } 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); } 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) { 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; }
-
什么時(shí)候擴(kuò)屉凯？
hashmap擴(kuò)容是因?yàn)閔ash沖突過高，而hash沖突過高在HashMap中有一個(gè)默認(rèn)的負(fù)載因子（0.75）晓勇，當(dāng)數(shù)組的大小占到了總大小的0.75就會觸發(fā)擴(kuò)容機(jī)制宵蕉。在jdk1.8以后規(guī)定了hashmap的擴(kuò)容大小為每次擴(kuò)到一倍,也就是*2(具體為什么要擴(kuò)大兩倍节榜，是因?yàn)橐粋€(gè)非常巧妙地?cái)U(kuò)容算法，這里不多)稼稿。（這里的兩次循環(huán)可以證明让歼，擴(kuò)容機(jī)制是把所有的Entry都拿了出來重新的放了一遍）
總結(jié)：
在jdk1.7以前丽啡，hashmap的建造方式是：Entity+數(shù)組+鏈表，jdk1.8建造方式：Node+數(shù)組+紅黑樹
一個(gè)小問題：
為什么要用紅黑樹來替代鏈表改执？
首先如果鏈表的長度超過8了辈挂，就會被樹化裹粤。選用紅黑樹是因?yàn)榉治鲆幌滤母偁帉κ?/p>
- 二叉搜索樹遥诉，存在最壞情況，導(dǎo)致搜索效率變低
- AVL樹挫酿，需要滿足左右高度條件愕难，使得插入麻煩
- 中庸選擇紅黑樹猫缭，紅黑樹是低配的AVL樹
5.hashmap是線程安全的嘛？如果想要線程安全的hashmap怎么辦芝加？
hashmap是線程不安全的類藏杖，如果想要線程安全的可以使用hashtable,但是hashtable的key和value是不能為null的,還可以使用Collections工具類制造一個(gè)synchronizedHashMap接口，或者使用ConcurrentHashMap來獲得一個(gè)線程安全的hashmap点寥。hashmap線程不安全主要因?yàn)椋涸诓迦氲臅r(shí)候敢辩，如果不加鎖弟疆，兩個(gè)線程同時(shí)進(jìn)行擴(kuò)容的時(shí)候會形成一個(gè)環(huán)形鏈表，造成死鎖同廉，所以如果想要線程安全加鎖的話迫肖，就加在put方法上就好了帜羊。
6.concurrentHashMap了解過嘛？
了解過帐姻，concurrentHashMap是線程安全的HashMap類饥瓷，在jdk1.7以前它采用的是：segment分段鎖來保證線程安全的痹籍，在jdk1.8以后它采用CAS算法來保證線程安全(下一章講“線程鎖”會提到)。這里主要講segment棺克，segment的源碼如下
static class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
final float loadFactor;
Segment(float lf) { this.loadFactor = lf; }
}
首先segment是ReentratLock的實(shí)現(xiàn)類（下一章會講ReentratLock）娜谊。這里主要講一個(gè)過程：
- 先算出插入數(shù)據(jù)的hash值
- 根據(jù)此hash值計(jì)算出線程要拿的segment鎖
- 拿到鎖以后對鎖內(nèi)的數(shù)據(jù)進(jìn)行操作纱皆，用完釋放鎖
總結(jié)
線程安全實(shí)在是太重要了，所以下一節(jié)細(xì)講搀缠。其實(shí)考察的點(diǎn)也就三個(gè)：存儲結(jié)構(gòu)艺普，插入方式钳踊，線程安全勿侯，其中主要的變化是jdk1.7到j(luò)dk1.8的變化：
jdk1.7:數(shù)組+鏈表+segment
jdk1.8:數(shù)組+鏈表+紅黑樹+CAS
