一. 插入
1.1 主流程解析
public static void main(String[] args) {
HashMap<Object, Object> map = new HashMap<Object, Object>();
// 重寫Entity的hashCode方法，傳回傳入的數值
map.put(new Entity(97), "2");
// 插入a，hashCode值同樣為97，模拟相同hashCode的值插入，形成連結清單
map.put("a", "1");
// 再次插入a，模拟相同hashCode且滿足==，或equals，替換原值并傳回
map.put("a", "1");
// 增加多個值，模拟擴容
for(int i = 'b'; i < 'q'; i++){
map.put(String.valueOf((char)i), i);
}
}
調用put方法
public V put(K key, V value) {
// 計算hash值，調用key.hashCode() ^ (key.hashCode() >>> 16)
// hashCode和hashCode右移16位進行位運算，增加離散性
return putVal(hash(key), key, value, false, true);
}
利用算好的hash值，開始插入資料
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，那麼先初始化，預設hashMap數組大小是16【DEFAULT_INITIAL_CAPACITY】
// 預設的擴容因子是0.75【DEFAULT_LOAD_FACTOR】，即16 * 0.75
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 根據容量（n - 1） & hash，算出一個小于n的數組下标，判斷目前下标對應的tab是不是為空，
// 如果為空，那麼直接建立一個Node放到該數組位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 如果目前下标已經有一個Node了
Node<K,V> e; K k;
// 判斷hash值知否一樣，并且key是不是同一個對象或這個equals相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果相等，就把目前下标的Node賦給臨時變量e
e = p;
else if (p instanceof TreeNode)
// 如果目前下标的Node是一個TreeNode，說明是一個紅黑樹的Node，然後往紅黑樹中插入資料，插入邏輯就移到TeeNode中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 否則目前下标的Node是一個連結清單結構
// 從頭部周遊連結清單
for (int binCount = 0; ; ++binCount) {
// 如果沒有下一個節點了，表示前面的周遊都沒有遇到key相等或equal的，說明該節點已經是尾節點了，那麼就把尾節點的下一個節點設定為目前需要插入的節點
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 判斷節點數有8個了，那麼就将連結清單轉換成紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果有相同或equals的key，那麼就break掉，此時e就是該相同key的Node
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果e不為null，說明連結清單中有相同的key，直接替換該值并傳回，不會對modCount或者size執行++操作
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 成功插入資料，除開相等或equals的key，modeCount都要++
++modCount;
//size也執行++操作，并且比較是否大于了擴容門檻值，然後進行自動擴容操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
上面是HashMap插入的大緻插入流程，下面我們來具體分析每一步
1.2 初始化table
初始化的過程其實分為兩步，第一步是在執行個體化HashMap的時候，HashMap的構造方法分為無參構造和有參構造
1.2.1 構造器初始化
// 無參構造方法預設會初始化擴容門檻值因子，loadFactor=0.75，後續初始化時預設使用16作為數組初始化容量
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 有參構造方法，可以傳入一個容量大小，擴容因子
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方法中會進行一些列的位運算，最終傳回一個小于等于initalCapacity的2的幂次方的容量值，後續resize的時候會用到
this.threshold = tableSizeFor(initialCapacity);
}
1.2.1 插入過程中的初始化
數組的初始化是在put的時候進行的，當發現目前table為空會長度為0時，會進行重新計算數組長度。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
下面來看resize方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 擷取到原數組的長度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 擷取到原門檻值，如果是通過有參構造器建立的hashMap，這個值會是一個2的幂次方的數值，當第一次進這個方法的時候就是将要初始化的數組的長度，而不是乘以因子後的門檻值
int oldThr = threshold;
int newCap, newThr = 0;
// 如果原容量大于0，表示初始化過了
if (oldCap > 0) {
// 長度不能超過2^32次方個
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// oldCap左移以為表示 乘以 2，原來的擴容門檻值也翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 如果沒初始過，并且原來的門檻值大于0，那應該就是通過有參構造函數執行個體化的HashMap，直接将擴容門檻值給新數組的容量
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) {
// 周遊原來長度的數組，決定該下标的Node應該放到新的數組的哪個下标
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 先把原下标置為null
oldTab[j] = null;
// 如果目前下标隻有一個Node，沒有連結清單也沒有紅黑樹，那麼就用hash值和新數組長度-1做與運算，
// 得到一個小于新數組長度的下标，并放進去
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果目前下标的Node是紅黑樹結構，就拆分紅黑樹，這裡我們等到面說了紅黑樹再來分析
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;
// hash值和原數組長度做與運算，長度是一個2的幂次方，是以隻有可能有一個位上是1
// 是以這個與運算，要麼是等于0，要麼是等于原數組長度
// 如果等于0，就放到低位，如果不等于0，就放到新擴容的高位，位置為原位置 + 原數組長度
// 這樣就完成了原連結清單的拆分
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.2.2 連結清單轉紅黑樹
前面我們提到當同一個下标上的連結清單的Node個數大于等于了8個，那麼就會将連結清單轉換成紅黑樹，但實際上，這麼回答不對，大于等于8隻是會進入下面的treeifyBin方法，但這個方法還有一個判斷條件必須是數組的長度要大于等于64【MIN_TREEIFY_CAPACITY】才會轉換紅黑樹，否則hashMap會認為目前數組還太小，可以通過擴容解決。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 判斷數組長度是否小于64，如果小于進行擴容操作
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// (n - 1) & hash就是目前連結清單上Node數等于8的數組下标，擷取到這個下标的node
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 頭節點，尾節點
TreeNode<K,V> hd = null, tl = null;
do {
// 利用原Node的hash，value，key， next建立一個新的TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
// 第一次循環把原連結清單的作為head節點産生的TreeNode指派給hd，尾節點也指向它
if (tl == null)
hd = p;
// 後面的循環将目前周遊的節點的prev指向上一次循環種的尾節點，上一次循環的尾節點指向目前節點
else {
p.prev = tl;
tl.next = p;
}
// 并把尾節點指向目前節點
tl = p;
} while ((e = e.next) != null);
// 上面循環完成後形成了另一個TreeNode的雙向連結清單
// 還是按原來的格式，将頭節點放入數組中，即頭插法
if ((tab[index] = hd) != null)
// 産生紅黑樹
hd.treeify(tab);
}
}
看生成紅黑樹之前，我們先看下TreeNode類
TreeNode<K,V> parent; // red-black tree links 父節點
TreeNode<K,V> left; // 左邊子節點
TreeNode<K,V> right;// 右邊子節點
TreeNode<K,V> prev; // 雙向連結清單用的上一個子節點
boolean red; // 是否為紅節點
紅黑樹的定義或者說是規則如下：
- 每個結點或是紅的，或是黑的
- 根節點是黑的
- 每個葉結點是黑的，null leaves
- 如果一個結點是紅的，則它的兩個兒子都是黑的
- 對每個結點，從該結點到其子孫節點的所有路徑上包含相同數目的黑結點
下面來看TreeNode是怎麼利用頭節點的treeify方法建立出這個樹的
final void treeify(Node<K,V>[] tab) {
// 根節點臨時變量
TreeNode<K,V> root = null;
// 周遊treenode連結清單，一個一個插入到紅黑樹種
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
// x為目前節點，next為下一個節點
x.left = x.right = null;
// 當周遊的x為頭節點時root==null
// 設定它的父節點為null，不為紅節點，root定位頭節點
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
// 當後續進入該節點時
K k = x.key;
int h = x.hash;
Class<?> kc = null;
// 從根節點開始比較hash值的大小
for (TreeNode<K,V> p = root;;) {
// 臨時變量辨別方向和目前周遊到的節點的hash值
int dir, ph;
K pk = p.key;
// 如果周遊到的樹節點的hash值大于目前待插入的節點，辨別需要繼續和左邊子節點進行比較
// 如果相反，則和右邊子節點繼續比較
// 如果相等，看待插入節點是否實作了Comparable，如果沒有實作或者實作了但是調用compareTo比較結果還是等于0，那麼就調用tieBreadOrder方法繼續比較
// 如果比較的其中一個有一個為null或者類名稱相同，就調用System.identityHashCode方法進行比較，反正最後得出一個比較值，如果還是等于0，就讓它為0，預設走比較左子節點的邏輯
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// xp臨時變量，辨別待插入節點的父節點
// 根據上面判斷出來的方向，看它的左右子節點是否存在，如果存在則繼續比較，如果不存在
// 将目前周遊到的樹節點作為待插入節點的父節點
// 并且根據方向，将目前周遊的樹節點根據方向将左或右子節點置為待插入節點
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 插入後平衡目前樹，傳回數的root節點
root = balanceInsertion(root, x);
break;
}
}
}
}
// 得到的root對應的node放回數組的對應下标上
moveRootToFront(tab, root);
}
我們繼續看如何平衡插入節點後的樹
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
// 預設插入的新的節點都是紅節點
x.red = true;
// 定義循環變量
// xp：目前節點的父節點
// xpp：目前節點的祖父節點
// xppl：目前節點的祖父節點的左子節點
// xppr：目前節點的祖父節點的右子節點
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
// 如果目前節點的父節點為null，說明目前節點就是根節點，将自己置為黑色傳回
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
// 如果目前節點的父節點為黑色，或者祖父節點為null，說明新插入的節點的為第二層節點，上層就是root節點，直接傳回父節點root節點
else if (!xp.red || (xpp = xp.parent) == null)
return root;
// 如果父節點的左子節點就是新插入的節點的父節點
if (xp == (xppl = xpp.left)) {
// 如果叔叔節點已經存在，并且是紅節點，那麼就将祖父節點的黑向下壓，即父節點和叔叔節點都置為黑節點，祖父節點置為紅節點，目前需要平衡的節點設定為祖父節點遞歸
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
// 叔叔節點為空或者為黑色
else {
// 如果目前節點是父節點的右子節點，先左旋，再右旋
// 如果是左子節點，那麼直接右旋
// 得到新的root節點後，繼續遞歸平衡
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
// 如果父節點是右孩子節點
else {
// 同上面判斷叔叔節點的邏輯一樣，如果叔叔節點也是紅色，直接将黑色的祖父節點顔色向下壓，祖父節點變紅，祖父節點的兩個子節點變黑，然後遞歸判斷祖父節點
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
// 同上面的邏輯，隻不過是反過來的
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
左旋，其中參數說明一下：
root：目前的根節點
p：需要進行左旋的節點
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
// 要滿足左旋必須是目前要左旋的節點的右節點不為空
if (p != null && (r = p.right) != null) {
// 将需要左旋的節點的右子節點指向原右節點的左節點，如果不為空，再将這個右子節點的父節點指向目前節點
if ((rl = p.right = r.left) != null)
rl.parent = p;
// 如果目前節點的父節點為null，說明p節點是root節點，那麼就将它的右節點置為root節點并置為黑色
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
// 如果p不是root節點，p是它父節點的左節點，那麼直接将pp的左節點指向p的右節點r
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
// 把最終得到的r的左節點指向目前節點完成左旋
r.left = p;
p.parent = r;
}
return root;
}
右旋的操作邏輯自己體會一下，這裡就不概述了。
最後得到一顆完整的紅黑樹結構，傳回了他的root節點，
然後把root節點對應的node設定到對應的數組下标上。
1.2.3 插入到已生成的紅黑樹
前面主流程中會判斷目前下标的節點是否是instanceof TreeNode，如果是說明這個下标上已經是紅黑樹，那麼本次插入會直接将節點往紅黑樹中插。
調用TreeNode【root節點】的putTreeVal方法插入。
/**
* Tree version of putVal.
*/
// map：hashMap執行個體
// tab：數組
// h： hash值
// k：鍵
// v：值
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
// 拿到root節點，一般就是自己
TreeNode<K,V> root = (parent != null) ? root() : this;
// 這裡的邏輯基本和treeify方法一樣，判斷出本次插入的這個節點的hash值，是該往左邊查還是往右邊查，如果周遊到的節點剛好有這個方向的子節點，就遞歸比較，循環中主要做插入位置的判斷，其他操作還是一樣交給balanceInsertion，然後再設定root節點對應的Node到數組上
// **另外，這裡還有一個很大的不同是**：判斷周遊到的節點hash值如果和目前節點的hash值相等，并且兩個key的對象是同一個對象或者equals，那麼直接傳回該節點值，不會做任何插入操作，而是直接在外層方法中進行值替換
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
// 平衡調整及設定數組下标對應的root節點
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
好了，插入的部分基本上講到這裡，下面我們來看查詢的部分，如果能了解插入的邏輯，查詢就比插入簡單多了。
二. 查詢
2.1 主流程
查詢的基本思路：
- 通過hash值，根據容量做與運算，擷取到這個hash值對應的數組下标，
- 比較判斷節點類型
- 周遊比較key是否是同一對象或是否equals，拿出對應的Node節點或者TreeNode節點
- 擷取value
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;
}
其實基本上查詢的代碼就差不多結束了，隻有treeNode需要再次進getTreeNode擷取節點，稍微想一下就應該知道裡面的邏輯是什麼，無非就是遞歸判斷樹節點和目前要查詢的節點的hash值大小，選擇方向，繼續遞歸，一旦查詢到有滿足條件的key，就傳回該節點。
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// 如果既不大于也不小于，還不等于，那麼判斷是否有左子節點是否為kong，取右節點繼續向下周遊
else if (pl == null)
p = pr;
// 取左節點繼續往下周遊
else if (pr == null)
p = pl;
// 比較compareTo，能比較出大小，繼續向下周遊
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
// 所有上述條件都得不到一個，預設使用右節點查找，再找不到就傳回null
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
今天就先寫到這裡，後面還涉及到HashMap的删除操作，也是一個比較複雜的過程，下次慢慢寫。
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)