一、HashMap实现原理
1.HashMap概述
HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变
2.HashMap的数据结构
在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外,HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体
3.HashMap 基于 Hash 算法实现
当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标存储元素如果出现hash值相同的key，此时有两种情况如果key相同，则覆盖原始值如果key不同（出现冲突），则将当前的key-value放入链表中,Jdk 1.8中对HashMap的实现做了优化，当链表中的节点数据超过八个之后，该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn)获取数据元素
直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值
二、 HashMap在JDK1.7和JDK1.8中底层实现不同
在Java中，保存数据有两种比较简单的数据结构：数组和链表数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做拉链法的方式可以解决哈希冲突1.HashMap JDK1.8之前
JDK1.8之前采用的是拉链法将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可
2. HashMap JDK1.8之后
相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间3. JDK1.7 VS JDK1.8 比较
JDK1.8主要解决或优化了以下问题 resize 扩容优化引入了红黑树，目的是避免单条链表过长而影响查询效率，解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题头插法的方式可能会造成死循环，死循环是HashMap在并发下线程不安全的体现，在下面的jdk1.7扩容会给出解释
三、 HashMap的put方法的具体流程
流程
当我们put的时候，判断hashMap的存储容量是否大于当前容量*0.75（loadFatory–加载因子），如果大于进行扩容resize为原来的一倍
计算 key 的 hash 值，这里调用了 hash 方法， hash 方法实际是让key.hashCode() 与 key.hashCode()>>>16 进行异或操作，高16bit补0，一个数和0异或不变
以 hash 函数做异或运算
高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞
因为bucket数组大小是2的幂，计算下标 index = (table.length - 1) &hash ，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位
数组大小为2的幂时性能最高，减少哈希碰撞
数组长度为16-1（2的4次方-1），使用不同的hashCode进行与运算，结果是9和8
数组长度为15-1，使用不同的hashCode进行与运算，结果是8和8
当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，数组可以使用的位置比数组长度小了很多，增加了碰撞的几率，减慢了查询的效率！
当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了
通过hash计算出hash值，哈希没有碰撞直接存入
哈希碰撞，通过equal比较key值，相同则覆盖原始值，返回旧的value
计算的key值不相同，则将当前的key-value放入链表中Jdk 1.8中对HashMap的实现做了优化，当链表中的节点数据超过八个之后，该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn)
putVal方法执行流程图
解决哈希冲突
链表法
将相同hash值的对象组织成一个链表放在hash值对应的槽位
开放地址法
通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位
相比于hashCode返回的int类型，我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4 （即2的四次方16）要远小于int类型的范围，让hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算（高低位异或）}
相比在1.7中的4次位运算，5次异或运算（9次扰动），在1.8中，只进行了1次位运算和1次异或运算（2次扰动）
不能使用哈希值直接作为table的下标
hashCode() 方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）~2 ^ 30，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，从而导致通过 hashCode() 计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置
解决方案
HashMap自己实现了自己的 hash() 方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均在保证数组长度为2的幂次方的时候，使用 hash() 运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的方式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题
四、 HashMap的扩容操作
jdk1.8扩容操作
在jdk1.8中，resize方法是在hashMap中的键值对大于阀值时（加载因子*16(数组初始化容量)）或者初始化时，就调用resize方法进行扩容每次扩展的时候，都是扩展2倍扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置在putVal()中，我们看到在这个函数里面使用到了2次resize()方法，resize()方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发，这也是JDK1.8版本的一个优化的地方jdk1.7扩容操作
在1.7中，扩容之后需要重新去计算其Hash值，根据Hash值在同一个桶的位置中进行判断(e.hash & oldCap)是否为0，重新进行hash分配后，该元素的位置对其进行分发，但在1.8版本中，则是根据要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上死循环
jdk1.7扩容的时候可能会造成死循环，HashMap在并发条件下线程不安全的体现之一
举例头插法正常扩容的场景数据初始化，数组长度为4，数据A和数据B
进行扩容，数组长度加一倍，长度为8，先取出A
再取出B进行头插法，A往后移一位，B插入节点，指针指向A
举例头插法死循环的场景线程1进行扩容后，要重新分配数据的时候，CPU使用权给到了线程2,造成线程1拿到的数据是扩容后没完成数据分配的数组，A的指针指向B
线程2拿到CPU使用权，拿到扩容后的数组，并对数据进行重新分配,分配好的数据是B的指针指向A
线程1是A的指针指向B，线程2是B的指针指向A，两个线程的A、B的内存地址都是一样的，造成A和B相互引用，造成死循环
如果觉得《HashMap实现原理和扩容机制》对你有帮助，请点赞、收藏，并留下你的观点哦！
