摘要：看属性有一个，所以是红黑树的节点。会在链表过长的时候，将其重构成红黑树，这个看后面的代码。如果是红黑树的话，调用红黑树的查找函数来最终找到这个节点。该位置为平衡树。但是这导致链表增长，需要触发链表重构成平衡树的判断逻辑。
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。
最后
考虑到篇幅够长了，还是拆分成两篇比较好，剩下的留到下一篇博文再写吧。
