一、HashMap简介

HashMap是Java使用频率非常高的一个集合，存储key-value的键值对。采用空间换时间的策略，大大提高检索效率。HashMap的底层是采用链地址法来实现的。

HashMap在JDK1.7及之前版本采用的是数组加链表的方式实现，采用头插法（在链表头部插入节点）。但是当经常发生hash冲突时，链表的长度就会拉长，检索效率也会下降。

在这里插入图片描述

JDK1.8之后，也是采用数组加链表，但是采用尾插法（在链表尾部插入节点），同时当链表长度大于8时，会自动转化为红黑树，提高检索效率。检索效率接近O(log2N)。

在这里插入图片描述

二、hash计算

hash的计算最简单的方式就是key的hash%n，但是这个执行效率比较低。HashMap通过(n-1)&key的hash的方式就可以快速计算出这个key该存在哪个数组下标里面。这要求HashMap的数组长度始终保持在2的n次方，扩容也会2倍进行扩容。

当链表长度大于8会转为红黑树，之所以保留链表，不直接使用红黑树，是因为红黑树节点的大小是普通节点大小的两倍，所以为了节省内存空间不会直接只用红黑树。之所以是8，是通过泊松分布得出的结论，是为了平衡时间和空间的问题。
当红黑树节点少于6要从红黑树转成链表，也是为了平衡时间和空间，节点少的时候链表遍历也很快，没必要成红黑树，变成链表节约内存。之所以定了6而不是小于等于8就变，是因为要留个缓冲余地,避免反复横跳，减少转变的频率。