HashMap是不可重复key的 Map集合。

数组 链表对比

数组长度不可增加、读取速度块，在内存时一块连续的区域

链表在内存不是一块连续的区域

HashMap底层原理是： 数组 + 链表 当链表长度大于8时 即链表长度等于9，链表结构就会转换为红黑树

map是无序的，但是LinkedHashMap 是有序的

JDK 1.7 HashMap 源码分析

安装JDK 1.7 太烦了，我直接参考于：https://blog.csdn.net/qq_19431333/article/details/61614414

文章不错！！！！

核心属性 （规定一些默认的值）

threshould 必须是2的 次方 由 tableSizeFor(int cap) 进行二进制位运算得出

locaFactory 一般等于 0.75f ，这是经过 科学计算的

size

modCount 容量变化次数

构造方法 （4个）

进行一些参数的校验，

put(K key, V value)方法

1. 如果哈希表还未创建，那么创建哈希表
2. 如果键为null，那么调用putForNullKey插入键为null的值
3. 如果键不为null，计算hash值并得到桶中的索引数，然后遍历桶中链表，一旦找到匹配的，那么替换旧值
4. 如果桶中链表为null或链表不为null但是没有找到匹配的，那么调用addEntry方法插入新节点

1.7的addEntry方法

将键值对，以新节点作为链表的头节点，在JDK 1.8 之后，采用尾插法！

resize方法

将原有数组容量，扩容原来的2倍（实际数组的扩容，就是创建一个新的数组），扩容后，需要 转移原来的元素 到 新结构上的元素(相当于 进行原来的put)，由于是头插法，如果 原来属性是 1，2，3 那么新的结构就是 3，2，1

get方法

remove方法

replace方法

JDK7 HashMap的桶初始容量是16（只有第一次put的时候，才会初始化,put源码有说明）
HashCode的范围-2的31次方到2的31次方-1
长度2的n次方原因: hash & 数组的长度-1 只有是2的n次方的时候 -1 才能拿到2的n次方的值 进行按位与 才能快速拿到下标，并且均匀分布
如果遇见相同的key value，就直接覆盖（key存在，不会被替换，实际是替换value）。
扩容机制 :如果新put值。一旦超过当时的容量乘以负载因子，容量就会翻倍，但不会缩容。
首先先扩容，按照原来的顺序，然后再rehash，再添值
put方法：先进行hash()运算，获取hashcode值，（目的是尽量减少Hash碰撞）然后indexFor获得length-1&h 得出再数组中的位置，判断这个位置有没有key，有的话，替换value；如果没有key，调用addEntry()方法，这个方法先把键值对new出来，接下来判断是否超过阈值，接下来进行。一旦超过阈值，就把表的尺寸扩大，然后进行复制老数组。JDK7是反转链表的位置，多线程get时会出现链路回环，JDK8时顺序读取，就不会出现get链路回环，然后性能最消耗的就是：一旦resize（扩容）就按照原来的顺序，重新进行rehashu运算，重新插入。
get方法：先进进行hash(),然后去数组上找，然后判断链表。
HashMap线程不安全的原因：假如两个线程，同时操作HashMap，如果两个线程同时扩容，存储在链表的顺序会翻过来，将元素放在头部，避免尾部遍历，如果发生了，就死循环了。
JDK7 HashMap的死锁问题。

JDK7put流程（存储的结构Hash、Key、Value、Next 。hash存储的时哈希值，key是键值，value是值，next指向下一个的索引下标）
将元素进行hash运算获得索引下标，然后插入数组中，一旦发生Hash碰撞，将新的键值对的next指向原在数组位置上的元素 .
为什么不是将老值的next指向新值呢？ 如果要将老值的next指向新值，就需要重新遍历修改，浪费性能。

创建HashMap ==>初始容量initialCapacity(必须是2的指数次幂)、加载因子loadFactor(默认是0.75)、扩容阈值threshHold（容量*加载因子）
HashMap的数组初始化，不在构造方法里面(构造方法会判断初始容量、负载因子是否合法，不合法，强行转成2的指数次幂，保障分布均衡)，使用Put的时候再初始化。

第一次put的时候，判断数组有没有初始化，如果没有直接初始化数组，然后去判断要插入的key，没有key，直接（putForNullKey）添加值，直接返回。如果值不为空，先进行hash运算，得出哈希值（hash散列，位扰动，尽可能减少Hash碰撞），接下来将这个Hash运算成存储的索引下标（与运算（ 运算规则：两个数都转为二进制，然后从高位开始比较，如果两个数都为1则为1，否则为0。）==>Hash值&数组长度-1； PS:保证结果在0到length-1的范围，否则就会出先索引越界异常）不用%的原因，%的散列度不高，运算效率没二进制与高。)拿到索引位置后，遍历该节点上面的所有的节点，看一下有没有相同的key，有的相同的key，把新值替换老值。如果没有，那就添加新的节点（实际添加节点的时候，会判断是否满足扩容机制原来的两倍（扩容机制JDK7是键值对数量>=满足阈值，并且插入的数组上有键值对才会扩容）扩容完成后，将老值添加到新的数组上 （transfor()首先拿到新数组的长度，然后遍历集合死循环e键值对，将老e指向老的头节点，新的next指向头节点下面的节点，将重新的rehash，调用indexFor拿到在新数组的位置，把值复制过去，新next指向新数组上的头节点，将e指向老节点的next。第一轮循环结束，然后e会指向老节点的下个节点，如此循环，直到e未null为止），在添加新值进去，将下标指向原来数组的那个头部节点）。

JDK1.7 HashMap链表回环的原因：

可以理解成 头插法，JDK 1.8 是尾插法

再多线程情况下：线程1、2都要去扩容，原来的结构是：B存在数组上，A存在B的链表上，如果线程1扩容、复制值完毕（假设有两个元素添加到链表上，数组上存的是A(e=a,next=B),该数组上的链表村的是B(e=b,next=null)）线程1扩容完毕，线程二唤醒了，他去读取数据，先读取数组上的A(e=a,next=B)存入数组，然后读取B(e=b,next=A)，此刻就埋下了链表回环的伏笔。当结束后e=next，就变成e=a，但是e.next就会得到A的next，也就是B，这样就形成回环，死锁了。

JDK8的结构
数组+链表+如果链表长度大于8就将链表转为红黑树了。

总结1.7与1.8中 HashMap：

相同点：

默认初始容量都是16，默认加载因子都是0.75。容量必须是2的指数倍数

扩容时都将容量增加1倍

初始时表为空，都是懒加载，在插入第一个键值对时初始化

键为null的hash值为0，都会放在哈希表的第一个桶中

不同点：

1.7是数组+链表，1.8则是数组+链表+红黑树结构

1.7是头插法，1.8是尾插法

面试

HashMap如何解决Hash冲突？

如果计算Hash后得到的数组下标，如果有相同的数组下标，就会放入链表中。JDK8采用尾插法。