jdk1.8 HashMap 的数据结构是数组+链表+红黑树,因为HashMap不是线程安全的，所以暂时不需要考虑多线程操作。
看HashMap源码前，考虑几个问题：
1、数组初始容量多大，最大容量多大
2、如何计算Hash值，如何尽量避免Hash冲突
3、数组如何扩容,扩容之后原数组的内容如何copy
4、链表到多大后才转成红黑树，如果红黑树小于一定数量会不会再变回链表
5、为啥允许空key ? 在哪里怎么实现的？
为了描述方便下文中：数组中每个节点简称为桶
1、HashMap 初始化
1、定义：
静态字段：默认值
实例字段：存储数组，元素数量，扩容阀值，迭代工具
2、构造函数
初始化 loadFactor 负载因子默认 DEFAULT_LOAD_FACTOR （0.75）
3、计算扩容阀门
注意：这里没有创建数组
/* ---------------- Static 默认值-------------- */
//默认数组大小 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4
//最大数组容量 1073741824
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;
/* ---------------- Fields 每个HashMap 实例都有特有的值-------------- */
//这个最重要：即所谓的Hash数组
transient Node<K,V>[] table;
//当调用 entrySet() 是返回一个 EntrySet 引用指向所有 Map.Entry<K,V> （Node）
transient Set<Map.Entry<K,V>> entrySet;
//元素数量
transient int size;
//modCount用于记录HashMap的修改次数,在 put(),get(),remove(),Interator()等方法中,都使用了该属性
transient int modCount;
//扩容阀值
int threshold;
//负载因子
final float loadFactor;
/* ---------------- 从 AbstractMap 继承过来的------------- */
//Set 的 Iterator 是调用 entrySet() 返回一个 EntrySet.iterator() 即 EntryIterator
//Set 的 Iterator.next() 等同于 EntryIterator.next().getKey()
transient Set<K> keySet;
//和 keySet 原理一样
//Collection 的 Iterator.next() 等同于 EntryIterator.next().getValue()
transient Collection<V> values;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//NaN = 0.0f / 0.0f;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
(1)、计算扩容阀值 tableSizeFor(initialCapacity)
计算扩容阀值 tableSizeFor(initialCapacity) 看到这里有许多同学可能感到奇怪，因为入参 initialCapacity 参数英文含义是初始容量，正常理解应该是 Hash 数组容量，但是这里规格化后赋值给了 threshold 扩容阀值，扩容阈值应该等于 initialCapacity * DEFAULT_LOAD_FACTOR(0.75) 呀？ 别急请看下文。
这个规格化函数也是比较有意思的。
例如：入参二进制数 100010111
看如下代码
//入参 cap = 100010111
static final int tableSizeFor(int cap) {
//n= 100010110
int n = cap - 1;
// n >>> 1 = 010001011 n = 100010110 | 010001011 = 110011111 保证前2位是1
n |= n >>> 1;
// n >>> 2 = 001100111 n = 110011111 | 001100111 = 111111111 保证前4位是1
n |= n >>> 2;
//n >>> 4 = 000011111 n = 111111111 | 000011111 = 111111111 保证前8位是1
n |= n >>> 4;
//n >>> 8 = 000000001 n = 111111111 | 000000001 = 111111111 保证前16位是1
n |= n >>> 8;
//n >>> 16 = 000000000 n = 111111111 | 000000000 = 111111111 保证前32位是1 int 最大就32位所以结束
n |= n >>> 16;
//这里判断最大容量，然后将第一步减掉的 1 这里加回来
//111111111 + 1 = 1000000000 最高位是1其他位都是 0 必然是 2 的倍数，而且还是最接近入参的 2 的倍数
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
此处可以继续提出问题：上边看到数组长度规格化为 2 的幂次方数，为什么？有什么好处
注意：至此初始化已经结束了,但是还没有创建数组，因为创建数组这个消耗动作延迟到了，真正添加值的时候了。
2、put() 方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
在这里我们看到了最想看到的计算 Hash 值的方法
2.1、获取 key 的 hashCode
hashCode 方法是 object 类中的方法，如果子类不覆盖，那么会调用native 方法，返回值 int 二进制 32 位。并且高16 位与自己的低16位做异或运算---相同为0不同为1，因为这样可以减少一些 hash 冲突。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看一下数组下标的计算方法
//n 为当前数组的大小
n = tab.length
// 将(数组的长度-1)和 hash 值进行按位与操作:
i = (n - 1) & hash
（1）为啥用数组长度n - 1 & hash 确定下标呢？ 而不是常用的方法 n % hash。
数组长度是 2 的幂次方，所以数组长度 n 的二进制表示形式的最高有效位是1，其他位都是零。
例如：
8 二进制 : 1000 , 8-1 =7 二进制 111
16 二进制 :10000 ,16-1 = 15 二进制 1111
32 二进制: 100000 ,32-1 = 31 二进制 11111
因为 & 位运算符，参与运算的两个位都为 1 才是 1，否则为0，所以 111（7） & 任何数相当于截取二进制中的三位。肯定小于等于 111（7）。所以HashMap用这种方式代替了 n % hash ,效率高很多。
（2）为啥 (h = key.hashCode()) ^ (h >>> 16) 这样计算Hash，为什么不直接用 hashCode() 的返回值呢？
假设：hashCode() 返回十进制int 数 h=45880 ，hash数组长度位 n =16
根据上图的演算发现：
（1）HashCode 中有多少位参与定位数组下标的运算，由数组的长度决定的。因为本例中数组长度为 16 位所以参与运算的 hash 值的二进制位数为四位。
（2）如果直接拿 HashCode 计算下标 ，那么不管高位是什么，只有后四位参与了数组下标的定位的运算之中，冲突的概率相对较高。
（3）如果按照 (h = key.hashCode()) ^ (h >>> 16) 方式计算数组下标，高16位的后四位，和低16位的后四位都可以参与数组下表的定位的运算之中，冲突概率相对低一些。
注意：0-16 位二进制正整数，最大可以表示十进制 65535 。
如果 hashCode 方法返回值小于 65535 那么意味着 (h = key.hashCode()) ^ (h >>> 16) 和 key.hashCode() 相等，所以只有hashCode 大于 65535 的值此计算才有效
（3）为啥允许空key ？在哪里怎么实现的？
这里可以回答了，因为 hash 方法 (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) 这里返回了 0 ， 0 & 数组长度-1。都等于0，所以hash数组的第一个位置会存放 key 为 null 的元素。
2.2 数组长度n为啥是 2 的幂次方数
1、因为计算数组下标方法 n - 1 & hash 运算后得到的结果随机且均匀的分布到数组中。上文已经讲过了。
假设一个不是 2 的幂次方数，13 二进制为 1101，
（1101 - 1）& hash = 1100 & hash
计算结果：可能是 100，1000，1100 只能是这三种。
可想而知这种算法肯定不合格，用二的幂次方 - 1 & hash 运算会存在更多的可能性。
2、避免扩容时重复计算数组中的位置
在扩容时，扩容之后数组长度是原数组长度的两倍，因为原数组是 2 的幂次方，所以扩容后同样为 2 的幂次方。
假设原数组长度为 8 扩容后数组长度为 16
8 二进制 : 1000 , 8-1 =7 二进制 111
16 二进制 :10000 ,16-1 = 15 二进制 1111
因为扩容时数据要从原数组迁移到新数组
假设原数组内有数据 13 二进制为 1101
在原数组的位置是 1101 & 111 = 101 等于十进制的 5
在新数组的位置是 1101 & 1111= 1101 等于十进制的 13
根据例子可以观察出，新数组的位置有两种可能
- 和原数组的位置相等
- 原数组位置（101） + 1000 等于十进制 13。1000 这个值，可以由新数组长度16除2得到。
那如何区分这两种情况呢，其实很简单，就是判断 hash 值中新的参与确定下标计算的位是否是零即可，hash & (新数组长度<<1) 如果等于 0 那么数组位置不变，否则将原数组位置加上新数组长度除2得到。
2.3 putVal 方法
1、如果 hash 数组为空，即第一次添加key,value 那么初始化数组
2、计算数组下标 i = (n - 1) & hash 如果下标对应的数组值为空，那么直接创建节点并且放入到数组中
3、处理 hash 冲突的情况
4、累计 size
5、扩容
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;
//是否存在 hash 冲突
if ((p = tab[i = (n - 1) & hash]) == null)
//创建节点 并且放入数组
tab[i] = newNode(hash, key, value, null);
else {
/ 处理 hash 冲突的情况
............
}
++modCount;
//超过阀值扩容
if (++size > threshold)
resize();
//给客户一个，插入成功的扩展点
afterNodeInsertion(evict);
return null;
}
（1) 处理 hash 冲突的情况
1、入参和头节点的 key.hash 值，key.equals 是否相同。
2、如果hash 冲突的位置已经是红黑树了，那么插入树节点
3、否则从链表位部插入节点
4、如果超过阈值转红黑树
5、将key的hash值相同，并且 equals 也相同，的value替换成新value,然后将旧 value 返回
Node<K,V> e; K k;
//入参和头节点的 key.hash值，key.equals 是否相同
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);
//是否超过了链表转红黑树的阀值，应为从0开始所以减1
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//转红黑树
treeifyBin(tab, hash);
break;
}
//如果 key.hash 值，key.equals 相同
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//处理 key.hash 值且 key.equals 相同的数据
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//如果重复添加数据，触发客户端定义的方法
afterNodeAccess(e);
return oldValue;
}
（2) 转红黑树 treeifyBin(tab, hash) 方法
1、如果数组长度小于 64 MIN_TREEIFY_CAPACITY 那么不进行树化，而是直接进行扩容
2、将单向链表转化成 TreeNode ，然后将 TreeNode 连接成双向链表
3、将 TreeNode 树化成，红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果数组长度小于 64 MIN_TREEIFY_CAPACITY 那么不进行树
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 {
//循环将 Node 转换成 TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
//将 TreeNode 连接成双向链表
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);
}
}
关于红黑树的操作，下次讲。
这里可以考虑一下为啥将 TreeNode 连接成双向链表
（3) 扩容 resize 方法
1、根据情况计算新数组 newCap 长度。newThr 扩容阀
（1）老数组没有创建过，即第一次put 那么获取初始化的参数
（2）老数组创建过，那么根据老数组长度、扩容阈值计算新数组的newCap 长度。newThr 扩容阀值。
2、创建新数组
3、数据迁移
（1）如果老数组节点中只有一个值，即不存在hash冲突，计算数组中的位置然后，直接放入新数组
（2）老数组节点，是树节点，对树节点迁移，这个下个章将
（3）老数组节点，是链表节点，迁移链表
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//旧数组的长度。 因为这里有第一次添加 key,value 需要新创建数组的情况
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧数组的扩容阈值。 如果第一此创建数组 threshold 等于数组长度
int oldThr = threshold;
//newCap 新数组长度，newThr 新数组扩容阀值
int newCap, newThr = 0;
//如果老数组已经创建过
if (oldCap > 0) {
//数组长度最大值校验
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//新数组长度=老数组长度 * 2 。 如果新数组长度 < 最大长度限制，那么新数组扩容阈值 = 老数组扩容阈值 * 2
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
//看到这里就可以解答了： 为啥 HashMap 初始化时候入参 initialCapacity 规格化后赋值给 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;
//创建新数组
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;
//如果老数组节点中只有一个值，即不存在hash冲突
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 老数组节点为链表节点
..................
}
}
}
}
return newTab;
}
（3) 链表节点，数据迁移
理论知识在上文 “ 数组长度n为啥是 2 的幂次方数” 中讲过了
1、创建4个变量，将位置变化的和位置没变化的节点穿成两条线
（1）loHead , loTail 用于迁移位置没有改变的元素
（2）hiHead , hiTail 用于迁移位置发生变化的元素
2、判断节点的位置是在原位置，还是在新位置。(e.hash & oldCap)
3、将拆分好的链表数据 loHead 和 hiHead 放入到新数组中
//用于迁移位置没有改变的元素
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;
//新位置计算方法 j + oldCap 在上文讲过
newTab[j + oldCap] = hiHead;
}
（3) 树节点，数据迁移 （即双向链表的数据迁移）
1、和迁移单向链表逻辑差不多
2、维护位置发生变化的，和位置未发生变化的双向链表
3、判断迁移后的树节点的数量是否小于阀值 6，如果小于退化成为普通链表。
4、否则重新构建新的二叉树
//入参 bit 是老数组长度，tab 为新数组，j 为老数组中的节点位置
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
//用于迁移位置没有改变的元素
TreeNode<K,V> loHead = null, loTail = null;
// 用于迁移位置发生变化的元素
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//向后循环直到链表结束
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
//判断节点的位置，是否发生变化
if ((e.hash & bit) == 0) {//位置没变化
//e.prev = loTail 向前指
//是否第一个位置没发生变化的元素
if ((e.prev = loTail) == null)
loHead = e;
else
//向后指
loTail.next = e;
loTail = e;
++lc;
}
else {//位置发生变化
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
//判断树节点的数量是否小于阀值，如果小于退化成为普通链表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
这里可以回答，为啥将 treeNode 构建成双向链表了，因为其中一个原因是，迁移时候方便。
