HashMap是Java开发中常用的数据结构，了解它的内部实现有助于更好的使用它，Java8中的HashMap由三种数据结构组成：数组、链表、红黑树
内部存储
HashMap的内部存储是一个数组（bucket），数组的元素Node实现了是Map.Entry接口(hash, key, value, next)，next非空时指向定位相同的另一个Entry，如图:
内部主要特点：
- 使用哈希表进行数据存储，使用链地址法解决哈希碰撞
- 当链表的长度大于等于8时，讲链表转成红黑树存储
- 每次进行二次幂的扩容，即扩容为原容量的两倍
存储机制
hash(Object key)方法
HashMap便是通过Object类中的hashCode()方法，来确定key在数组下标位置的，Java 8 之前的做法和现在的有所不同，Java 8 对此进行了改进，优化了该算法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以注意到，HashMap并不是直接通过hashCode()方法来当作散列值的，而是通过hash方法来做无符号右移和异或处理后的结果当作散列值，这样做的好处是避免了哈希碰撞。
上图的计算方式可以看出，key的哈希值高16位不变，低16位与高16位进行异或（相同位数的数值进行比较，相等则取0，不等则取1）运算，然后通过
(n - 1) & hash
来得到数组中元素的下标位置。
很显然，这种计算方式决定了元素的位置只关系到低位的数值，这样会使得哈希碰撞出现的可能性增加，因此我们利用 hash 值高位与低位的异或处理来降低冲突的可能性，使得元素的位置不单单取决于低位
put(K key, V value)
put方法是HashMap中十分重要的方法，关系到HashMap的存储问题。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put方法调用了putVal方法，解释如下：
//这里onlyIfAbsent表示只有在该key对应原来的value为null的时候才插入，也就是说如果value之前存在了，就不会被新put的元素覆盖。
//evict参数用于LinkedHashMap中的尾部操作，这里没有实际意
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//定义变量tab是将要操作的Node数组引用，p表示tab上的某Node节点，n为tab的长度，i为tab的下标。
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断当table为null或者tab的长度为0时，即table尚未初始化，此时通过resize()方法得到初始化的table。
if ((tab = table) == null || (n = tab.length) == 0)
//判断hash表是否为空，若为空，初始化哈希表
n = (tab = resize()).length;
//此处通过（n - 1） & hash 计算出的值作为tab的下标i，并另p表示tab[i]，也就是该链表第一个节点的位置。并判断p是否为null。
if ((p = tab[i = (n - 1) & hash]) == null)
//当p为null时，表明tab[i]上没有任何元素，那么接下来就new第一个Node节点，调用newNode方法返回新节点赋值给tab[i]。
tab[i] = newNode(hash, key, value, null);
else {
//下面进入p不为null的情况，有三种情况：p为链表节点；p为红黑树节点；p是链表节点但长度为临界长度TREEIFY_THRESHOLD，再插入任何元素就要变成红黑树了。
Node<K,V> e; K k;
//HashMap中判断key相同的条件是key的hash相同，并且符合equals方法。这里判断了p.key是否和插入的key相等，如果相等，则将p的引用赋给e。
//这一步的判断其实是属于一种特殊情况，即HashMap中已经存在了key，于是插入操作就不需要了，只要把原来的value覆盖就可以了。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//这里为什么要把p赋值给e，而不是直接覆盖原值呢？答案很简单，现在我们只判断了第一个节点，后面还可能出现key相同，所以需要在最后一并处理。
e = p;
//现在开始了第一种情况，p是红黑树节点，那么肯定插入后仍然是红黑树节点，所以我们直接强制转型p后调用TreeNode.putTreeVal方法，返回的引用赋给e。
else if (p instanceof TreeNode)
//你可能好奇，这里怎么不遍历tree看看有没有key相同的节点呢？其实，putTreeVal内部进行了遍历，存在相同hash时返回被覆盖的TreeNode，否则返回null。
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//接下里就是p为链表节点的情形，也就是上述说的另外两类情况：插入后还是链表/插入后转红黑树。另外，上行转型代码也说明了TreeNode是Node的一个子类。
else {
//我们需要一个计数器来计算当前链表的元素个数，并遍历链表，binCount就是这个计数器。
for (int binCount = 0; ; ++binCount) {
//遍历过程中当发现p.next为null时，说明链表到头了，直接在p的后面插入新的链表节点，即把新节点的引用赋给p.next，插入操作就完成了。注意此时e赋给p。
if ((e = p.next) == null) {
//最后一个参数为新节点的next，这里传入null，保证了新节点继续为该链表的末端。
p.next = newNode(hash, key, value, null);
//插入成功后，要判断是否需要转换为红黑树，因为插入后链表长度加1，而binCount并不包含新节点，所以判断时要将临界阈值减1。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//当新长度满足转换条件时，调用treeifyBin方法，将该链表转换为红黑树。
treeifyBin(tab, hash);
//当然如果不满足转换条件，那么插入数据后结构也无需变动，所有插入操作也到此结束了，break退出即可。
break;
}
//在遍历链表的过程中，我之前提到了，有可能遍历到与插入的key相同的节点，此时只要将这个节点引用赋值给e，最后通过e去把新的value覆盖掉就可以了。
//老样子判断当前遍历的节点的key是否相同。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//找到了相同key的节点，那么插入操作也不需要了，直接break退出循环进行最后的value覆盖操作。
break;
//在第21行我提到过，e是当前遍历的节点p的下一个节点，p = e 就是依次遍历链表的核心语句。每次循环时p都是下一个node节点。
p = e;
}
}
//左边注释为jdk自带注释，说的很明白了，针对已经存在key的情况做处理。
if (e != null) { // existing mapping for key
//定义oldValue，即原存在的节点e的value值。
V oldValue = e.value;
//前面提到，onlyIfAbsent表示存在key相同时不做覆盖处理，这里作为判断条件，可以看出当onlyIfAbsent为false或者oldValue为null时，进行覆盖操作。
if (!onlyIfAbsent || oldValue == null)
//覆盖操作，将原节点e上的value设置为插入的新value。
e.value = value;
//这个函数在hashmap中没有任何操作，是个空函数，他存在主要是为了linkedHashMap的一些后续处理工作。
afterNodeAccess(e);
//这里很有意思，他返回的是被覆盖的oldValue。我们在使用put方法时很少用他的返回值，甚至忘了它的存在，这里我们知道，他返回的是被覆盖的oldValue。
return oldValue;
}
}
//收尾工作，值得一提的是，对key相同而覆盖oldValue的情况，在前面已经return，不会执行这里，所以那一类情况不算数据结构变化，并不改变modCount值。
++modCount;
//同理，覆盖oldValue时显然没有新元素添加，除此之外都新增了一个元素，这里++size并与threshold判断是否达到了扩容标准。
if (++size > threshold)
//当HashMap中存在的node节点大于threshold时，hashmap进行扩容。
resize();
//这里与前面的afterNodeAccess同理，是用于linkedHashMap的尾部操作，HashMap中并无实际意义。1
afterNodeInsertion(evict);
//最终，对于真正进行插入元素的情况，put函数一律返回null。
return null;
}
扩容机制
resize()方法
此方法在第一次put时调用进行初始化并分配内存空间，第一次put时调用进行初始化并分配内存空间
/**
* 1.初始化：根据构造函数传递过来的参数和默认参数初始化table，第一次put时调用进行初始化并分配内存空间
* 由于超出threshold,对原数据进行两倍扩容
*/
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) {
//如果旧容量到达最大容量限制，则不进行扩容，而是修改threshold的值为最大整数值。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果没有超过容量限制，则讲容量扩大2倍，扩大后在进行最大最小容量判断
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//同时将threshold也进行两倍扩大
newThr = oldThr << 1; // double threshold
}
//-------------------------------旧数组长度为0，初始化操作-------------------------------
//判断构造函数中指定的容量
else if (oldThr > 0) // initial capacity was placed in threshold
//将构造函数中指定的长度initialCapacity赋值给新的容量
newCap = oldThr;
//为0则表示调用HashMap无参构造方法，则使用默认参数
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;
//-------------------------------根据新计算的容量进行扩容-----------------------------
//创建新容量的数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//1.如果旧数组为null，则说明这是在初始化table
// table为上面代码创建的，里面没有元素则不需要复制转移
//2.如果旧数组不为null，则需要进行元素节点赋值转移
if (oldTab != null) {
//遍历每个桶节点
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//桶节点不为null
if ((e = oldTab[j]) != null) {
//则赋值给null，帮助垃圾回收
oldTab[j] = null;
//若桶节点只有一个元素，则直接赋值到新数组中
if (e.next == null)
//将e的哈希值和新数组的长度进行取模计算新的数组索引
newTab[e.hash & (newCap - 1)] = e;
//判断桶节点是否为树节点
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//桶节点为链表节点
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//遍历桶节点的单项链表
do {
next = e.next;
//判断hash和oldCap的最高位上的1对应的位上是0还是1
//是0，则重新hash后再新数组的索引位置保持不变
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//是1，则重新计算后再新数组的位置上为 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//将上面判断对应位为1的单向链表的head节点
//插入到新数组的原索引位置上
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//将上面判断对应位为1的单向链表的head节点
//插入到新数组(原索引+oldCap)位置上
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}