|
HashMap作為java開發(fā)中最常用的集合之一,，了解其特性對(duì)日常開發(fā)尤為重要,，本文基于jdk1.8源碼來分析HashMap有哪些重要的特性,。
1 數(shù)據(jù)結(jié)構(gòu)
了解HashMap首先當(dāng)然要從了解數(shù)據(jù)結(jié)構(gòu)說起,，具體見下圖：
數(shù)據(jù)結(jié)構(gòu)源碼如下：
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
......
}
從上圖可以看出HashMap內(nèi)部是由Node節(jié)點(diǎn)的鏈表數(shù)組構(gòu)成,，該數(shù)據(jù)結(jié)構(gòu)又稱為哈希桶,。
2 鏈地址法解決哈希沖突
既然HashMap內(nèi)部是一個(gè)哈希桶，那么進(jìn)行put操作時(shí)就有可能會(huì)發(fā)生哈希沖突,，哈希沖突是將元素放入數(shù)組時(shí),，若數(shù)組中存在一樣的元素即表示發(fā)生了哈希沖突，而HashMap解決哈希沖突的方法為鏈地址法,，這種解決沖突的方法具體操作是采用鏈表的方式,，詳細(xì)具體操作如下：
- 首先計(jì)算傳入key的hash值
- 根據(jù)hash值找出對(duì)應(yīng)數(shù)組中的下標(biāo)
- 若數(shù)組下標(biāo)中存在元素，則判斷key是否相等,，相等則覆蓋value值,，不相等則進(jìn)入next節(jié)點(diǎn)
- 循環(huán)步驟3，若找不到相等的key,，則用傳入的key,，value值創(chuàng)建一個(gè)新的Node節(jié)點(diǎn),，將新的Node節(jié)點(diǎn)加入鏈表尾部
源碼如下：
public V put(K key, V value) {
//hash方法計(jì)算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;
//hashmap采用默認(rèn)構(gòu)造器未指定大小時(shí)，則進(jìn)行擴(kuò)容,，這也表示默認(rèn)構(gòu)造hashmap時(shí)其容量為懶加載
if ((tab = table) == null || (n = tab.length) == 0)
//resize()為擴(kuò)容主要方法
n = (tab = resize()).length;
//i = (n - 1) & hash 即為計(jì)算哈希桶位置的算法
if ((p = tab[i = (n - 1) & hash]) == null)
//算出位置后,，若該處沒有節(jié)點(diǎn)（產(chǎn)生哈希沖突）則直接插入
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則表示產(chǎn)生哈希沖突的處理方法
else if (p instanceof TreeNode)
//若為樹結(jié)構(gòu)，則進(jìn)行樹化處理
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//主要邏輯在這里
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//找不到相等的key,，則構(gòu)造一個(gè)新Node插入鏈表尾部
p.next = newNode(hash, key, value, null);
//判斷是否達(dá)到紅黑樹構(gòu)造條件
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//找到了相等的key則break
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//相等的key替換value值邏輯
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//新value值替換老value值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判斷容量是否大于閾值,，大于則擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
注意，這里計(jì)算哈希桶位置的代碼為：i = (n - 1) & hash,，該算法表示在n為2的倍數(shù)情況下,，通過位運(yùn)算的方式計(jì)算數(shù)組下標(biāo)，等同于數(shù)學(xué)中的取余,，這同時(shí)也表示了hashmap的大小永遠(yuǎn)為2的倍數(shù),。
3 hash值計(jì)算方法
HashMap中計(jì)算hash值方法源碼如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
從上面代碼可看出，首先調(diào)了傳入key的hashCode方法計(jì)算出hashCode,，最后將該hashCode與它的高16位做與運(yùn)算,，這樣做的原因在于因?yàn)閿?shù)組大小值一般都是低位，采用(n - 1) & hash算法計(jì)算數(shù)組位置時(shí),，hash值只有低位有用,，所以要將hash值的高位與低位相與，這樣增加了隨機(jī)性,，發(fā)生哈希沖突的概率變得更小了,。
4 擴(kuò)容
HashMap擴(kuò)容主要是由下列三個(gè)屬性相互影響決定的：
- 第一個(gè)是HashMap的總?cè)萘縞apacity(默認(rèn)值16）
- 第二個(gè)是負(fù)載因子loadFactor（默認(rèn)值0.75）
- 第三個(gè)是閾值threshold（默認(rèn)值12），該值由capacity * loadFactor決定
當(dāng)進(jìn)行put操作時(shí),，若hashmap內(nèi)節(jié)點(diǎn)數(shù)大于閾值則進(jìn)行擴(kuò)容,，擴(kuò)容形式為兩倍擴(kuò)容，與jdk1.7擴(kuò)容明顯不同的是,，jdk1.8的擴(kuò)容不再是遍歷老的節(jié)點(diǎn),，重新計(jì)算老的節(jié)點(diǎn)在新的容量中的位置，僅僅只是將當(dāng)前位置加上擴(kuò)容前的容量當(dāng)做新的位置,，這樣就避免了jdk1.7擴(kuò)容時(shí)的環(huán)形鏈表問題,。
具體源碼如下：
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;
}
//newCap即為擴(kuò)容后的大小
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 閾值也增加兩倍
}
else if (oldThr > 0) // 用構(gòu)造器初始化hashmap時(shí)，若只指定了閾值則容量值等于設(shè)置的閾值
newCap = oldThr;
else { // 如果閾值也沒有設(shè)置,，則容量和閾值都設(shè)為默認(rèn)
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;
//下面則是擴(kuò)容主要邏輯
@SuppressWarnings({"rawtypes","unchecked"})
//生成一個(gè)新的哈希桶
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;
//如果老哈希桶下標(biāo)處只有一個(gè)元素則直接計(jì)算新哈希桶中位置放置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//若節(jié)點(diǎn)是樹則進(jìn)行樹化處理
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 下面就是一般的擴(kuò)容邏輯了
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;
}
5 節(jié)點(diǎn)數(shù)大于等于7時(shí)構(gòu)造紅黑樹
當(dāng)hashmap進(jìn)行put操作時(shí)，若發(fā)生哈希沖突且對(duì)應(yīng)鏈表中無相等的節(jié)點(diǎn),，則將新的節(jié)點(diǎn)加入鏈表尾部,，此時(shí)若該鏈接長(zhǎng)度過長(zhǎng)，hashmap會(huì)將該鏈表進(jìn)行樹化處理,，具體處理為假如該鏈表長(zhǎng)度大于等于7時(shí),，會(huì)轉(zhuǎn)變成紅黑樹,，紅黑樹是一個(gè)典型的二叉查找樹，在搜索節(jié)點(diǎn)時(shí)具有比鏈表更優(yōu)的性能,，時(shí)間復(fù)雜度一般為O(logn),，hashmap轉(zhuǎn)變?yōu)闃涞倪^程是jdk1.7中沒有的。
具體源碼如下：
if ((e = p.next) == null) {
//找不到相等的key,，則構(gòu)造一個(gè)新Node插入鏈表尾部
p.next = newNode(hash, key, value, null);
//判斷是否達(dá)到紅黑樹構(gòu)造條件,，TREEIFY_THRESHOLD是一個(gè)final值為8
if (binCount >= TREEIFY_THRESHOLD - 1)
//對(duì)該鏈表進(jìn)行樹化處理
treeifyBin(tab, hash);
break;
}
6 容量值永遠(yuǎn)為2的倍數(shù)
從上面的分析可知，計(jì)算哈希桶位置算法(n - 1) & hash需保證n一定為2的倍數(shù),，hashmap是如何保證容量為2的倍數(shù)的呢,？我們知道hashmap初始化時(shí)可以指定容量，我們可以先從該構(gòu)造方法看起：
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;
//tableSizeFor方法保證了傳入的值一定是2的倍數(shù)
//hashmap容量為懶加載,，只有在put操作時(shí)才會(huì)對(duì)自己擴(kuò)容,，假如容量為0，擴(kuò)容后的容量會(huì)設(shè)置成閾值,，所以這里的閾值也可以看成hashmap的容量
this.threshold = tableSizeFor(initialCapacity);
}
從以上源碼可以看出,，hashmap是通過tableSizeFor方法保證自己的容量為2的倍數(shù)，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;
}
該算法詳解如下：
先來看有關(guān)n位操作部分,，先來假設(shè)n的二進(jìn)制為01xxxxxx,，然后
- 對(duì)n右移1位：001xxxxx，再位或：011xxxxx
- 對(duì)n右移2為：00011xxx,，再位或：01111xxx
- 同理,，前面有四個(gè)1了，再右移4位然后進(jìn)行位或操作可得8個(gè)1
- 綜上可知,，該算法讓最高位的1后面的位全變?yōu)?,。
- 由于int只有32位，所以完全覆蓋了int的位數(shù)
將最高位的1后面的位全變?yōu)?后,，再進(jìn)行n+1操作,，得出的值就為2的倍數(shù)了
|
