谈到HashMap，本质是一个散列表，重点是三大问题：散列函数、哈希冲突、扩容方案。
散列函数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
// 与数组长度-1进行位与运算，得到下标
if ((p = tab[i = (n - 1) & hash]) == null)
...
}在putVal中，将key的hash值与数组长度-1 进行与运算，得到的 p 就是数组下标。
哈希冲突
- 如果不存在元素，直接存入该位置
- 如果存在元素，则判断桶位上的元素是否与要插入的相同，如果相同，执行替换操作
如果不同，判断是链表还是红黑树。
如果是链表，就遍历链表上的元素，查找是否有与key相同的元素；如果没有，就插入链尾，并判断是否要树化。
Jdk1.8之前是数组+链表
jdk1.8之后是数组+链表+红黑树，在数组长度大于64且链表长度大于8转化为红黑树。
- 为什么要大于等于8转化为红黑树，而不是7或9？
数结点比普通结点更大，链表较短时用红黑树没有优势。在装载因子为0.75，链表长度达到8的概率极低。
JDK1.8 扩容优化
扩容时机由装载因子决定，在 1.8 之前，扩容时是把原来的每个节点重新计算 hash 值，对应到新数组的下标。在 1.8 中 HashMap 对扩容机制做了优化，对于结点在新数组的下标只有两种：原数组下标或 原数组下标 + 原数组长度。
回忆下计算 Hashmap 索引下标：索引 = hashCode & (数组长度 -1)。
比如当数组长度是 16 时，长度 - 1 就是 15，二进制为 1111。当数组长度是 32 时，长度 - 1 就是 31，二进制为 11111。从 16 扩容到 32 时，只是在 1111 前面多加了个 1。
这样做有什么好处？在计算新的索引时，只需判断原来的 hashCode 第五位是 0 还是 1。
- 如果第五位是 0，那么这个元素在新数组中的位置不变。（0进行 & 运算还是为 0）
- 如果第五位是 1，那么新数组索引是 旧索引加上 16（二进制 10000），也就是 旧索引加上原来数组长度。
通过这种方式，不需要重新计算每个元素的索引，只需判断第五位，就能快速定位新数组的索引。
为什么HashMap不安全
- 在1.7时多线程同时扩容可能造成链表形成环。
- put 和 get 并发时，可能导致 get 为 null。因为一个线程在进行 put 时触发扩容，此时另一个线程来 get，新数组还没有初始化，当然 get 为 null 了。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1216271933@qq.com
