1、 HashMap 介绍

HashMap 是开发中常用的数据结构，其以键值对的存储数据，接下来我们看下 hashmapde 数据结构、底层实现原理。主要介绍下下面的几方面，底层数据结构、扩容机制、寻址算法和 hash 算法、在 1.7 下的死锁问题

2、 底层数据结构

在 1.7 中由数组和链表构成，hash 存在概率性，不可避免的存在冲突，链表其实在 hash 冲突情况的下产物，在 jdk1.8 之前采用头插法，此时就形成了链表。在一些极端情况下，hash 冲突严重，会造成链表过长，此时查找效率严重降低。所以在 jdk1.8 引入了红黑树，当链表过长的情况下转化为红黑树。

3、 扩容机制、寻址算法、hash 算法

以 put 为入口理解下相关的原理寻址算法和 hash 算法 public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}

通过 hash（hey）计算 hash 值 static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

  Hash计算主要有两个重点，计算出hash值，然后进行右移16位；在与原来的值进行抑或，其实就是hash高16位和低16位进行抑或，可以有效的减少hash冲突。

为什么不直接用 hashCode() 而是用它的高 16 位进行异或计算新 hash 值？int 类型占 32 位，可以表示 2^32 种数（范围：-2^31 到 2^31-1），而哈希表长度一般不大，在 HashMap 中哈希表的初始化长度是 16（HashMap 中的 DEFAULT_INITIAL_CAPACITY），如果直接用 hashCode 来寻址，那么相当于只有低 4 位有效，其他高位不会有影响。这样假如几个 hashCode 分别是 2^10、2^20、2^30，那么寻址结果 index 就会一样而发生冲突，所以哈希表就不均匀分布了。为了减少这种冲突，HashMap 中让 hashCode 的高位也参与了寻址计算（进行扰动），即把 hashCode 高 16 位与 hashCode 进行异或算出 hash，然后根据 hash 来做寻址。扩容机制：HashMap 底层主要结构是数组，而数组必须开辟连续的空间；达到一定长度后会触发扩容机制，也就是 resize。主要有两个因素● Capacity：HashMap 当前长度。● LoadFactor：负载因子，默认值 0.75f。怎么理解呢，当你当前容量是 16，存进第 13 的元素的时候，判断需要进行 resize。

扩容？它是怎么扩容的呢？

• 扩容：创建一个新的 Entry 空数组，长度是原数组的 2 倍。

• ReHash：遍历原 Entry 数组，把所有的 Entry 重新 Hash 到新数组。为甚需要重新 hash 一遍，因为此时数组长度不一样，需要计算位置。

取模

（1）(n-1)&hash=.（1）hash % (n-1) （1）保证了位运算的效率，（2）保证了范围在数组范围内，所以 2 必须为 2 的 n 次幂。

负载因子为什么默认值 0.75f。如果太大，hash 冲突的可能性随之提高；太小有点浪费空间，这是在经验中取得一个平衡值。

红黑树当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间，8 是经过开发和实际经验来采用的。

头插是 JDK1.7 的那 1.8 的尾插是怎么样的呢？使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。就是说原本是 A->B，在扩容后那个链表还是 A->B

Java7 在多线程操作 HashMap 时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。

Java8 在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。