1.概述
學(xué)習(xí)本文你可以了解到：
- HashMap 是什么樣的內(nèi)部結(jié)構(gòu)？有什么特點(diǎn)？
- 他的工作原理是什么樣？
- equlas() 和 hashCode() 方法都有什么作用？
- 默認(rèn)常量的定義有什么意義？
2.重要參數(shù)介紹
在構(gòu)造參數(shù)中，一個(gè)是桶的容量，一個(gè)是加載因子。
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
閾值常量
/**
* 默認(rèn)的初始容量 - 必須是2的冪。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 容量最大值，分配數(shù)組最大長(zhǎng)度，超過(guò)這個(gè)長(zhǎng)度在保存就只能保存在鏈表中了。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默認(rèn)加載因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 鏈表和紅黑樹(shù)轉(zhuǎn)換的閾值
* 該值必須大于2，并且應(yīng)該至少為8，
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 當(dāng)執(zhí)行resize操作時(shí)，當(dāng)桶中bin的數(shù)量少于UNTREEIFY_THRESHOLD時(shí)使用鏈表來(lái)代替樹(shù)。默認(rèn)值是6
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 當(dāng)鏈表中的元素等于8個(gè)進(jìn)行創(chuàng)建樹(shù)的時(shí)候，如果當(dāng)前桶的數(shù)量小于64，則進(jìn)行擴(kuò)容重新分配 hash 值
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
3.算法介紹
hash 值的計(jì)算方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
index 算法
// n = table.length
int index = (n - 1) & hash
為什么要有HashMap的hash()方法，難道不能直接使用KV中K原有的hash值嗎？在HashMap的put、get操作時(shí)為什么不能直接使用K中原有的hash值。
從上面的代碼可以看到key的hash值的計(jì)算方法。key的hash值高16位不變，低16位與高16位異或作為key的最終hash值。（h >>> 16，表示無(wú)符號(hào)右移16位，高位補(bǔ)0，任何數(shù)跟0異或都是其本身，因此key的hash值高16位不變。）
為什么要這么干呢？這個(gè)與HashMap中table索引的計(jì)算有關(guān)。因?yàn)?，table的長(zhǎng)度都是2的冪，因此index僅與hash值的低n位有關(guān)，hash值的高位都被與操作置為0了。
假設(shè)table.length=2^4=16。
hash 計(jì)算
0000 0000 0000 0000 0000 0000 00000 1000 = 8
0000 0000 0000 0000 0000 0000 00000 0000 = 0 位移16
------------------------------------------------------------
0000 0000 0000 0000 0000 0000 00000 1000 = 8 異或運(yùn)算結(jié)果
0000 0000 0000 0001 0000 0000 00000 1000 = 65544
0000 0000 0000 0000 0000 0000 00000 0001 = 1 位移16
------------------------------------------------------------
0000 0000 0000 0001 0000 0000 00000 1001 = 65545 異或運(yùn)算結(jié)果
index 計(jì)算
0000 0000 0000 0000 0000 0000 00000 1000 = 8 hash 值
0000 0000 0000 0000 0000 0000 00000 1111 = 15 (16-1)數(shù)組長(zhǎng)度-1
------------------------------------------------------------
0000 0000 0000 0000 0000 0000 00000 1000 = 8 與運(yùn)算結(jié)果
# 在沒(méi)有 進(jìn)行hash 運(yùn)算的情況下，和上面的8的索引值結(jié)果一樣，發(fā)生了碰撞
0000 0000 0000 0001 0000 0000 00000 1000 = 65544 hash 值
0000 0000 0000 0000 0000 0000 00000 1111 = 15 (16-1)數(shù)組長(zhǎng)度-1
------------------------------------------------------------
0000 0000 0000 0000 0000 0000 00000 1000 = 8 與運(yùn)算結(jié)果
# 有過(guò) hash 運(yùn)算，因?yàn)楦?6位和低16位異或過(guò)產(chǎn)生的 hash 結(jié)果發(fā)生了變化，這樣就避免的高位的 hash 碰撞
0000 0000 0000 0001 0000 0000 00000 1001 = 65545 hash 值
0000 0000 0000 0000 0000 0000 00000 1111 = 15 (16-1)數(shù)組長(zhǎng)度-1
------------------------------------------------------------
0000 0000 0000 0000 0000 0000 00000 1001 = 9 與運(yùn)算結(jié)果
上面的第一個(gè)示例，我們拿 8的 hash 計(jì)算的第一個(gè)結(jié)果來(lái)計(jì)算索引值，因?yàn)?hashCode 和 hash 的結(jié)果一致，我們就直接拿來(lái)和 length-1 來(lái)計(jì)算索引值為8。
第二和第三個(gè)示例我們分別拿了 65544的hashCode和 hash 值做了索引計(jì)算，結(jié)果卻不一樣。
由上可以看到，只有hash值的低4位參與了運(yùn)算。
這樣做很容易產(chǎn)生碰撞。設(shè)計(jì)者權(quán)衡了speed, utility, and quality，將高16位與低16位異或來(lái)減少這種影響。設(shè)計(jì)者考慮到現(xiàn)在的hashCode分布的已經(jīng)很不錯(cuò)了，而且當(dāng)發(fā)生較大碰撞時(shí)也用樹(shù)形存儲(chǔ)降低了沖突。僅僅異或一下，既減少了系統(tǒng)的開(kāi)銷，也不會(huì)造成的因?yàn)楦呶粵](méi)有參與下標(biāo)的計(jì)算(table長(zhǎng)度比較小時(shí))，從而引起的碰撞。
4.方法介紹
數(shù)組
transient Node<K,V>[] table;
鏈表結(jié)構(gòu)
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // hash 值
final K key; // key 值
V value; // value 值
Node<K,V> next; // 下一個(gè)節(jié)點(diǎn)
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
紅黑樹(shù)
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父節(jié)點(diǎn)
TreeNode<K,V> left; // 左邊節(jié)點(diǎn)
TreeNode<K,V> right; // 右邊節(jié)點(diǎn)
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // 顏色，root 節(jié)點(diǎn)為黑色
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
TreeNode繼承了LinkedHashMap.Entry<K,V>，然而LinkedHashMap.Entry<K,V>又繼承了HashMap.Node<K,V>，所以所數(shù)組中存儲(chǔ)的結(jié)構(gòu)都可以使用HashMap.Node。
紅黑樹(shù)是一種特殊的二叉樹(shù)，主要用它存儲(chǔ)有序的數(shù)據(jù)，提供高效的數(shù)據(jù)檢索，時(shí)間復(fù)雜度為O(lgn)，每個(gè)節(jié)點(diǎn)都有一個(gè)標(biāo)識(shí)位表示顏色，紅色或黑色，有如下5種特性：
- 每個(gè)節(jié)點(diǎn)要么紅色，要么是黑色；
- 根節(jié)點(diǎn)一定是黑色的；
- 每個(gè)空葉子節(jié)點(diǎn)必須是黑色的；
- 如果一個(gè)節(jié)點(diǎn)是紅色的，那么它的子節(jié)點(diǎn)必須是黑色的；
- 從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑包含相同個(gè)數(shù)的黑色節(jié)點(diǎn)；
紅黑樹(shù)
初始化
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);
}
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
put 方法邏輯：
- 對(duì) key 的 hashCode 重新計(jì)算 hash，然后計(jì)算出 index
- 若 table 為空，調(diào)用 resize 初始化
- 如果沒(méi)有碰撞直接放到桶中，如果有碰撞了key 相等就覆蓋 value，不相等就添加到鏈表尾端
- 如果鏈表長(zhǎng)度大于8時(shí)轉(zhuǎn)換為紅黑樹(shù)結(jié)構(gòu)（大于等于TREEIFY_THRESHOLD時(shí)）
- 如果bucket滿了(超過(guò)load factor*current capacity)，就要resize。
public V put(K key, V value) {
// 獲取 key 的 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;
// 判斷 table 是否為 null 或者為空，重置大小
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 獲取 hash 的索引和對(duì)應(yīng)的值，如果為 null 創(chuàng)建一個(gè) Node 對(duì)象放到對(duì)應(yīng)索引的位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 判斷當(dāng)前索引的 key 是否和 put 的 key 相等，如果相等就把值覆蓋老的值（這一步可以看出 hashmap 的 key 唯一性）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 后邊用于統(tǒng)一設(shè)置返回值和覆蓋相同 key 的值
e = p;
else if (p instanceof TreeNode)
// 如果當(dāng)前節(jié)點(diǎn)是紅黑樹(shù)，直接調(diào)用紅黑樹(shù)的 put 方法（此方法后面會(huì)詳細(xì)講解）
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 創(chuàng)建 Node 對(duì)象放置在鏈表的尾端
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 添加節(jié)點(diǎn)后判斷當(dāng)前鏈表的長(zhǎng)度是否大于等于8了，如果是就轉(zhuǎn)換為紅黑樹(shù)結(jié)構(gòu)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 當(dāng)在鏈表中找到有 key 相等的情況了直接跳出循環(huán)，后邊用于統(tǒng)一設(shè)置返回值和覆蓋相同 key 的值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 統(tǒng)一設(shè)置返回值和覆蓋相同 key 的值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 添加完后 size++ 操作，然后判斷是否大于最大裝載閾值，如果是就調(diào)整大小，調(diào)增大小為原長(zhǎng)度的2倍。
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
get 方法相對(duì)比較簡(jiǎn)單，先去匹配索引位置的key 相等就直接返回，然后在去檢查是否為數(shù)，否則遍歷 table 去查找
public V get(Object key) {
Node<K,V> e;
// 獲取 key 的 hash
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;
// 如果 table 不為空且索引位置值不為 null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 索引位置的 key 和 key 若相等直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 如果是紅黑樹(shù)結(jié)構(gòu)直接調(diào)用 getTreeNode 方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 遍歷鏈表對(duì)比 key 是否相等，找到就返回，否則返回 null
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
resize
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;
}
treeifyBin
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
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);
}
}
5.問(wèn)題回答
1.hashmap 是個(gè)什么樣的結(jié)構(gòu)？
hashmap 內(nèi)部采用的是 數(shù)據(jù)+鏈表/紅黑樹(shù)的方式存在。在 jdk1.8中加入了紅黑樹(shù)很好的解決了 hash 碰撞導(dǎo)致鏈表查詢效率過(guò)低。查詢效率：O + O(n) / O(logn)
6.運(yùn)算符介紹
& 與運(yùn)算：兩個(gè)操作數(shù)中位都為1，結(jié)果才為1，否則結(jié)果為0
| 或預(yù)算：兩個(gè)位只要有一個(gè)為1，那么結(jié)果就是1，否則就為0
^ 異或運(yùn)算：兩個(gè)操作數(shù)的位中，相同則結(jié)果為0，不同則結(jié)果為1
示例:
0001 0110 22
0000 0101 5
----------------
0001 0011 19
~ 非運(yùn)算：如果位為0，結(jié)果是1，如果位為1，結(jié)果是0
<< 向左位移
>> 向右位移
>>> 向右無(wú)符號(hào)位移
