建議先看下文章中提供的源碼惹谐，然后再看解釋可以加深理解齐板。
內(nèi)部靜態(tài)變量
DEFAULT_INITIAL_CAPACITY
默認(rèn)初始化容量
DEFAULT_LOAD_FACTOR
默認(rèn)負(fù)載因子
TREEIFY_THRESHOLD
二叉樹閾值
UNTREEIFY_THRESHOLD
取消二叉樹閾值
MIN_TREEIFY_CAPACITY
二叉樹化所需要的最小容量
內(nèi)部類张吉，Node<K, V>
好像內(nèi)部存儲(chǔ)的hash沒(méi)用到霞势。
hashCode
計(jì)算hash值晕城，
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
靜態(tài)方法
static final inti hash(Object key)
計(jì)算key的hash值泞坦。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
static Class<?> comparableClassFor(Object x)
TODO
在二叉樹中使用到
static int compareComparables(Class<?> kc, Object k, Object x)
TODO
也是在二叉樹中用到
static final int tableSizeFor(int cap)
傳入容量cap，返回比傳入的容量cap大的最小二次冪砖顷。
變量
table
最終存儲(chǔ)數(shù)據(jù)的地方
entrySet
TODO
一個(gè)緩存用的set
size
容量大小當(dāng)前
modCount
TODO
操作數(shù)贰锁，貌似是線程安全用的
threshold
resize的閾值
loadFactor
負(fù)載因子
公有方法
構(gòu)造方法
public HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity)
public HashMap()
public HashMap(Map<? extends K, ? extends V> m)
pubMapEntries(Map<? extends K, ? extends V> m, boolean evict)
一次性放入多組鍵值對(duì)，也可以叫做鍵值對(duì)的復(fù)制滤蝠。
- 如果table沒(méi)有初始化則進(jìn)行初始化豌熄，根據(jù)傳入的m計(jì)算最大容量（根據(jù)負(fù)載因子）
- 如果table初始化了，則判斷是否會(huì)大于閾值物咳，大于閾值則resize
- for遍歷m锣险，完成數(shù)據(jù)的復(fù)制
注意：putVal函數(shù)
public int size()
返回map的容量
public boolean isEmpty()
返回map是否為空
public V get(Object key)
通過(guò)調(diào)用內(nèi)部方法getNode來(lái)獲取數(shù)據(jù)
final Node<K, V> getNode(int hash, Object key)
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)
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;
}
- 如果table為null或者長(zhǎng)度為0，或者計(jì)算的index的對(duì)應(yīng)值為null览闰，則返回null（沒(méi)有匹配）
- 否則檢查第一個(gè)值芯肤，如果keys也相等則說(shuō)明找到，返回
- 否則檢查是不是TreeNode压鉴，如果是則調(diào)用getTreeNode
- 否則遍歷鏈表后找到值后返回
public boolean containsKey(Object key)
調(diào)用內(nèi)部方法getNode崖咨，判斷是否包含key
public V put(K key, V value)
調(diào)用內(nèi)部方法putVal來(lái)實(shí)現(xiàn)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
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)
n = (tab = resize()).length;
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();
afterNodeInsertion(evict);
return null;
}
很重要，用來(lái)往table里放東西的方法晴弃。
- 檢查table掩幢，必要時(shí)做初始化（resize）
- 計(jì)算index逊拍，如果不和任何hash沖突，則新建Node
- 否則查看是否是同一個(gè)key（hash也相同）际邻，如果是則覆寫
- 否則發(fā)生撞庫(kù)芯丧，判斷是否是TreeNode，如果是則調(diào)用putTreeval方法
- 否則遍歷鏈表世曾，如果在鏈表中有相同的hash和key缨恒，則覆寫
- 否則插入鏈表鏈尾，如果插入后超過(guò)閾值轮听，則Treeify
- 如果onlyIfAbsent是true的話骗露，則不更新舊值
- 如果size大于閾值，則調(diào)用resize
onlyIfAbsent: 只有當(dāng)不存在時(shí)才更新
evict:
還有一些鉤子函數(shù)
- afterNodeAccess
- afterNodeInsertion
final Node<K, V>[] 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;
}
resize是很重要的一個(gè)內(nèi)部使用的函數(shù)血巍，
主要是用來(lái)處理數(shù)據(jù)結(jié)構(gòu)的初始化萧锉，以及在增刪Node的時(shí)候，
通過(guò)resize來(lái)保持?jǐn)?shù)據(jù)結(jié)構(gòu)的合理性述寡。
table為內(nèi)部保存數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)柿隙。
流程的大概總結(jié)：
- 計(jì)算當(dāng)前容量，如果已經(jīng)大于等于最大容量鲫凶，則沒(méi)必要resize禀崖，直接返回
- 如果當(dāng)前容量的兩倍小于最大容量，并且大于初始容量螟炫，則當(dāng)前閾值和容量翻倍
- 如果容量為零波附，但是閾值不為零，則將容量設(shè)置為閾值的值
- 否則的話則初始化容量和閾值
- 如果閾值還是零的話昼钻，則用當(dāng)前閾值和負(fù)載因子計(jì)算新的閾值
到此為止掸屡，閾值和容量的事情我們搞定了
下面開始把舊的table中的Node放到新的table中去。
- 對(duì)于每一個(gè)table中的Node换吧，計(jì)算新的index
- 還是老樣子折晦，如果是單個(gè)節(jié)點(diǎn)，則直接放進(jìn)新table中
- 如果是TreeNode沾瓦，則調(diào)用tree的方法满着，split
- 否則插入鏈表，因?yàn)閞esize之后贯莺，每個(gè)元素都可能出現(xiàn)在不同的位置上风喇，所以判斷插入的位置，然后建立兩個(gè)鏈表
判斷方式：(e.hash & oldCap) == 0
解釋：因?yàn)閞esize之后缕探，左移一位魂莫，相當(dāng)于最高位左移一位，因此如果e.hash & oldCap為零的話爹耗，
說(shuō)明e.hash的高位上沒(méi)有1耙考，因此就算newCap和e.hash并運(yùn)算結(jié)果也不會(huì)改變谜喊。
用此方法可以判斷每個(gè)e到底屬于哪個(gè)鏈表，
只可能有兩種倦始，一種是保持原來(lái)的鏈表斗遏，一種是進(jìn)入新的鏈表。
final void treeifyBin(Node<K, V>[] tab, int hash)
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);
}
}
鏈表到樹結(jié)構(gòu)的轉(zhuǎn)換
- 如果傳入的tab不符合要求鞋邑，則resize
- 否則诵次，計(jì)算index找到對(duì)應(yīng)元素，開始treeify
- 調(diào)用內(nèi)部方法
replacementTreeNode新建一個(gè)TreeNode - 創(chuàng)建樹頭hd枚碗，之后對(duì)于新的節(jié)點(diǎn)逾一，他的prev指向上一輪的舊節(jié)點(diǎn)，舊節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
- 創(chuàng)建紅黑樹肮雨，
treeify遵堵，之后細(xì)講
public void putAll(Map<? extends K, ? extends V> m)
調(diào)用內(nèi)部的函數(shù)putMapEntries。
public V remove(Object key)
繼續(xù)封裝怨规，調(diào)用內(nèi)部的removeNode方法鄙早。
返回被刪除的元素
final Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean moveable)
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
參數(shù)好多。椅亚。
先說(shuō)下參數(shù)
- hash，對(duì)應(yīng)的哈希值
- key舱污，對(duì)應(yīng)的key值呀舔，這個(gè)是唯一的
- value，對(duì)應(yīng)的value
- matchValue扩灯，配合value使用的媚赖，只刪除value也相同的Node
- moveable，用在tree中
具體的邏輯
- 如果符合條件（table不為空珠插，hash對(duì)應(yīng)的位置有數(shù)據(jù)之類）惧磺，則正式開始
- 找到要?jiǎng)h除的Node，和putVal差不多捻撑，單值磨隘，紅黑樹或者鏈表，找到為止
- 如果找到的node不為空顾患，且value相同（matchValue）番捂，則根據(jù)node類型刪除
- 如果是TreeNode，調(diào)用removeTreeNode方法
- 如果是firstNode江解，則tabl[index] = node.next
- 否則p.next = node.next设预，經(jīng)典的鏈表刪除元素的方法
鉤子函數(shù)：afterNodeRemoval
public void clear()
清空所有的元素，tab[i] = null
public boolean containsValue(Object value)
因?yàn)槊恳粋€(gè)Node都有next屬性犁河，
所以對(duì)table遍歷鳖枕，再對(duì)node遍歷即可找到是否包含value的node魄梯。
