HashMap原理
1.HashMap存儲(chǔ)結(jié)構(gòu)
從結(jié)構(gòu)來講，HashMap是有數(shù)組，鏈表，紅黑樹(jdk1.8之后加入)實(shí)現(xiàn)的，如下圖所示
image
引入紅黑樹是因?yàn)樗檎?，插入，刪除的平均時(shí)間復(fù)雜度為O(log(n))。這是因?yàn)楫?dāng)產(chǎn)生hash碰撞的時(shí)候，數(shù)據(jù)會(huì)掛載(尾插)，形成鏈表，鏈表空間上不連續(xù)，邏輯上連續(xù)，增刪元素塊，只需要采用節(jié)點(diǎn)間引用，時(shí)間復(fù)雜度為O(1),查詢慢，需要遍歷查找，時(shí)間復(fù)雜度為O(n);
2.源碼分析
2.1構(gòu)造方法
// initialCapacity 初始容量 默認(rèn)16
// loadFactor 加載因子 默認(rèn) 0.75
// threshold 閾值 = initialCapacity*loadFactor
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);
}
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);
}
HashMap構(gòu)造方法一共重載了四個(gè)，其中初始化三個(gè)參數(shù)
- initialCapacity:初始容量，默認(rèn)為16，HashMap底層由數(shù)組+鏈表(或紅黑樹)實(shí)現(xiàn)，但是還是從數(shù)組開始，所以當(dāng)儲(chǔ)存的數(shù)據(jù)越來越多時(shí)，就必須進(jìn)行擴(kuò)容操作，如果在知道需要存儲(chǔ)數(shù)據(jù)大小的情況下，指定初始容量可以避免不必要的擴(kuò)容操作，提升效率。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
- loadFactor:加載因子(默認(rèn)0.75)，當(dāng)負(fù)載因子較大的時(shí)，去給table數(shù)組擴(kuò)容的可能性會(huì)少，所以相對(duì)占用內(nèi)存就會(huì)較少(空間上較少)，但是每條entry鏈上的元素相對(duì)較多，查詢的時(shí)間就會(huì)增長(zhǎng)(時(shí)間上較多)。反之就是，負(fù)載因子較小的時(shí)候，給table數(shù)組擴(kuò)容的可能性就會(huì)變大，那么占用內(nèi)存空間就會(huì)較大，但是entry鏈上的元素就會(huì)較少，查詢的時(shí)間也會(huì)減少。所以才有了負(fù)載因子是時(shí)間和空間上一種折中的說法。所以設(shè)置負(fù)載因子的時(shí)候要考慮自己追求的事時(shí)間上的少還是空間上的少(一般情況下不需要設(shè)置，系統(tǒng)給定的默認(rèn)值就是比較合適了)。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
-
threshold :閾值，hashMap所能容納最大鍵值對(duì)的數(shù)量，如果超過則需要擴(kuò)容，計(jì)算方式
,構(gòu)造方法中通過#tableSizeFor(initiaCapacity)方法進(jìn)行了賦值，主要原因是在構(gòu)造方法中，數(shù)組table并沒有進(jìn)行初始化，而是在put方法中進(jìn)行初始化的，同時(shí)在put方法中也會(huì)對(duì)threshold進(jìn)行重新賦值。
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 找到大于或等于cap的最小2的冪
* 不考慮最大容量的情況下，返回cap且最近接2的整數(shù)次冪
*/
static final int tableSizeFor(int cap) {
int n = cap - 1; // 防止cap已經(jīng)是2的整數(shù)次冪
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;
}
image
2.2put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int TREEIFY_THRESHOLD = 8;
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ù)組是否已經(jīng)初始化
if ((tab = table) == null || (n = tab.length) == 0)
// 如果此時(shí)table尚未初始化，則此處進(jìn)行初始化數(shù)組，并賦值初始容量，重新計(jì)算閾值，默認(rèn)長(zhǎng)度為16
n = (tab = resize()).length;
// (n - 1) & hash 確定元素存在哪個(gè)桶中
if ((p = tab[i = (n - 1) & hash]) == null)
// 通過hash找到下標(biāo)，如果hash置頂?shù)奈恢脼榭?，則直接將該數(shù)據(jù)存放進(jìn)去
tab[i] = newNode(hash, key, value, null);
// 若數(shù)組中已經(jīng)存在元素，發(fā)生碰撞
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果需要插入的key與當(dāng)前hash值指定下標(biāo)的key一樣，現(xiàn)將第一個(gè)元素p賦值給e
e = p;
// 如果節(jié)點(diǎn)為紅黑樹節(jié)點(diǎn)
else if (p instanceof TreeNode)
// 放入到樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 其余情況則為鏈表節(jié)點(diǎn)
else {
// 遍歷當(dāng)前鏈表，在鏈表的最末端插入節(jié)點(diǎn)（jdk1.7采用頭插法，容易造成死循環(huán)）
for (int binCount = 0; ; ++binCount) {
// p.next 為空則代表鏈表尾端
if ((e = p.next) == null) {
// 在鏈表尾部插入節(jié)點(diǎn)
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD 擴(kuò)容閾值8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 如果達(dá)到閾值，則轉(zhuǎn)為紅黑樹
treeifyBin(tab, hash);
// 跳出循環(huán)
break;
}
// 判斷鏈表中元素的key與插入元素key值是否想的
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
// 如果相等，掉出循環(huán)
break;
// 遍歷桶中的列表，與前面e = p.next 組合，可以遍歷鏈表
p = e;
}
}
// 如果e有記錄，則表示桶中找到與元素key值，hash值與插入元素相等的節(jié)點(diǎn)，說明上面的值以及存在于當(dāng)前的hashmap中，更新指定指定 // 鍵值對(duì)
if (e != null) { // existing mapping for key
// 記錄e的value
V oldValue = e.value;
// onlyIfAbsent true 不改變已經(jīng)存在的值
// onlyIfAbsent false
if (!onlyIfAbsent || oldValue == null)
// onlyIfAbsent 為false，或者新插入的value為空，用新值替換舊值
e.value = value;
// 回調(diào)，將元素插入到鏈表的最后
afterNodeAccess(e);
// 返回舊值
// map.put("haha","hehe");
// map.put("haha","heiheihei");
// return hehe
return oldValue;
}
}
// 記錄內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)
++modCount;
// 每當(dāng)put一個(gè)元素，當(dāng)實(shí)際大小，小于大于閾值的時(shí)候，進(jìn)行擴(kuò)容
if (++size > threshold)
// 擴(kuò)容
resize();
// 插入后回調(diào)
afterNodeInsertion(evict);
return null;
}
具體過程如下圖
image
2.3resize方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// table 已經(jīng)初始化，且容量>0
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// 如果舊的容量已經(jīng)達(dá)到最大值2^30，則不再擴(kuò)容，閾值直接設(shè)置為最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果舊數(shù)組*2小于最大容量2^30 并且 舊數(shù)組的常量大于等于初始容量16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 閾值擴(kuò)容的大小為當(dāng)前的2倍
newThr = oldThr << 1; // double threshold
}
// 舊閾值>0,
// 說明使用的構(gòu)造方法為HashMap(int initialCapity,int loadFactory)，該方法中，
// this.threshold=tableSizeFor(initialCapity),返回的容量為2的n次冪
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 閾值為初始化0，oldCap為空，及創(chuàng)建數(shù)組是為無參構(gòu)造方法，調(diào)用resize()初始化默認(rèn)值，
// 將新的初始化長(zhǎng)度設(shè)置為16，閾值設(shè)置為16*0.75=12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的閾值為0，根據(jù)負(fù)載因子設(shè)置初始化的值
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"})
// 創(chuàng)建一個(gè)長(zhǎng)度為newCap的Node數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果就的數(shù)組中有數(shù)據(jù)，則將數(shù)組中的值復(fù)制到新的數(shù)組中
if (oldTab != null) {
// 遍歷舊的數(shù)組，將元素節(jié)點(diǎn)進(jìn)行復(fù)制
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 如果指定下標(biāo)有數(shù)據(jù)，
if ((e = oldTab[j]) != null) {
//1.將指定下標(biāo)數(shù)據(jù)置空，
oldTab[j] = null;
// 2.指定下標(biāo)只有一個(gè)元素
if (e.next == null)
// 重新計(jì)算hash值，確定元素的位置
newTab[e.hash & (newCap - 1)] = e;
// 紅黑樹 treenode數(shù)據(jù)結(jié)構(gòu)
else if (e instanceof TreeNode)
//
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 鏈表數(shù)據(jù)結(jié)構(gòu)
else { // preserve order
// 如果是鏈表，重新計(jì)算hash值，根據(jù)下標(biāo)重新分組
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 如果hash值為0，元素在數(shù)組中的位置未發(fā)生改變
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 不為0，元素在擴(kuò)容數(shù)組中的位置發(fā)生改變，新的下標(biāo)為原索引+oldCap
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.先判斷當(dāng)前table是否進(jìn)行過初始化，如果沒有，此處解決了調(diào)用無參構(gòu)造器的時(shí)候，threshold和initialCapacity初始值的問題，如果已經(jīng)初始化了，則擴(kuò)容為原來的2倍
2.擴(kuò)容后對(duì)新的table，并對(duì)所有的數(shù)據(jù)進(jìn)行遍歷
- 如果新計(jì)算的位置為空，則直接插入
- 如果新計(jì)算的位置未鏈表，則通過hash算法重新計(jì)算下標(biāo)，對(duì)鏈表進(jìn)行分組。
- 如果是紅黑樹，則需要進(jìn)行重新拆分操作。
2.4get方法
public V get(Object key) {
Node<K,V> e;
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;
// 1.根據(jù)hash算法找出對(duì)應(yīng)位置的第一個(gè)數(shù)據(jù)，如果key相等，則直接返回
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) {
// 如果該節(jié)點(diǎn)為樹節(jié)點(diǎn)，則通過數(shù)查找
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;
}
說明
- 根據(jù)hash值找到對(duì)應(yīng)的數(shù)據(jù)的位置;
- 判斷第一個(gè)節(jié)點(diǎn)的key是否為需要查詢的key，如果是直接返回，如果不是繼續(xù)查找第二個(gè)節(jié)點(diǎn);
- 如果數(shù)據(jù)是TreeNode(紅黑樹節(jié)點(diǎn))，直接紅黑樹節(jié)點(diǎn)查找數(shù)據(jù);
- 如果是鏈表結(jié)構(gòu)，直接遍歷所有節(jié)點(diǎn)，返回?cái)?shù)據(jù);
- 如果沒有找到符合要求的，直接返回null。
2.4.1 hash方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
說明:這段代碼叫做擾動(dòng)函數(shù)，也是HashMap中的hash運(yùn)算。
- key.hashcode()，獲取key的hashcode值，如果不進(jìn)行重寫返回的就是根據(jù)內(nèi)存地址得到一個(gè)int值
- 獲取到的hashcode值無符號(hào)右移16位然后與原h(huán)ashcode進(jìn)行 ^ 運(yùn)算，這樣做的目的就是讓高位與低位進(jìn)行混合，讓兩者都參與運(yùn)算，一遍hash值分布更均勻。
2.4.2 取模運(yùn)算 (n-1) & hash
hash算法中為了使元素分布的更加均勻，很多都會(huì)使用取謀運(yùn)算，在HashMap中并沒有hash%n這樣的取謀運(yùn)算，而是使用(n-1) & hash代替，原因是因?yàn)樵谟?jì)算機(jī)中，&的效率遠(yuǎn)高于%，需要注意的是，只有容量在2的n次冪的情況下，(n-1)&hash才等效于hash%n,這也是為什么hashmap在初始容量的時(shí)候，不管傳入什么值，都會(huì)執(zhí)行tableSizeFor(int cap)的方法轉(zhuǎn)換成2的n次冪的原因。
3.總結(jié)
- HashMap底層結(jié)構(gòu)在1.7之前是數(shù)組+鏈表組成的，1.8之后加入了紅黑樹；鏈表的長(zhǎng)度小于8的時(shí)候，發(fā)生hash沖突的時(shí)候會(huì)增加鏈表的長(zhǎng)度，當(dāng)鏈表長(zhǎng)度大于8的時(shí)候，會(huì)先判斷數(shù)組的容量，如果容量小于64則先擴(kuò)容(原因是數(shù)組長(zhǎng)度越小，越容易發(fā)生碰撞，因此當(dāng)容量小的時(shí)候，首先考慮的是擴(kuò)容),如果容量大于64，則將鏈表轉(zhuǎn)換為紅黑樹，提升效率。
- hashmap的容量為2的n次冪，無論在初始化的時(shí)候傳入的容量的值為多少，都會(huì)轉(zhuǎn)換為2的n次冪，這樣做的原因是為了在取模運(yùn)算的時(shí)候可以用&而不是用%，可以極大的提升效率，同時(shí)也降低了hash沖突。
- HashMap是非線程安全的，在多線程的情況下會(huì)存在異常(如形成閉環(huán))，1.8的時(shí)候已修復(fù)閉環(huán)問題，但仍是線程非現(xiàn)場(chǎng)安全的?？梢允褂胔ashtable和ConcurrentHashMap代替。
4.問題
1.為什么主數(shù)組的長(zhǎng)度要為2的n次冪，如何保證？
為了讓HashMap存儲(chǔ)高效，盡量減少碰撞，也就是盡量的把數(shù)據(jù)分配均勻，每個(gè)鏈表/紅黑樹長(zhǎng)度大致相同。這個(gè)實(shí)現(xiàn)就是把數(shù)據(jù)存到哪個(gè)鏈表/紅黑樹中的算法。
首先想到的是hash%n hash=key的hashcode n為數(shù)組大小，
- 取余(%)操作中如果除數(shù)為2的n次冪，則等價(jià)于與其除數(shù)-1的(&)操作，也就是(***<u>hash%n== (n-1) & hash ,前提是n為2的n次冪)
- 采用2進(jìn)制&操作，相對(duì)于采用%操作效率要高的多。
這就解釋了為什么數(shù)組的長(zhǎng)度為2的n次冪。
2.為什么桶中節(jié)點(diǎn)個(gè)數(shù)超過8個(gè)才會(huì)轉(zhuǎn)成紅黑樹？
紅黑樹中，刪除，插入和遍歷的最壞時(shí)間復(fù)雜度為O(log(n))
TreeNode占用的空間是普通Nodes占用空間的2倍，所以只有當(dāng)bin(bin就是bucket-桶，即HashMap中hashcode值一樣元素保存的地方)包含足夠多的節(jié)點(diǎn)的時(shí)候才會(huì)轉(zhuǎn)換為treenode，足夠多這個(gè)值是由TREEIFY_THRESHOLD的值決定的，當(dāng)bin中節(jié)點(diǎn)數(shù)變少是，又會(huì)轉(zhuǎn)換為普通node。
當(dāng)hashCode離散性很好的時(shí)候，樹型bin用到的概率非常小，因?yàn)閿?shù)據(jù)均勻分布在每個(gè)bin中，幾乎不會(huì)有bin中鏈表長(zhǎng)度會(huì)達(dá)到閾值。但是在隨機(jī)hashCode下，離散性可能會(huì)變差，然而JDK又不能阻止用戶實(shí)現(xiàn)這種不好的hash算法，因此就可能導(dǎo)致不均勻的數(shù)據(jù)分布。不過理想情況下隨機(jī)hashCode算法下所有bin中節(jié)點(diǎn)的分布頻率會(huì)遵循泊松分布，我們可以看到，一個(gè)bin中鏈表長(zhǎng)度達(dá)到8個(gè)元素的概率為0.00000006，幾乎是不可能事件。
image
