前言
學(xué)過數(shù)據(jù)結(jié)構(gòu)的讀者們想必其實(shí)也都學(xué)過HashMap耘拇，面試官問你的時(shí)候撵颊，想來你都是很清楚的知道HashMap是怎樣的一個(gè)構(gòu)成？確實(shí)很簡(jiǎn)單惫叛，就是數(shù)組加鏈表嘛倡勇。那再問你Hashtable和HashMap的區(qū)別是什么？腦子也不用想嘉涌，又能出來一個(gè)答案線程安全和線程不安全,Hashtable不允許存在空值唄妻熊。那繼續(xù)往深處問，HashMap是怎么做性能優(yōu)化的洛心？這個(gè)時(shí)候你是怎么樣的反應(yīng)呢固耘？如果知道紅黑樹，那就能答出來词身；不知道的話那不是就涼了厅目，因?yàn)檫@個(gè)時(shí)候連ConcurrentHashMap都需要放棄回答了！７ㄑ稀损敷！
思維導(dǎo)圖
HashMap源碼導(dǎo)讀
其實(shí)思路大致都是相同的，所以這里只分析一個(gè)HashMap深啤，先貼出他的幾個(gè)常見用法拗馒。
HashMap hashMap = new HashMap();
hashMap.put(key, value);
hashMap.get(key);
主要從這個(gè)方面對(duì)HashMap的整個(gè)工作流程進(jìn)行分析。
HashMap()
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 對(duì)數(shù)組的一個(gè)保護(hù)溯街，不能超過int最大值范圍
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
其實(shí)在無(wú)參構(gòu)造方法诱桂，我們并沒有看到所謂的數(shù)組的初始化，他只對(duì)我們的負(fù)載因子做了一個(gè)初始化呈昔，也就是我們一直常說的0.75f,但為什么是0.75f呢挥等，只能說是一個(gè)經(jīng)驗(yàn)值，也就是經(jīng)驗(yàn)所致堤尾，因?yàn)?strong>0.5f時(shí)空間太浪費(fèi)肝劲，1f時(shí)容易出現(xiàn)極端情況，當(dāng)然也不是隨便定的郭宝，設(shè)計(jì)師肯定是做了很多的測(cè)試的辞槐，但依舊是一個(gè)經(jīng)驗(yàn)值，或者說是測(cè)試后的最優(yōu)解粘室。
回到我們之前的問題榄檬，既然我們學(xué)習(xí)的時(shí)候?qū)W到過HashMap是一個(gè)數(shù)組+鏈表。那做第一個(gè)思考為什么初始化不見了衔统？ 先帶著這樣的問題繼續(xù)啊往下走鹿榜。
先看看自己動(dòng)手初始化容量構(gòu)造函數(shù)先朦，最后都會(huì)調(diào)用下方的tableSizeFor()方法。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
本質(zhì)意思就是把數(shù)值變成2的指數(shù)倍犬缨，這樣的好處是計(jì)算方便處理。但是出現(xiàn)同樣的問題棉浸，沒有初始化怀薛，這里也只看到了容量。問題繼續(xù)保留迷郑。
put(key, value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true); // 1
}
// 由注釋1直接調(diào)用的方法putVal()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, I;
// 第一次來判斷的時(shí)候枝恋，顯然的tab是一個(gè)空，因?yàn)樵跇?gòu)造函數(shù)中嗡害，我們并沒有看到他的初始化焚碌，那么必然要調(diào)用resize()方法。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; // 2霸妹，未能出事而必然調(diào)用的方法
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
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;
if (++size > threshold)
resize(); // 2
afterNodeInsertion(evict);
return null;
}
// 由注釋2直接調(diào)用的方法
// 由多種方法調(diào)用到這里：
// 1. 尚未初始化
// 2. 保存的數(shù)據(jù)超出 容量 * 負(fù)載因子
// 3. 數(shù)據(jù)被刪的不足以支持樹形的時(shí)候
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 十电。。叹螟。鹃骂。
// 此處對(duì)容量大小做了一系列的判定，為定義初始化容量為16
// 罢绽。畏线。。良价。
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 進(jìn)行了整個(gè)的table進(jìn)行一個(gè)初始化
// 而這個(gè)table就是一個(gè)Node的數(shù)組
// Node也就是鏈表的一個(gè)個(gè)節(jié)點(diǎn)寝殴，讀者自己點(diǎn)進(jìn)去觀察就能看到next節(jié)點(diǎn)
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 。明垢。蚣常。。袖外。
}
到這里我們就已經(jīng)明白了史隆，原來初始化的過程已經(jīng)在這里進(jìn)行了定義，這也就解決了我們的第一個(gè)問題了曼验。但是隨之而來第二個(gè)問題泌射，為什么要這樣設(shè)計(jì)呢？ 這里給出我思考的一個(gè)答案鬓照，如果只創(chuàng)建了熔酷，卻沒有進(jìn)行使用呢？那至少就會(huì)占去16個(gè)數(shù)據(jù)類型大小的內(nèi)存豺裆，而這樣的創(chuàng)建方法拒秘，就是對(duì)內(nèi)存的一種保護(hù)機(jī)制号显。
第三個(gè)問題，為什么要轉(zhuǎn)變成樹形（當(dāng)然它是有好聽的名字的躺酒，叫做紅黑樹）押蚤？ 其實(shí)結(jié)構(gòu)的轉(zhuǎn)換為的不外乎幾種原因效率問題、空間占用問題羹应。如果使用鏈表查詢揽碘，他的查詢速度是O(n) ，而紅黑樹的查詢速度是O(logn)园匹。但是紅黑樹帶來的問題確實(shí)一個(gè)存儲(chǔ)容量的問題雳刺，作為二叉樹，他需要同時(shí)保存左右節(jié)點(diǎn)裸违，而單鏈表只有一個(gè)節(jié)點(diǎn)掖桦，那么內(nèi)存消耗的問題就出來了。樹的構(gòu)造問題能講一篇博客供汛，所以就不再這里講先了枪汪。
get(key)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
通過hash值來尋找我們對(duì)應(yīng)的節(jié)點(diǎn)，那我們就需要先來看看這個(gè)hash是怎么計(jì)算的怔昨。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
答案也是一目了然的料饥，獲得hashCode()值，然后進(jìn)行于0000_0000_0000_0000b進(jìn)行異或運(yùn)算朱监。其實(shí)就是為了算出hashCode()的低16位岸啡。那我們獲得了hash值以后，就需要來找找我們的節(jié)點(diǎn)了赫编。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
// 對(duì)樹形中的數(shù)據(jù)進(jìn)行查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 對(duì)鏈表中的數(shù)據(jù)進(jìn)行查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
然后獲取到我們需要的數(shù)據(jù)巡蘸，然后就返還給我們了，哇哦＠匏汀悦荒！原來整體就夠就是這么簡(jiǎn)單的。（其實(shí)真正寫起來不簡(jiǎn)單嘹吨，分析起來簡(jiǎn)單一點(diǎn)罷了搬味，嘿嘿。）
HashMap和Hashtable有什么不同
既然我們已經(jīng)知道了整個(gè)的HashMap的構(gòu)成蟀拷，那主要要了解的對(duì)象就應(yīng)該是Hashtable了碰纬。那我們先來看看Hashtable的構(gòu)造函數(shù)好了。
// 無(wú)參構(gòu)造函數(shù)初始化问芬，處理容量為11悦析，負(fù)載因子為0，75
public Hashtable() {
this(11, 0.75f);
}
// 鏈表的創(chuàng)建在默認(rèn)最后嗲用的構(gòu)造函數(shù)中就已經(jīng)創(chuàng)建
// 那這里我們就發(fā)現(xiàn)了第一個(gè)不同的地方此衅。
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
文內(nèi)寫了第一個(gè)不同點(diǎn)强戴，但是還有一個(gè)不同點(diǎn)亭螟，你是否發(fā)現(xiàn)了？ 就是容量的問題骑歹，在HashMap中的容量計(jì)算全部都是往2的指數(shù)倍進(jìn)行靠近的预烙，但是Hashtable并沒有做出這樣的選擇，但是在負(fù)載因子上又出奇的一致道媚。
再看看Hashtable的put(key, value)方法默伍。
public synchronized V put(K key, V value) {
// 判空機(jī)制的存在，和HashMap并無(wú)判空衰琐，也就容許null作為key存在
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
我們常說Hashtable是一個(gè)線程安全的類，而這里也給了我們答案炼蹦，他在方法上加了synchronized羡宙，也就是鎖的機(jī)制，來完成我們的同步掐隐。但是思前想后狗热，我都存在一個(gè)疑惑，你們是否看到了他的resize()函數(shù)呢虑省？匿刮，沒錯(cuò)，并不存在resize()函數(shù)探颈。也就說明Hashtable并不會(huì)做擴(kuò)容的機(jī)制熟丸，那一旦發(fā)生極端情況，我們的就炸裂了伪节。
那我們繼續(xù)往下看看好了光羞，因?yàn)樵谶@個(gè)函數(shù)中還存在一個(gè)addEntry()方法，看看里面是不是有擴(kuò)容機(jī)制呢怀大。
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
原來他改頭換面了纱兑，在addEntry()方法中，我們發(fā)現(xiàn)他的重構(gòu)函數(shù)是一個(gè)叫做rehash()的函數(shù)化借。而擴(kuò)容機(jī)制和HashMap相同都是放大兩倍的操作來進(jìn)行完成的潜慎。但是從效率上來講，因?yàn)橐恢睌?shù)組+鏈表的形式存在蓖康，就算是沒有線程安全的機(jī)制铐炫，效率上來說總體還是比HashMap差勁的。
ConcurrentHashMap就線程安全的性能優(yōu)化
說到ConcurrentHashMap蒜焊，其實(shí)他和HashMap一樣都是存在JDK1.8前后的版本差異的驳遵。
網(wǎng)上可以查到很多關(guān)于version 1.8之前的機(jī)制，也就是分段鎖山涡，可以看做成多個(gè)Hashtable的組合堤结。而version 1.8之后的機(jī)制唆迁，就是鎖槽了。遲點(diǎn)做一個(gè)詳細(xì)的解析竞穷。
既然是性能優(yōu)化唐责，那么就應(yīng)該有性能優(yōu)化的點(diǎn)。
（1）和HashMap的實(shí)現(xiàn)方式一樣瘾带，數(shù)組+鏈表+紅黑樹鼠哥，查找性能上優(yōu)于Hashtable。前提： 使用的容量大于8看政。
（2）分段鎖機(jī)制 / 鎖槽機(jī)制：不再是整個(gè)數(shù)組加鎖朴恳，而是對(duì)單條或者幾條鏈表和紅黑樹進(jìn)行加鎖，也就同時(shí)能夠就收多個(gè)不同的hash操作了允蚣。
因?yàn)槲冶镜厥褂玫腏DK1.8于颖，所以我們就先研究一下JDK1.8的做法好了。
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
//嚷兔。森渐。。冒晰。同衣。
}
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 引入了CAS機(jī)制
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
//。壶运。耐齐。。蒋情。
else {
V oldVal = null;
synchronized (f) {
// 蚪缀。。恕出。询枚。。
}
//浙巫。金蜀。。的畴。渊抄。
}
}
addCount(1L, binCount);
return null;
}
需要關(guān)注的是加鎖對(duì)象synchronized (f)。對(duì)變量f代表就一個(gè)hash對(duì)應(yīng)的一條鏈表丧裁，而加鎖正好加的是這條鏈表护桦，或者這顆紅黑樹上，另外索引為空時(shí)通過CAS的方式來創(chuàng)建一個(gè)新的節(jié)點(diǎn)煎娇。這也就是JDK 1.8引入的新機(jī)制CAS+鎖二庵。
那我們?cè)倏纯碕DK 1.7的做法是什么樣的贪染，就直接用一張圖來直觀感受吧
version 1.7的時(shí)候根據(jù)Segment來給每一鏈配鎖，但是帶來的問題就是hash搜索時(shí)間變長(zhǎng)催享。不過相較于Hashtable而言杭隙，性能上還是更加出色的。因?yàn)榉侄捂i的機(jī)制也就不影響兩兩段之間并不會(huì)存在鎖的問題因妙，也就提高了性能痰憎。
而相較于version 1.8來說，性能確是不足的攀涵，首先是引入了紅黑樹的原因铣耘，第二Segment的維護(hù)其他相較于現(xiàn)在是一個(gè)比較麻煩的過程。而后者調(diào)整為單個(gè)Node進(jìn)行一個(gè)調(diào)整以故，需要進(jìn)行調(diào)整的范圍減小了蜗细，帶來了兩個(gè)好處，一是好管理据德，二是可同時(shí)操作的數(shù)量增加。
總結(jié)
其實(shí)總體來說就是性能上是HashMap > ConcurrentHashMap > Hashtable 跷车，考慮上線程安全以后ConcurrentHashMap > Hashtable 棘利。所以才會(huì)出現(xiàn)后來我們的ConcurrentHashMap出現(xiàn)來替代Hashtable。
以上就是我的學(xué)習(xí)成果朽缴，如果有什么我沒有思考到的地方或是文章內(nèi)存在錯(cuò)誤善玫，歡迎與我分享。
相關(guān)文章推薦：
