在平常的开发过程中，我们会使用到HashMap处理key-value数据结构类型的数据，那么需要深入理解一些HashMap的原理。
- HashMap初始容量，扩容倍数
- HashMap 1.7 Hash碰撞，以及如何解决Hash碰撞
- HashMap1.8 数组 + 链表 + 红黑树
- HashMap常见主要方法执行流程
1. Java1.7中的HashMap
1.1 hashMap 数据结构
在jdk1.8中HashMap 主要包含了table数组+Entry<k,v>
1.2 hashMap 加载因子、阀值
HashMap默认的加载因子是0.75， 阀值 = 加载因子 * 数组容量，达到阀值得时候将会进行数组的扩容。
1.2.1 加载因子为什么是0.75？
作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了很好的折中。较高的值会降低空间开销，但提高查找成本（体现在大多数的HashMap类的操作，包括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。
1.2.2 为什么数组容量一定是2的指数幂？
1.3 resize扩容机制
2. Java1.8中的HashMap
2.1 数据结构
在jdk1.8中HashMap 主要包含了table数组+Node<k,v>（链表）+TreeNode(红黑树)
2.2 resize扩容机制
在java8中Hashmap扩容机制避免了在jdk1.7中需要进行rehash，重新确定在新数组中的位置，1.7的时候进行rehash在高并发的场景下容易造成死循环，死锁。在java8中的Hashmap引入了高位低位指针避免了进行rehash。
2.3 高位指针
- 判断key的hash值与扩容前数组容量进行位运算不为0时表示是高位指针
- 高位指针在新数组中的位置是在就数组中的索引+旧数组容量
2.4 低位指针
- 判断key的hash值与扩容前数组容量进行位运算为0时表示是低位指针
- 低位指针在新数组中的位置和以前在就数组中的索引位置一致
do {
next = e.next;
// 判断key的hash值与扩容前数组容量进行位运算为0时表示是低位指针
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 判断key的hash值与扩容前数组容量进行位运算不为0时表示是高位指针
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;
}
}
2.5 put方法执行流程
1.判断哈希表Node<K,V>[] table是否为空或者null，是则执行resize()方法进行扩容。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
2.根据插入的键值key的hash值，通过(n - 1) & hash当前元素的hash值 & hash表长度 - 1（实际就是 hash值 % hash表长度） 计算出存储位置table[i]。如果存储位置没有元素存放，则将新增结点存储在此位置table[i],其中n表示的 是table数组的长度。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
....
3.如果存储位置已经有键值对元素存在，则判断该位置元素的hash值和key值是否和当前操作元素一致，一致则证明是修改value操作，覆盖value即可。
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
4.当前存储位置即有元素，又不和当前操作元素一致，则证明此位置table[i]已经发生了hash冲突，则通过判断头结点是否是treeNode，如果是treeNode则证明此位置的结构是红黑树，已红黑树的方式新增结点。
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
5.如果不是红黑树，则证明是单链表，将新增结点插入至链表的最后位置，随后判断当前链表长度是否 大于等于 8，是则将当前存储位置的链表转化为红黑树。遍历过程中如果发现key已经存在，则直接覆盖value。
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//新增节点插入链表最后
p.next = newNode(hash, key, value, null);
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;
}
6.插入成功后，判断当前存储键值对的数量 大于 阈值threshold 是则扩容。
if (++size > threshold)
resize();
2.6 get方法执行流程
1.先调用 hash(key)方法计算出 key 的 hash值
getNode(hash(key), key)
2.根据查找的键值key的hash值，通过(n - 1) & hash当前元素的hash值 & hash表长度 - 1（实际就是 hash值 % hash表长度） 计算出存储位置table[i]，判断存储位置是否有元素存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
3.首先判断链表头结点是否相等，如果hash值、key值相等则返回头结点
//判断头结点的hash值与当前key的hash值是否相等和key是否相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
4.判断头结点的下一结点是否为空，如果不为空的话则判断是否为TreeNode ，如果是TreeNode的话则通过红黑树的方式获取数据
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
5.如果头结点的后续结点不是红黑树是链表的话，则遍历链表中的数据，如果有则返回，没有则返回null
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
2.7 remove 方法执行流程
1.首先计算key的hash值
e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
2.通过数组容量-1 & key的hash值计算出当前这个key在table数组中的索引位置
// 判断 table不为空，并且table[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;
3.判断当前节点是否是头节点，如果是头结点则给要删除的node赋值
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 判断是头结点则进行赋值
node = p;
4.如果不是头结点则继续判断后续结点，判断是否是红黑树，如果为红黑树则用红黑树的方式进行查找
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
5.如果不是红黑树则遍历链表
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);
}
6.如果找到要删除的结点node，则判断是否需要比较value也是否一致，如果value值一致或者不需要比较value值，则执行删除结点操作，删除操作根据不同的情况与结构进行不同的处理。 如果当前结点是树结点，则证明当前位置的链表已变成红黑树结构，通过红黑树结点的方式删除对应结点。 如果不是红黑树，则证明是单链表。如果要删除的是头结点，则当前存储位置table[i]的头结点指向删除结点的下一个结点。 如果要删除的结点不是头结点，则将要删除的结点的后继结点node.next赋值给要删除结点的前驱结点的next域，即p.next = node.next;。
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
7.删除完成之后size-1，并且返回当前删除的node
--size;