HashMap【Java】

简介

HashMap的继承结构

HashMap是Java中非常重要的数据结构，HashMap继承自Map、Serializables、Cloneable等三个接口，并且实现了抽象类AbstractMap。

HashMap是散列表结构，存储的数据是键值对(key-value)。

HashMap 实现了Map接口，根据键值的HashCode值计算数据的存储位置，在查询数据的时候通过HashCode的值可以在Θ（1）的时间复杂度检索数据。
HashMap通过Hash值存储数据，所以是无序的。
HashMap中Key的值是唯一的，如果插入重复Key的Value值，会覆盖之前的Value。
HashMap是线程非安全的数据结构，并发插入的时候可能会出现脏读，死循环等未知问题。

Map是非常重要的数据结构，除了HashMap的实现的之外，常用的Map实现还有HashMap、TreeMap、ConcurrentHashMap等。


Map实现	父类	实现数据结构	线程安全	能力
HashMap	AbstractMap	数组+链表+红黑树	否	只能实现Key的查询，但是查询效率高。
TreeMap	AbstractMap	红黑树	否	通过红黑树实现，可以实现排序的能力
LinkedHashMap	HashMap	数组+链表+红黑树+双向链表	否	维护了数据特定顺序（插入序或者访问序）的双向链表，所以LinkedHashMap也经常被用作LRU的缓存结构。
ConcurrentHashMap	HashMap		是

原理

Hash算法

HashMap的Hash公式是(h = key.hashCode()) ^ (h >>> 16)。

其中hashCode()方法继承自Object类，该方法的实现是native方法，在不同的JVM版本，不同的系统平台上会有不同的实现。OpenJDK 6以及OpenJDK 7，HashCode的实现是随机数字，AZUL-ZING的JVM中，hashCode()的计算依赖对象的物理地址。

hashCode()是完成计算之后，会存储在对象头，因为hashCode的值在Map等结构中会参与判断对象是否相等，根据随机数、地址计算可能会将相同值的对象存储在不同的Hash槽中，无法判定为相等。所以类型可以自定义hashCode方法，例如java.lang.String中的hashCode就是根据字符串的字符进行位移计算而来的。

h >>> 16将hashCode的值右移16位，高位补0，然后再与hashCode() 进行异或运算确定最终的hashCode。当数组长度小于2^16即大于65536时，hashCode的高位数据对存储位置影响不大，所以此处针将hashCode的值做了右移操作。

异或运算可以让HashCode的低16位进行充分的打散，从而减少Hash冲突的概率。

HashMap通过hashCode的值计算数据的存储位置（Hash槽），HashMap中位置的运算公式是hashcode & (length-1)，公式中length为Hash槽数组的长度，该值默认长度是16。同时为了数据的均匀，所以对长度减一进行取模运算。

数据结构

HashMap的结构图

HashMap使用到的数据结构有数组，链表以及红黑树。

数组作为Hash槽存储数据，保存到HashMap中的Key计算Hash值并且计算存储槽位的索引之后，将数据放值在该数组的索引槽位，但是当该位置已经有存储数据的时候，需要判断已有数据和当前的数据的Key值是否相等，如果相等，则覆盖原有数据的Value，如果不等则需要存入解决冲突的链表或者红黑树。

当Hash槽位上冲突的Key数量在一定范围（8个以内）的时候，HashMap采用拉链法解决冲突问题，就是将冲突的数据作为链表的结点存入冲突的链表中。

因为冲突链表达到一定长度之后，查询一个Key遍历该链表的成本较高，所以当冲突的Key大于8个的时候，HashMap会引入红黑树进行冲突数据的存储。

因为红黑树中数据是排序的，所以在查询冲突数据的时候可以有链表有更高的效率。

容量

当HashMap中存储的数据较多，而Hash数组的长度偏小的时候，HashMap的冲突会变得严重，影响到存取效率。所以HashMap需要有扩容的机制。

HashMap存储的数据量/Hash数组的长度得出的值称为负载因子，当负载因子大于0.75的时候，Hash表会启用扩容机制，扩容之后的容量是当前容量的2倍，所以Hash数组的长度一定是2ⁿ。

因为计算Hash数组位置的公式是hashcode & (length-1)，所以2ⁿ可以更好的将数据打散。

当Hash表扩容之后，会将之前的值重新进行位置元素，迁移到新的位置，这个过程称为rehash。

并发问题

头插法和尾插法

HashMap不是一个线程安全的数据结构，因为在写入、Rehash等时候没有加锁，所以读取的值可能存在脏读，幻读等。

而且是使用拉链法存储Hash冲突，在JDK8之前的版本中在多线程Hash表扩容时可能会出现死循环，因为JDK8的链表插入改成尾插法之前使用的是头插法。

使用头插法是指新插入的结点插入到链表头部，头插法实现比较简单，只需要更改新插入结点以及头节点的指针即可，而且链表可以直接查询到链表的头节点，所以头插法效率较高。

在rehash的时候，链表从从一个Hash槽的位置，迁移到另一个Hash槽，使用头插法创建新链表的过程中会发生链表倒置的情况，即链表元素和原链表相反。

尾插法的效率较低，实现复杂度较高，但是rehash的时候新创建的链表和原链表顺序相同。

头插法出现死循环的情景推演如下：

线程 T1 和线程 T2 要对 HashMap 进行扩容操作，此时 T1 和 T2 指向的是链表一个两个元素的链表，链表的头节点元素 A，而头元素指向B结点，在扩容前，T1和T2看到的链表结构都是A->B。

T1首先对HashMap执行扩容，当扩容完成链表的头节点变为B，当前的链表结构是B->A，当时对于线程T2而言，它依然储存了扩容之前的链表结构即A->B。

在T2执行扩容的时候，其看到的链表视图是A->B->A，也就发生了死循环场景。