摘要：看屬性有一個，所以是紅黑樹的節點。會在鏈表過長的時候，將其重構成紅黑樹，這個看后面的代碼。如果是紅黑樹的話，調用紅黑樹的查找函數來最終找到這個節點。該位置為平衡樹。但是這導致鏈表增長，需要觸發鏈表重構成平衡樹的判斷邏輯。
hash表是應用最廣泛的數據結構，是對鍵值對數據結構的一種重要實現。
它能夠將關鍵字key映射到內存中的某一位置，查詢和插入都能達到平均時間復雜度為O(1)的性能。
HashMap是java對hash表的實現，它是非線程安全的，也即不會考慮并發的場景。
HashMap實現思路
hash表是常見的數據結構，大學都學過，以前也曾用C語言實現過一個：
https://github.com/frapples/c...
偷點懶，這里就大概總結一下了，畢竟這篇博文jdk代碼才是重點。
在使用者的角度來看，HashMap能夠存儲給定的鍵值對，并且對于給定key的查詢和插入都達到平均時間復雜度為O(1)。
實現hash表的關鍵在于：
對于給定的key，如何將其對應到內存中的一個對應位置。這通過hash算法做到。
通過一個數組保存數據，通過hash算法hash(K) % N來將關鍵字key映射數組對應位置上。
hash算法存在hash沖突，也即多個不同的K被映射到數組的同一個位置上。如何解決hash沖突？有三種方法。
分離鏈表法。即用鏈表來保存沖突的K。
開放定址法。當位置被占用時，通過一定的算法來試選其它位置。hash(i) = (hash(key) + d(i)) % N，i代表第i次試選。常用的有平方探測法，d(i) = i^2。
再散列。如果沖突，就再用hash函數再嵌套算一次，直到沒有沖突。
HashMap代碼分析
Node節點
先來看Node節點。這表明HashMap采用的是分離鏈表的方法實現。
Node為鏈表節點，其中存儲了鍵值對，key和value。
不過實際上，HashMap的真正思路更復雜，會用到平衡樹，這個后面再說。
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
/* ... */
}
還能發現，這是一個單鏈表。對于HashMap來說，單鏈表就已經足夠了，雙向鏈表反而多一個浪費內存的字段。
除此之外，還能夠注意到節點額外保存了hash字段，為key的hash值。
仔細一想不難明白，HashMap能夠存儲任意對象，對象的hash值是由hashCode方法得到，這個方法由所屬對象自己定義，里面可能有費時的操作。
而hash值在Hash表內部實現會多次用到，因此這里將它保存起來，是一種優化的手段。
TreeNode節點
這個TreeNode節點，實際上是平衡樹的節點。
看屬性有一個red，所以是紅黑樹的節點。
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
/* ... */
}
除此之外，還能發現這個節點有prev屬性，此外，它還在父類那里繼承了一個next屬性。
這兩個屬性是干嘛的？通過后面代碼可以發現，這個TreeNode不僅用來組織紅黑樹，還用來組織雙向鏈表。。。
HashMap會在鏈表過長的時候，將其重構成紅黑樹，這個看后面的代碼。
屬性字段
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node[] table;
transient Set> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
最重要的是table、size、loadFactor這三個字段：
table可以看出是個節點數組，也即hash表中用于映射key的數組。由于鏈表是遞歸數據結構，這里數組保存的是鏈表的頭節點。
size，hash表中元素個數。
loadFactor，裝填因子，控制HashMap擴容的時機。
至于entrySet字段，實際上是個緩存，給entrySet方法用的。
而modCount字段的意義和LinkedList一樣，前面已經分析過了。
最后，threshold這個字段，含義是不確定的，像女孩子的臉一樣多變。。。
坦誠的說這樣做很不好，可能java為了優化時省點內存吧，看后面的代碼就知道了，這里總結下：
如果table還沒有被分配，threshold為初始的空間大小。如果是0，則是默認大小，DEFAULT_INITIAL_CAPACITY。
如果table已經分配了，這個值為擴容閾值，也就是table.length * loadFactor。
構造函數
/**
* Constructs an empty HashMap with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
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;
}
第一個構造函數是重點，它接收兩個參數initialCapacity代表初始的table也即hash桶數組的大小，loadFactor可以自定義擴容閾值。
this.threshold = tableSizeFor(initialCapacity);
這里也用到了類似前面ArrayList的“延遲分配”的思路，一開始table是null，只有在第一次插入數據時才會真正分配空間。
這樣，由于實際場景中會出現大量空表，而且很可能一直都不添加元素，這樣“延遲分配”的優化技巧能夠節約內存空間。
這里就體現出threshold的含義了，hash桶數組的空間未分配時它保存的是table初始的大小。
tableSizeFor函數是將給定的數對齊到2的冪。這個函數用位運算優化過，我沒怎么研究具體的思路。。。
但是由此可以知道，hash桶數組的初始大小一定是2的冪，實際上，hash桶數組大小總是為2的冪。
get函數
hash二次運算
先從get函數看起。
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
我們發現，調用getNode時：
return (e = getNode(hash(key), key)) == null ? null : e.value;
其中調用了hash這個靜態函數：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
也就是說，用于HashMap的hash值，還需要經過這個函數的二次計算。那這個二次計算的目的是什么呢？
通過閱讀注釋：
Computes key.hashCode() and spreads (XORs) higher bits of hash
to lower. Because the table uses power-of-two masking, sets of
hashes that vary only in bits above the current mask will
always collide. (Among known examples are sets of Float keys
holding consecutive whole numbers in small tables.) So we
apply a transform that spreads the impact of higher bits
downward. There is a tradeoff between speed, utility, and
quality of bit-spreading. Because many common sets of hashes
are already reasonably distributed (so don"t benefit from
spreading), and because we use trees to handle large sets of
collisions in bins, we just XOR some shifted bits in the
cheapest possible way to reduce systematic lossage, as well as
to incorporate impact of the highest bits that would otherwise
never be used in index calculations because of table bounds.
嗯。。。大概意思是說，由于hash桶數組的大小是2的冪次方，對其取余只有低位會被使用。這個特點用二進制寫法研究一下就發現了：如1110 1100 % 0010 0000 為 0000 1100，高位直接被忽略掉了。
也即高位的信息沒有被利用上，會加大hash沖突的概率。于是，一種思路是把高位的信息混合到低位上去，提高區分度。就是上面這個hash函數了。
getNode函數
final Node getNode(int hash, Object key) {
Node[] tab; Node 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)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;
}
get函數調用了getNode，它接受給定的key，定位出對應的節點。這里檢查了table為null的情況。此外first = tab[(n - 1) & hash]實際上就是first = tab[hash % n]的優化，這個細節太多，等會再分析。
代碼雖然有點多，但是大部分都是一些特別情況的檢查。首先是根據key的hash值來計算這個key放在了hash桶數組的哪個位置上。找到后，分三種情況處理：
這個位置上只有一個元素。
這個位置上是一個鏈表。
這個位置上是一棵紅黑樹。
三種情況三種不同的處理方案。比較奇怪的是為什么1不和2合并。。。
如果是紅黑樹的話，調用紅黑樹的查找函數來最終找到這個節點。
如果是鏈表的話，則遍歷鏈表找到這個節點。值得關注的是對key的比較：
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
類似于hashCode方法，equals方法也是所屬對象自定義的，比較可能比較耗時。
所以這里先比較Node節點保存的hash值和引用，這樣盡量減少調用equals比較的時機。
模運算的優化
回到剛才的位運算：
first = tab[(n - 1) & hash]
這個位運算，實際上是對取余運算的優化。由于hash桶數組的大小一定是2的冪次方，因此能夠這樣優化。
思路是這樣的，bi是b二進制第i位的值：
b % 2i = (2NbN + 2N-1 bN-1+ ... + 2ibi + ... 20b0) % 2i
設x >= i，則一定有2xbx % 2i = 0
所以，上面的式子展開后就是：
b % 2i = 2i-1bi-1 + 2i-2bi-2 + ... 20b0
反映到二進制上來說，以8位二進制舉個例子：
顯然2的冪次方N的二進制位是只有一個1的。8的二進制為00001000，1在第3位。
任何一個數B余這個數N，反映二進制上，就是高于等于第3位的置0，低于的保留。如10111010 % 00001000 = 00000010
這樣，就不難理解上面的(n - 1) & hash了。以上面那個例子，
00001000 - 1 = 00000111，這樣減一之后，需要保留的對應位為全是1，需要置0的對應位全都是0。把它與B作與運算，就能得到結果。
put函數
沒想到寫這個比想象中的費時間。。。還有很多其他事情要做呢
這個put函數太長了，容我偷個懶直接貼代碼和我自己的注釋吧
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// onlyIfAbsent含義是如果那個位置已經有值了，是否替換
// evict什么鬼？table處于創造模式？先不管
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// table為null或者沒有值的時候reisze()，因此這個函數還負責初始分配
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 定位hash桶。如果是空鏈表的話（即null），直接新節點插入：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
// 如果hash桶掛的是二叉樹，調用TreeNode的putTreeVal方法完成插入
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
// 如果掛的是鏈表，插入實現
// 遍歷鏈表，順便binCount變量統計長度
for (int binCount = 0; ; ++binCount) {
// 情況一：到尾巴了，就插入一條
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 插入會導致鏈表變長
// 可以發現，TREEIFY_THRESHOLD是個閾值，超過了就調用treeifyBin把鏈表換成二叉樹
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;
// 如果hash桶數組的大小超過了閾值threshold，就resize()，可見resize負責擴容
if (++size > threshold)
resize();
// evice的含義得看afterNodeInsertion函數才能知道
afterNodeInsertion(evict);
return null;
}
思路大概是這樣的邏輯：
判斷table是否分配，如果沒有就先分配空間，和前面提到的“延時分配”對應起來。
同樣，根據hash值定位hash桶數組的位置。然后：
該位置為null。直接創建一個節點插入。
該位置為平衡樹。調用TreeNode的一個方法完成插入，具體邏輯在這個方法里。
該位置為鏈表。遍歷鏈表，進行插入。會出現兩種情況：
遍歷到鏈表尾，說明這個key不存在，應該直接在鏈表尾插入。但是這導致鏈表增長，需要觸發鏈表重構成平衡樹的判斷邏輯。
找到一個key相同的節點，多帶帶拎出來處理，得看onlyIfAbsent的參數。
完畢之后，這個時候hash表中可能多了一個元素。也只有多了一個元素的情況下控制流才能走到這。這時維護size字段，并且觸發擴容的判斷邏輯。
在這里我有幾點疑惑：
為什么null的情況、一個節點的情況、單鏈表的情況不合并在一起處理？因為性能？
為什么采用尾插法不用頭插法？頭插法根據局部性原理豈不是更好嗎？
在遍歷鏈表時會同時統計鏈表長度，然后鏈表如果被插入，會觸發樹化邏輯：
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
TREEIFY_THRESHOLD的值是8，也就是說，插入后的鏈表長度如果超過了8，則會將這條鏈表重構為紅黑樹，以提高定位性能。
在插入后，如果hash表中元素個數超過閾值，則觸發擴容邏輯：
if (++size > threshold)
resize();
記得前面說過，threshold在table已經分配的時候，代表是擴容閾值，即table.length * loadFactor。
最后
考慮到篇幅夠長了，還是拆分成兩篇比較好，剩下的留到下一篇博文再寫吧。
