HashMap可能是我們使用最多的鍵值對(duì)型的集合類了，它的底層基于哈希表，采用數(shù)組存儲(chǔ)數(shù)據(jù)，使用鏈表來(lái)解決哈希碰撞。在JDK1.8中還引入了紅黑樹來(lái)解決鏈表長(zhǎng)度過(guò)長(zhǎng)導(dǎo)致的查詢速度下降問題。以下是文檔對(duì)它的介紹中我們重點(diǎn)關(guān)注的部分：
Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs.
Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use. And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used.
HashMap的結(jié)構(gòu)如下所示：
構(gòu)造函數(shù)與成員變量
在看構(gòu)造函數(shù)和成員變量前，我們要先看下其數(shù)據(jù)單元，因?yàn)?code>HashMap有普通的元素，還有紅黑樹的元素，所以其數(shù)據(jù)單元定義有兩個(gè)：
// 普通節(jié)點(diǎn)
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// ...
}
// 樹節(jié)點(diǎn)，繼承自LinkedHashMap.Entry
// 這是因?yàn)長(zhǎng)inkedHashMap是HashMap的子類，也需要支持樹化
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
// ...
}
// LinkedHashMap.Entry的實(shí)現(xiàn)
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
TreeNode定義了一些相關(guān)操作的方法，我們會(huì)在使用時(shí)進(jìn)行分析。
成員變量
// capacity初始值，為16，必須為2的次冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// capacity的最大值，為2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// load factor，是指當(dāng)容量被占滿0.75時(shí)就需要rehash擴(kuò)容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 鏈表長(zhǎng)度到8，就轉(zhuǎn)為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 樹大小為6，就轉(zhuǎn)回鏈表
static final int UNTREEIFY_THRESHOLD = 6;
// 至少容量到64后，才可以轉(zhuǎn)為樹
static final int MIN_TREEIFY_CAPACITY = 64;
// 保存所有元素的table表
transient Node<K,V>[] table;
// 通過(guò)entrySet變量，提供遍歷的功能
transient Set<Map.Entry<K,V>> entrySet;
// 下一次擴(kuò)容值
int threshold;
// load factor
final float loadFactor;
構(gòu)造函數(shù)
HashMap有多個(gè)構(gòu)造函數(shù)，主要支持配置容量capacity和load factor，以及從其他Map集合獲取初始化數(shù)據(jù)。
public HashMap(int initialCapacity, float loadFactor) {
// ... 參數(shù)校驗(yàn)
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
這些構(gòu)造函數(shù)都很簡(jiǎn)單，putMapEntries也是依次插入元素的，我們后續(xù)分析put方法時(shí)就能理解其操作了，這里我們還要看下tableSizeFor這個(gè)方法：
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;
}
如果你是跟隨我文章的順序讀到這里，有沒有感覺十分熟悉？這就是找到距離cap參數(shù)最近的2的次冪呀。沒有讀過(guò)也沒有關(guān)系，這里奉上鏈接，里面有非常詳細(xì)的解析。
Java集合源碼分析之Queue（三）：ArrayDeque
重要方法
無(wú)論是List還是Map，最重要的操作都是增刪改查部分，我們還從增加一個(gè)元素開始分析。
增加一個(gè)元素
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
這里我們先關(guān)注下hash函數(shù)，在HashMap中其實(shí)現(xiàn)如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這里用到的方法很簡(jiǎn)單，就是把key與其高16位異或。文檔中有如下說(shuō)明：
There is a tradeoff between speed, utility, and quality of bit-spreading.
因?yàn)闆]有完美的哈希算法可以徹底避免碰撞，所以只能盡可能減少碰撞，在各方面權(quán)衡之后得到一個(gè)折中方案，這里我們就不再追究了。
put方法的具體實(shí)現(xiàn)在putVal中，我們看下其實(shí)現(xiàn)：
// 參數(shù)onlyIfAbsent表示是否替換原值
// 參數(shù)evict我們可以忽略它，它主要用來(lái)區(qū)別通過(guò)put添加還是創(chuàng)建時(shí)初始化數(shù)據(jù)的
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)
// resize()不僅用來(lái)調(diào)整大小，還用來(lái)進(jìn)行初始化配置
n = (tab = resize()).length;
// (n - 1) & hash這種方式也熟悉了吧？都在分析ArrayDeque中有體現(xiàn)
//這里就是看下在hash位置有沒有元素，實(shí)際位置是hash % (length-1)
if ((p = tab[i = (n - 1) & hash]) == null)
// 將元素直接插進(jìn)去
tab[i] = newNode(hash, key, value, null);
else {
//這時(shí)就需要鏈表或紅黑樹了
// e是用來(lái)查看是不是待插入的元素已經(jīng)有了，有就替換
Node<K,V> e; K k;
// p是存儲(chǔ)在當(dāng)前位置的元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //要插入的元素就是p，這說(shuō)明目的是修改值
// p是一個(gè)樹節(jié)點(diǎn)
else if (p instanceof TreeNode)
// 把節(jié)點(diǎn)添加到樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 這時(shí)候就是鏈表結(jié)構(gòu)了，要把待插入元素掛在鏈尾
for (int binCount = 0; ; ++binCount) {
//向后循環(huán)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 鏈表比較長(zhǎng)，需要樹化，
// 由于初始即為p.next，所以當(dāng)插入第9個(gè)元素才會(huì)樹化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 找到了對(duì)應(yīng)元素，就可以停止了
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 繼續(xù)向后
p = e;
}
}
// e就是被替換出來(lái)的元素，這時(shí)候就是修改元素值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 默認(rèn)為空實(shí)現(xiàn)，允許我們修改完成后做一些操作
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// size太大，達(dá)到了capacity的0.75，需要擴(kuò)容
if (++size > threshold)
resize();
// 默認(rèn)也是空實(shí)現(xiàn)，允許我們插入完成后做一些操作
afterNodeInsertion(evict);
return null;
}
以上方法和我們開頭看到的文檔描述一致，在插入時(shí)可能會(huì)從鏈表變成紅黑樹。里面用到了TreeNode.putTreeVal方法向紅黑樹中插入元素，關(guān)于TreeNode的方法我們最后分析。除此之外，還有一個(gè)樹化的方法是treeifyBin，我們現(xiàn)在看下其原理：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果表是空表，或者長(zhǎng)度還不到樹化的最小值，就需要重新調(diào)整表了
// 這樣做是為了防止最初就進(jìn)行樹化
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;
// while循環(huán)的目的是把鏈表的每個(gè)節(jié)點(diǎn)轉(zhuǎn)為TreeNode
do {
// 根據(jù)當(dāng)前元素，生成一個(gè)對(duì)應(yīng)的TreeNode節(jié)點(diǎn)
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)
// 這里也用到了TreeNode的方法，我們?cè)谧詈笠黄鸱治? // 通過(guò)頭節(jié)點(diǎn)調(diào)節(jié)TreeNode
// 鏈表數(shù)據(jù)的順序是不符合紅黑樹的，所以需要調(diào)整
hd.treeify(tab);
}
}
無(wú)論是在put還是treeify時(shí)，都依賴于resize，它的重要性不言而喻。它不僅可以調(diào)整大小，還能調(diào)整樹化和反樹化（從樹變?yōu)殒湵恚┧鶐?lái)的影響。我們看看它具體做了哪些工作：
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) {
// 大小超過(guò)了2^30
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 擴(kuò)容，擴(kuò)充為原來(lái)的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 原來(lái)的threshold設(shè)置了
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 全部設(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ò)容完成，現(xiàn)在需要進(jìn)行數(shù)據(jù)拷貝，從原表復(fù)制到新表
@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)
// 這是只有一個(gè)值的情況
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 重新規(guī)劃樹，如果樹的size很小，默認(rèn)為6，就退化為鏈表
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 處理鏈表的數(shù)據(jù)
// loXXX指的是在原表中出現(xiàn)的位置
Node<K,V> loHead = null, loTail = null;
// hiXXX指的是在原表中不包含的位置
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//這里把hash值與oldCap按位與。
//oldCap是2的次冪，所以除了最高位為1以外其他位都是0
// 和它按位與的結(jié)果為0，說(shuō)明hash比它小，原表有這個(gè)位置
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);
// 掛在原表相應(yīng)位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 掛在后邊
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
刪除一個(gè)元素
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
和插入一樣，其實(shí)際的操作在removeNode方法中完成，我們看下其實(shí)現(xiàn)：
// matchValue是說(shuō)只有value值相等時(shí)候才可以刪除，我們是按照key刪除的，所以可以忽略它。
// movable是指是否允許移動(dòng)其他元素，這里是和TreeNode相關(guān)的
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;
// 不同情況下獲取待刪除的node節(jié)點(diǎn)
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刪除
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// 在隊(duì)首，直接刪除
tab[index] = node.next;
else
// 鏈表中刪除
p.next = node.next;
++modCount;
--size;
// 默認(rèn)空實(shí)現(xiàn)，允許我們刪除節(jié)點(diǎn)后做些處理
afterNodeRemoval(node);
return node;
}
}
return null;
}
獲取一個(gè)元素
除了增刪之外，重要的就是查詢操作了。查詢的get方法也是通過(guò)調(diào)用getNode方法完成的，我們看下其實(shí)現(xiàn)：
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;
}
這里邏輯和我們分析的增刪很類似，再讀起來(lái)就很簡(jiǎn)單了。
TreeNode方法介紹
在前面分析增刪時(shí)，可以發(fā)現(xiàn)與紅黑樹相關(guān)的操作都是通過(guò)TreeNode來(lái)實(shí)現(xiàn)的，下面我們就來(lái)看看TreeNode的具體實(shí)現(xiàn)：
TreeNode算上其繼承來(lái)的成員變量，共有11個(gè)：
final int hash;
final K key;
V value;
Node<K,V> next;
Entry<K,V> before, after;
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
這么多的變量，說(shuō)明其功能十分強(qiáng)大。這主要是因?yàn)樗枰跇浜玩湵碇g來(lái)回轉(zhuǎn)換。下面按照本文中出現(xiàn)的方法順序?qū)ζ浜瘮?shù)進(jìn)行分析。
首先是在添加元素時(shí)使用到了TreeNode.putTreeVal：
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節(jié)點(diǎn)
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
// dir表示查詢方向
int dir, ph; K pk;
// 要插入的位置在樹的左側(cè)
// 樹化會(huì)依據(jù)key的hash值
if ((ph = p.hash) > h)
dir = -1;
// 要插入的位置在樹的右側(cè)
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p; //找到了，替換即可
// comparableClassFor是如果key實(shí)現(xiàn)了Comparable就返回具體類型，否則返回null
// compareComparables是比較傳入的key和當(dāng)前遍歷元素的key
// 只有當(dāng)前hash值與傳入的hash值一致才會(huì)走到這里
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
//左右都查過(guò)了
searched = true;
// 通過(guò)hash和Comparable都找不到，只能從根節(jié)點(diǎn)開始遍歷
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;
}
// 元素的hashCode一致，且沒有實(shí)現(xiàn)Comparable，在樹里也沒有
// tieBreakOrder則是調(diào)用System.identityHashCode(Object o)來(lái)進(jìn)行比較，
//它的意思是說(shuō)不管有沒有覆寫hashCode，都強(qiáng)制使用Object類的hashCode
// 這樣做，是為了保持一致性的插入
dir = tieBreakOrder(k, pk);
}
// 代碼執(zhí)行到這，說(shuō)明沒有找到元素，也就是需要新建并插入了
TreeNode<K,V> xp = p;
// 經(jīng)歷過(guò)上述for循環(huán)，p已經(jīng)到某個(gè)葉節(jié)點(diǎn)了
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;
// moveRootToFront目的很明確也是必須的。
// 因?yàn)檫@個(gè)紅黑樹需要掛在數(shù)組的某個(gè)位置，所以其首個(gè)元素必須是root
// balanceInsertion是因?yàn)椴迦朐睾罂赡懿环霞t黑樹定義了
// 這部分知識(shí)在分析TreeMap中有詳細(xì)介紹
// 需要了解的話可以查看文末鏈接
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
除了putTreeVal之外，我們還調(diào)用過(guò)treeify以及removeTreeNode等方法。這些方法的過(guò)程都和putTreeVal類似，大家感興趣可以自己去分析，這里就不再介紹了。
增刪圖示
上面這些增刪的代碼都很抽象，即使加了大量的注釋，也很難以理解，這里做一個(gè)簡(jiǎn)單的示意圖，方便我們理解為何要這么做。這里需要一些紅黑樹調(diào)整的知識(shí)，大家可以參考文末關(guān)于TreeMap的文章鏈接。
刪除和增加類似，我們以增加為例：
起初，我們有一張table表，其中插入了一些數(shù)據(jù)。由于HashMap優(yōu)秀的設(shè)計(jì)，想要構(gòu)造出一個(gè)需要紅黑樹的表很難。我們假設(shè)插入的數(shù)據(jù)的key在table表相同位置的hash值都一致，且實(shí)現(xiàn)了Comparable接口。Comparable按照key的自然順序比較，圖中的數(shù)字都表示key值。這里數(shù)據(jù)都是不準(zhǔn)確的甚至可能會(huì)重復(fù)，我們只要理解目的即可。
圖中左側(cè)是hash算法完成后的hash值，中間是插入的內(nèi)容，有的位置還沒有數(shù)據(jù)，有的位置已經(jīng)插入了一些數(shù)據(jù)并變?yōu)榱随湵?，并且我們假設(shè)capacity已經(jīng)大于64（64是可以樹化的閾值）。如下圖所示：
為了完整的演示，現(xiàn)在我們向表中插入一個(gè)hash=6的值。由于6的位置現(xiàn)在是空的，所以元素會(huì)直接放在此處：
我們繼續(xù)插入一個(gè)hash=6的值，此時(shí)，6的位置已經(jīng)存在一個(gè)元素，所以新的元素會(huì)通過(guò)鏈表的方式鏈接在18的后邊，如下所示：
現(xiàn)在，我們?cè)俨迦霂讉€(gè)hash=6的值，直到達(dá)到鏈表變?yōu)榧t黑樹的閾值（默認(rèn)是8個(gè)）：
此時(shí)，在6的位置上有了8個(gè)元素。這時(shí)，我們要向其中加入一個(gè)9，就需要進(jìn)行樹化，用紅黑樹代替鏈表以提升查詢性能。
樹化時(shí)，先獲取第一個(gè)元素18，將其轉(zhuǎn)為TreeNode節(jié)點(diǎn)，并設(shè)置為head。然后把后續(xù)節(jié)點(diǎn)依次轉(zhuǎn)為TreeNode，并依次掛在head之后，他們的prev指向前一個(gè)元素，next指向后一個(gè)元素。掛完之后類似下圖：
轉(zhuǎn)為樹節(jié)點(diǎn)之后，需要通過(guò)head，也就是這里的18，來(lái)進(jìn)一步調(diào)整。首先，18就是root節(jié)點(diǎn)，顏色設(shè)置為黑色。然后比較18與20，它們的hash都一樣，所以會(huì)采用Comparable比較。這時(shí)20應(yīng)該在18的右邊。然后按照balanceInsertion方法此時(shí)不需要調(diào)整，所以18依然是root，且依然在table表的首位，結(jié)果如下：
然后再調(diào)整31，31在18的右側(cè)，結(jié)果如下：
這時(shí)候就破壞了紅黑樹了，按照在TreeMap中介紹的方法，需要進(jìn)行調(diào)整，這里不再展示過(guò)程，而直接展示結(jié)果了：
如果僅是一棵紅黑樹，到此調(diào)整就完畢了，但是這棵紅黑樹需要在table表中，所以其根節(jié)點(diǎn)必須在首位。我們看到，加入31以后，根節(jié)點(diǎn)由18變?yōu)榱?0，所以就需要按照moveRootToFront方法將root節(jié)點(diǎn)提前。這一操作并不會(huì)改變樹的結(jié)構(gòu)，僅僅是把新的root和原來(lái)的root在table表中的位置交換了一下，如下所示：
然后按照這樣的規(guī)則繼續(xù)調(diào)整剩下的元素，這些步驟和上述類似，最終調(diào)整結(jié)果如下：
總結(jié)
HashMap是目前分析的最復(fù)雜的集合類了。合理的使用它能夠在增刪改查等方面都有很好的表現(xiàn)。在使用時(shí)我們需要注意以下幾點(diǎn)：
設(shè)計(jì)的key對(duì)象一定要實(shí)現(xiàn)
hashCode方法，并盡可能保證均勻少重復(fù)。由于樹化過(guò)程會(huì)依次通過(guò)hash值、比較值和對(duì)象的hash值進(jìn)行排序，所以key還可以實(shí)現(xiàn)
Comparable，以方便樹化時(shí)進(jìn)行比較。如果可以預(yù)先估計(jì)數(shù)量級(jí)，可以指定initial capacity，以減少rehash的過(guò)程。
雖然HashMap引入了紅黑樹，但它的使用是很少的，如果大量出現(xiàn)紅黑樹，說(shuō)明數(shù)據(jù)本身設(shè)計(jì)的不合理，我們應(yīng)該從數(shù)據(jù)源尋找優(yōu)化方案。
相關(guān)文章
下一篇：Java集合源碼分析之Map（六）：LinkedHashMap
我是飛機(jī)醬，如果您喜歡我的文章，可以關(guān)注我~
編程之路，道阻且長(zhǎng)。唯，路漫漫其修遠(yuǎn)兮，吾將上下而求索。
