前言
文章非常長,建議加入喜歡或收藏分多次看
首先放上來自美團(tuán)文章的Map的類繼承圖
我們本章介紹的是使用最頻繁的HashMap(基于JDK8),首先HashMap (綜合了數(shù)組+鏈表的優(yōu)點) , 我們都知道常用的數(shù)據(jù)結(jié)構(gòu)有數(shù)組,鏈表... 兩者都有各自的優(yōu)缺點 .
- 數(shù)組查詢快,增刪慢(因為要移位),而且需要一片連續(xù)的存儲空間
- 鏈表查詢慢(遍歷),增刪快,而且不需要一片連續(xù)的存儲空間
所以綜上,為了追求一種更完美的數(shù)據(jù)結(jié)構(gòu),或者是查詢也快,增刪也快,所以就有了Hash算法,Hash算法是根據(jù)某種Hash算法計算出Key,然后存儲,查詢的時候根據(jù)計算出的Key直接尋址到Value,更像是字典,但是如果Key沖突了怎么辦呢?就像是字典里開頭為A的有很多,常用的處理方式有兩種:
- 開放地址法
- 鏈地址法
HashMap采用的是第二種,采用數(shù)組+鏈表(+JDK8紅黑樹)的方式結(jié)合了數(shù)組和鏈表的優(yōu)點,接下來大體介紹下HashMap
HashMap有一個數(shù)組也就是桶,當(dāng)調(diào)用put之后先通過hash值計算出index找到數(shù)組上的位置,然后存儲,如果還沒有數(shù)據(jù)或者數(shù)組上的位置就是要存儲的數(shù)據(jù)就直接設(shè)置value,要不就是遍歷鏈表找到存儲的位置存儲,要不就是紅黑樹.下面會逐步詳細(xì)介紹
目錄
1. Hash算法
2. 延遲初始化
3. put
4. get
5. resize
6. 樹化
1. Hash算法
一個優(yōu)秀的Hash表就要盡可能的避免Hash沖突,當(dāng)然解決方式有很多種,比如加大數(shù)組的大小,或者一個散列很好的Hash算法,綜合時間和空間選擇一個合適的數(shù)組大小,然后加上一個很好的Hash算法就是JDK8中的做法.
//hash
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//index
static int indexFor(int h, int length) { //jdk1.7的源碼，jdk1.8沒有這個方法，但是實現(xiàn)原理一樣的
return h & (length-1); //第三步 取模運算
}
一: hash計算
首先Java的hashCode散列特別好,基本不會重復(fù),但是由于初始化數(shù)組長度只有16,所以實際上只有低位參與了index的計算,再看上面的hash方法,拿hashCode 與 hashCode右移16位做異或,這樣使得高位與低位做了摻雜使得低位更不容易產(chǎn)生沖突,而且開銷不大.
二: index計算
傳統(tǒng)的計算index的方法是計算出的hash值與數(shù)組的長度length做 % 運算,映射到數(shù)組的index上,但是計算機(jī)對 % 運算實際上比 & 運算開銷要大,那為什么還能通過 & 運算計算呢? 因為我們知道為什么HashMap的初始大小一定是2的整次冪 , 當(dāng)n為2的整次冪的時候取余就可以轉(zhuǎn)化為 : h % n ==> h & (n - 1),所以上面是通過 & 運算計算index,也是為了提升速度.
這里延伸一個: 如何判斷一個數(shù)是不是2的冪次方 假設(shè)數(shù)字為n 那么可以通過 n & (n - 1) == 0 來判斷
三: 數(shù)組大小的選擇
當(dāng)然一般常規(guī)的做法是Hash數(shù)組長度都設(shè)計為質(zhì)數(shù) , 因為質(zhì)數(shù)的沖突幾率會小于合數(shù) 詳見: 為什么一般hashtable的桶數(shù)會取一個素數(shù), JDK8還要選擇合數(shù)而且是2的冪次方的原因有幾點: 1. 取模上優(yōu)化（計算機(jī)擅長移位和或與操作） 2. resize時候優(yōu)化 , 當(dāng)然為了減少沖突對hash值的計算做了優(yōu)化，3，申請2的冪次方可以減少內(nèi)存的碎片化 , 所以總體來說是優(yōu)于質(zhì)數(shù)的.
2.延遲初始化
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
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);
}
第一個空構(gòu)造函數(shù)只是將負(fù)載因子初始化為0.75,至于為什么是0.75,Java也是經(jīng)過了大量的測試最后得出0.75比較合適
第二個構(gòu)造函數(shù)調(diào)用了第三個構(gòu)造函數(shù)
第三個構(gòu)造函數(shù): 前幾行參數(shù)校驗,然后將用戶設(shè)置的loadFactor賦值,然后threshold賦值,下面看一下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;
}
cap是用戶輸入的容量,然后調(diào)用tableSizeFor返回一個2的冪次方的數(shù),這里很重要,如果不設(shè)置大小,默認(rèn)為16 (2的4次冪) , 所以要將用戶輸入的數(shù)字轉(zhuǎn)換為2的冪次方, 一般我們會使用遞歸或遍歷實現(xiàn),Java的實現(xiàn)很厲害.
原理: (首先2的多少次冪的二進(jìn)制肯定是這種形式 (1000 0000) 高位是1后面全是0 )
首先cap - 1 是因為有可能用戶輸入的正好是2的冪次方,先-1,然后右移, 首先將數(shù)轉(zhuǎn)為2進(jìn)制,高位肯定是有一個1 (ex: 0001 0000 xxxx) , 先右移一位,然后在和原值或以下,這樣高位右邊一位也變成了1,這樣就有兩個連續(xù)的 1,然后同樣再右移2位,在和右移前或以下, 這樣就有連續(xù)的4個1,然后再一次右移4 , 8 , 16 這樣高位之后全變?yōu)榱?, 然后加1這樣就變?yōu)榱烁呶贿M(jìn)一位為1,后面全是0
如下圖解: (以6為例 )
有人可能會有個疑惑,那么假設(shè)我們傳入的cap很大呢? 經(jīng)過上面的計算能不能轉(zhuǎn)換為正確的數(shù)字呢? 有時候右移會變?yōu)樨?fù)數(shù)怎么處理呢?
源碼中可以看到上限為 static final int MAXIMUM_CAPACITY = 1 << 30 也就是2的30次冪 , 我們上面右移了31位所以肯定可以得到正確的數(shù) , 右移如果產(chǎn)生負(fù)數(shù),源碼也有一個小于0的判斷 如下:
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;
//這里判斷了n如果小于0 返回1
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
再回到標(biāo)題: 延遲初始化 , 可以看到HashMap并沒有在構(gòu)造函數(shù)里為HashMap做初始化操作,只是做了一些賦值操作,其實Java是把初始化放到了第一次插入數(shù)據(jù)的時候, 源碼如下:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//第一次插入數(shù)據(jù),table為null,所以會調(diào)用resize
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
...
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
可以看出當(dāng)?shù)谝淮蝡ut數(shù)據(jù),會調(diào)用到putVal,然后table就是我們的數(shù)組,會滿足==null,進(jìn)入resize,然后會在resize里面進(jìn)行初始化,具體resize操作會在后面resize的詳解里.
那么Java為什么要這么做呢?
我想可能是第一不在初始化的時候申請table數(shù)組的空間,加快速度 第二減少不必要的空間浪費,因為很多map可能一直不會put數(shù)據(jù),或者很久之后才會put數(shù)據(jù) , 第三 大多數(shù)map都是一起初始化的,減少同時初始化造成的大片內(nèi)存的分配
3. put
public V put(K key, V value) {
//首先還是計算hash
return putVal(hash(key), key, value, false, true);
}
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. 判斷table數(shù)組是不是空 或者 長度為0,如果為空則調(diào)用resize方法進(jìn)行初始化(也就是延遲初始化)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通過(hash&n-1)計算index,然后找到相應(yīng)的位置的值看下是否為空,如果為空就放到該位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {// 走到這里只有三種情況: 1): 數(shù)組節(jié)點的判斷 2): 鏈表的遍歷 3): 樹的遍歷
Node<K,V> e; K k;
// 判斷是不是數(shù)組的節(jié)點,如果是賦值給e,然后通過下面的代碼替換為新的值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果節(jié)點為TreeNode,就通過紅黑樹的方式將值插入或替換舊值
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // else為鏈表的遍歷
// for循環(huán)為無限循環(huán),由內(nèi)部跳出循環(huán)
for (int binCount = 0; ; ++binCount) {
// 找到鏈表的最后一個位置發(fā)現(xiàn)都沒有,則放到鏈表的最后一個節(jié)點上,然后判斷binCount是不是大于TREEIFY_THRESHOLD,否則鏈表樹化,變?yōu)榧t黑樹(Java8的優(yōu)化)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果找到一樣的,通過下面的代碼進(jìn)行舊值的替換
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;
// 插入數(shù)據(jù)要看一下當(dāng)前數(shù)目和負(fù)載的數(shù)目做比較,如果超過負(fù)載要進(jìn)行resize擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
詳見圖解:
4. get
public V get(Object key) {
Node<K,V> e;
// 首先通過hash計算index 然后調(diào)用getNode方法
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 首先判斷數(shù)組不為空,長度大于0,通過index定位到數(shù)組的第一個節(jié)點不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判斷第一個節(jié)點和key的比較,如果一致就返回第一個節(jié)點
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 判斷next不為空
if ((e = first.next) != null) {
// 如果是紅黑樹,那么通過調(diào)用樹的getNode方法獲取節(jié)點
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 這里就是鏈表的遍歷,如果有則返回
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
5. resize擴(kuò)容機(jī)制
Java的HashMap內(nèi)部有一個擴(kuò)容因子,默認(rèn)為0.75,也就是如果HashMap的size超過了容量x0.75,就要進(jìn)行擴(kuò)容,擴(kuò)大數(shù)組的容量,然后減少Hash沖突.
與Java7的擴(kuò)容區(qū)別: Java7(數(shù)組+鏈表)進(jìn)行擴(kuò)容的時候是reHash(重新計算Hash和Index)來移動到新的數(shù)組上,鏈表會倒置, Java8(數(shù)組+鏈表+紅黑樹)進(jìn)行擴(kuò)容,不需要reHash,原因后面會講到,然后依次將數(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;
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) { // 這里是擴(kuò)容的操作
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;
}
1. resize的一部分是用來延遲初始化HashMap的table
延遲初始化很簡單就是通過默認(rèn)的大小,計算一個容量,然后初始化一個數(shù)組,這里就不講了
2. 擴(kuò)容
主要介紹下:
1.為什么不需要rehash
首先我們知道HashMap數(shù)組的大小一定是2的冪次方,然后擴(kuò)容是2倍,所以依舊是2的冪次方,下面我們舉個例子:
假設(shè)默認(rèn)大小為16,擴(kuò)容之后大小為32,看一下index的變化:
建議點擊查看原圖
由圖上可以看出,在擴(kuò)容后index要么就是不變,要么就是舊index+舊容量,不需要重新計算index , 只需要判斷高位為0和1就可以了,這就是Java8相對Java7的優(yōu)化,可見Doug Lea(J.U.C包基本出自他之手,有很多文章和論文的發(fā)表,有興趣可以去看一下)的算法功底十分深厚
可以看下美團(tuán)技術(shù)文章的圖片:
2. 如何擴(kuò)容
擴(kuò)容后對值的移動主要如下:
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果只有數(shù)組節(jié)點,next為空那么直接計算index放到新的數(shù)組上即可
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果節(jié)點為TreeNode那么說明已經(jīng)樹化了,直接調(diào)用TreeNode的split進(jìn)行移動
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 這里主要介紹鏈表的移動,相對于Java7也有改動,寫的十分精煉
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;
}
}
}
}
}
這里主要介紹鏈表的處理:
我們拿到鏈表的節(jié)點,肯定只有兩種情況,一種是原index,另一種是原index+原大小,所以分別對這兩種進(jìn)行處理:
文字不太好描述,我們圖解一下吧
由于圖片較大,點擊查看原圖
6. 樹化
當(dāng)我們在put數(shù)據(jù)的時候,如果鏈表上節(jié)點的個數(shù)大于等于TREEIFY_THRESHOLD (static final int TREEIFY_THRESHOLD = 8),這時候會由鏈表樹化變?yōu)榧t黑樹,這就是Java8的優(yōu)化,其實還有一個條件,就是tab數(shù)組的個數(shù)需要大于等于MIN_TREEIFY_CAPACITY (static final int MIN_TREEIFY_CAPACITY = 64),直接看代碼吧
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//...省略部分代碼
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;
}
//...
p = e;
}
}
//... 省略部分代碼
}
}
//...
return null;
}
可以看到,當(dāng)調(diào)用putVal插入數(shù)據(jù)的時候,遍歷鏈表的節(jié)點,會通過binCount記錄節(jié)點的index, ( for (int binCount = 0; ; ++binCount) 這個for循環(huán)也是相當(dāng)個性,其實是個無限循環(huán)),再回到正題,當(dāng)遍歷節(jié)點如果遍歷到 if ((e = p.next) == null) 這個條件也就是最后一個了,那就應(yīng)該把節(jié)點放到最后一個節(jié)點的next的位置上,然后看一下鏈表節(jié)點的個數(shù),如果大于等于TREEIFY_THRESHOLD,就調(diào)用treeifyBin方法.
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 這里會判斷tab數(shù)組的個數(shù),如果小于MIN_TREEIFY_CAPACITY,其實并沒有樹化,而是擴(kuò)容
// 原因其實也很簡單,如果數(shù)組很小的話,改為紅黑樹提升也不大,反而會因為樹化和紅黑樹的調(diào)整增加插入的時間
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {//這里就是樹化的過程
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
紅黑樹是數(shù)據(jù)結(jié)構(gòu)中比較重要的數(shù)據(jù)結(jié)構(gòu),當(dāng)然也是樹結(jié)構(gòu)中比較簡單的數(shù)據(jù)結(jié)構(gòu),如果想了解紅黑樹,可以看一下我的這篇文章
圖片詳解紅黑樹(R-B Tree) 一種簡單而高效的數(shù)據(jù)結(jié)構(gòu) Java版
我自己畫了很多圖去詳解紅黑樹,可以看一下
參考:
- JDK1.7&JDK1.8 源碼。
- 博客園 : 數(shù)據(jù)結(jié)構(gòu)：哈希表以及哈希沖突的解決方案
- 美團(tuán)技術(shù)團(tuán)隊: Java 8系列之重新認(rèn)識HashMap
如有錯誤,請評論指正,萬分感謝!
