共计 3883 个字符，预计需要花费 10 分钟才能阅读完成。
HashMap 在面试中经常会被问到，一定会问到它的存储结构和实现原理，甚至可能还会问到一些源码
今天就来看一下 HashMap
首先得看一下 HashMap 的存储结构和底层实现原理
如上图所示，HashMap 底层是用数组 + 链表 + 红黑树实现的，其中红黑树是 JDK1.8 对 HashMap 优化之后加入的，当链表的长度大于 8 的时候会由链表结构转为红黑树，这些等下在看源码分析的时候都可以看到具体的实现。
那为什么用这几种数据结构来实现？
这种结构在数据结构上称为 散列链表，其中的数组就相当于一个一个的桶(Bucket)，当有数据准备存进去的时候，它会通过一定的散列算法去计算，尽可能的让数据平均的命中到各个桶上面去，尽可能的避免哈希碰撞。如果发生哈希碰撞，就是不同的数据最后落到了同一个桶上的时候，就采用链表的方式来存储，但是链表长度比较长了的时候，去存储数据，读取数据都需要不停的去遍历循环，所以此时再采用链表结构的话效率会明显下降，所以 JDK1.8 之后做了优化，当链表的长度大于 8 的时候就由链表转为红黑树来存储。红黑树是平衡二叉树的其中一种实现，它比普通的二叉树表现更优异，因为普通的查询二叉树在一定条件下也可能会变成链表结构，而红黑树它是平衡二叉树的一种，它是通过左旋右旋变色等保持树的平衡。
简单的了解了 HashMap 的存储结构后，下面来讲下 HashMap 其中三个方法的源码
一、hash()方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}这个方法里看似简单，却暗藏玄机。
它是拿到了 key 本身的 hashCode 后，又做了一次运算，先将原来的 hashCode 无符号右位移 16 位，然后再将原来的 hashCode 异或 (^) 上这个位移后的值，最后得到一个值。
补充知识：
表示右移，如果该数为正，则高位补 0，若为负数，则高位补 1。
表示无符号右移，也叫逻辑右移，即若该数为正，则高位补 0，而若该数为负数，则右移后高位同样补 0。
^ 表示异或运算，每个位相同为 0，不同为 1
比如：
0 ^ 1 得 1
1 ^ 1 得 0
0 ^ 0 得 0
1 ^ 0 得 1
那为什么要无符号右移 16 位后做异或运算？key 本身的 hashCode 直接拿来用不好吗？
我们做一个简单演练
将 h 无符号右移 16 为相当于将高区 16 位移动到了低区的 16 位，再与原 hashcode 做异或运算，可以将高低位二进制特征混合起来
从上文可知高区的 16 位与原 hashcode 相比没有发生变化，低区的 16 位发生了变化
我们可知通过上面 (h = key.hashCode()) ^ (h >>> 16) 进行运算可以把高区与低区的二进制特征混合到低区，那么为什么要这么做呢？
我们都知道重新计算出的新哈希值在后面将会参与 hashmap 中数组槽位的计算，计算公式：(n – 1) & hash，假如这时数组槽位有 16 个，则槽位计算如下：
仔细观察上文不难发现，高区的 16 位很有可能会被数组槽位数的二进制码锁屏蔽，如果我们不做刚才移位异或运算，那么在计算槽位时将丢失高区特征
也许你可能会说，即使丢失了高区特征不同 hashcode 也可以计算出不同的槽位来，但是细想当两个哈希码很接近时，那么这高区的一点点差异就可能导致一次哈希碰撞，所以这也是将性能做到极致的一种体现
使用异或运算的原因
异或运算能更好的保留各部分的特征，如果采用 & 运算计算出来的值会向 1 靠拢，采用 | 运算计算出来的值会向 0 靠拢
为什么槽位数必须使用 2^n
1、为了让哈希后的结果更加均匀
这个原因我们继续用上面的例子来说明
假如槽位数不是 16，而是 17，则槽位计算公式变成：(17 – 1) & hash
从上文可以看出，计算结果将会大大趋同，hashcode 参加 & 运算后被更多位的 0 屏蔽，计算结果只剩下两种 0 和 16，这对于 hashmap 来说是一种灾难
2、可以通过位运算 e.hash & (newCap – 1)来计算，a % (2^n) 等价于 a & (2^n – 1)，位运算的运算效率高于算术运算，原因是算术运算还是会被转化为位运算
说了这么多点，上面提到的所有问题，最终目的还是为了让哈希后的结果更均匀的分部，减少哈希碰撞，提升 hashmap 的运行效率
二、put()方法
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}这个没什么好讲的，调用了下边的 putVal()方法
三、putVal()方法
这个方法很重要，是往 hashMap 里 put 值的核心逻辑，下边源码里的每一行我都进行了注释
/**
* Implements Map.put and related methods
*
* @param hash hash for keyput
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
/**
* 判断 tab 是不是为空, 如果为空, 则将容量进行初始化, 也就是说, 初始换操作不是在 new HashMap()的时候进行的, 而是在第一次 put 的时候进行的
*/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 初始化操作以后, 根据当前 key 的哈希值算出最终命中到哪个桶上去，并且这个桶上如果没有元素的话, 则直接 new 一个新节点放进去
*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
/**
* 如果对应的桶上已经有元素
*/
else {
Node<K,V> e; K k;
/** 先判断一下这个桶里的第一个 Node 元素的 key 是不是和即将要存的 key 值相同，如果相同, 则
* 把当前桶里第一个 Node 元素赋值给 e, 这个 else 的最下边进行了判断，如果 e!=null 就执行把
* 新 value 进行替换的操作
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果和桶里第一个 Node 的 key 不相同, 则判断当前节点是不是 TreeNode(红黑树), 如果是, 则进
// 行红黑树的插入
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);
// 判断元素个数是不是大于等于 8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 转换成红黑树
treeifyBin(tab, hash);
break;
}
/**
* 如果在遍历的时候，发现 key 值相同（就是 key 已经存在了）就什么都不做跳出循环。因为在上边 e = p.next 的时候，已经记录 e 的 Node 值了，而下边进行了判断，如果 e!=null 就执行把新 value 进行替换的操作
*/
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 把当前下标赋值给 p 并进行下一次循环
p = e;
}
}
/**
只要 e 不为空, 说明要插入的 key 已经存在了, 覆盖旧的 value 值, 然后返回原来 oldValue
因为只是替换了旧的 value 值，并没有插入新的元素，所以不需要下边的扩容判断，直接
return 掉
*/
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
/**
* 判断容量是否已经到了需要扩充的阈值了, 如果到了, 则进行扩充
* 如果上一步已经判断 key 是存在的，只是替换了 value 值，并没有插入新的元素，所以不需要判断
* 扩容，不会走这一步的
*/
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}hashMap 中还有其他的一些方法在此就不挨个来说了
可以在下方进行评论，一起学习进步
