文章目录

1.HashMap的概述2.HashMap的数据结构为什么需要链表数据结构JDK7是什么插入法，而JDK8呢Hash值计算为什么HashMap的扩容大小要求是2的幂？& 比 % 运算效率高均匀分布如果自定义设置的值不是2的幂 3.HashMap 插入 和 扩容 源码插入扩容初始化扩容正常扩容 参考资料

1.HashMap的概述

HashMap是平常编程中使用的最多的一种数据结构，是Map下的一个具体实现类，Map下还有TreeMap、LinkedHashMap，这些就放到另外一篇文章讲了。

2.HashMap的数据结构

HashMap是一种非常常用的Key-Value的数据结构，在JDK1.7是由数组+链表组成的数据结构，在JDK1.8时是由Node数组+链表+红黑树组成的数据结构。

在Java7叫Entry，而在Java8中叫Node。Node结点代码如图：

为什么需要链表数据结构

可以从HashMap的put方法讲起，HashMap在put的时候，会将当前的key计算出hash值，通过哈希函数也就是hash & (n-1)算出应存放在数租的哪个位置也就是下标n，如果数组当前n位置没有值，那么直接创建新结点则完成put过程，但是如果存在值，再通过equals方法进行比较当前的key，如果key相同，则更新value值，如果不相同，则表示发生了hash冲突。

哈希冲突的解决方法有两种：一是拉链法，二是开放地址法。在JDK的实现中是用拉链法解决哈希冲突的，也就是在发生哈希冲突的结点形成一个链表，将新put的结点推到链表中去。

而开放地址法则在ThreadLocal中有着精彩的表现，具体可以看看ThreadLocal的文章。

JDK7是什么插入法，而JDK8呢

JDK7使用的是头插法，也就是新来的值会取代原有的值，原有的值就被推到链表中去：（插入顺序为C B A） 但是头插法在多线程resize的情况下会有链表死循环问题的发生，因为resize的赋值方式，也就是使用了单链表的头插入方式，同一位置上的新元素会放在链表的头部位置。在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

Hash值计算

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

这里计算hash值时，首先获取了key的hashCode，并跟hashcode的右移16位进行异或运算，其实就是hashcode的高16位和低16位进行异或运算。

为什么要这么设计？

假设不进行这一步操作，直接把key的hashcode作为hash值，会跟HashMap的长度n-1进行与运算（11=1，其他都是0），因为n-1比较小，高位几乎都是0，也就是hash值的低位跟长度n-1的低位进行与运算，抛弃了hash值高位，这种情况就会导致发生hash冲突的概率比较大，因此在计算的时候加入扰动函数，将key的hashcode的高16位跟低16位进行异或运算（相同就是1，不同就是0），让低16位保存高16位的一些特征，降低发生Hash冲突的概率，使得计算出来的Index均匀分布。

为什么HashMap的扩容大小要求是2的幂？

& 比 % 运算效率高

映射算法:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qVH7JNsk-1599136409448)(49F76A27E08C49078F9691564A4874FB)]

可以看到拿到key的hash值后与（n-1）进行与运算，因为与运算要比取模效率高，&运算直接通过内存地址，也就是二进制就可以计算结果，而取模运算还要经过转化成十机制进行计算，因此&运算效率会高。但是&预算要与%运算结果相同，也就是：

X % 2^n = X & (2^n – 1)

因为位运算效率比取模运算高，两个结果相等要求n必须是2的幂

均匀分布

容量16时，n-1=15，15的二进制是0111，因此index结果值就只跟key的HashCode的最后几位有关，换句话说，只要key的hash值分布均匀，那么整个HashMap就分布均匀，因为&运算之后的结果，只跟key的HashCode最后几位有关，为了均匀分布

也就是说只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。其实这样设置是为了均匀分布。

如果自定义设置的值不是2的幂

如果自定义的值设置成不是2的幂，那么HashMap会以此为基础，设置一个比该值大的2的幂作为初始容量。

3.HashMap 插入 和 扩容 源码

插入

HashMap 扩容比较多，尽量以简单句的形式来表达，以下面的语句开启分析：

HashMap<Integer,Integer> map = new HashMap<>(); map.put(1,2);

因为用的空的构造方法，因此只赋予loadFactor为默认的loadFactor 0.75

public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }

然后进行put操作，计算出key的hash值进行putVal操作：

//当前table为空，先去新建table if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //如果当前的table对应的Index位置为空，则直接插入 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //如果当前table对应的index位置有值，则有可能发生hash冲突 else { ... //如果当前的index的值与key进行equals比较为true，则覆盖新value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果当前的结点的类型是属于红黑树则进行红黑树添加 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //否则则进入尾插法链表添加，同时如果链表长度超过8则会树化。 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } ... } } ... //添加完成之后如果size > threshold则触发扩容机制 if (++size > threshold) resize();

扩容

在扩容操作中，主要涉及oldTable、oldThreshold、oldCapacity以及newTable、newThreshold、newCapacity等等变量。

初始化扩容

初始化扩容也就是指上面那种情况，HashMap刚创建然后put进入的情况，此时因为table == null会触发扩容机制：

if (oldCap > 0) { ... } else if (oldThr > 0) // initial capacity was placed in threshold ... else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } ... Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { } ... return table

因此将newCapacity设置成16，newThreshold设置成12.后面oldTab == null，因此不走if，直接返回table。

正常扩容

首先获取oldTable的长度，这里的oldCapacity是大于0的，因此：

int oldCap = (oldTab == null) ? 0 : oldTab.length; if (oldCap > 0) { //如果oldCapacity的长度大于等于最大长度1 << 30,则将threshold设置成Integer.MAX_VALUE并返回 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //进行两倍扩容，如果长度超过16阈值也做两倍扩容 //因为<16时，阈值不是做两倍扩容的 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //HashMap map = new HashMap(5) ，实际上只是设置oldThreshold为5而已，这里就将newCap = oldThr为5。 else if (oldThr > 0) newCap = oldThr; else { // zero initial threshold signifies using defaults ... } //按照给定的初始大小设置newThr，这里主要是给oldCap < 16的设置newThr if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //迁移数据 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) ...无后继结点，则直接计算并放在新数组中 else if (e instanceof TreeNode) ...遍历红黑树，进行数据转移 else { // preserve order ...有后继结点，是链表，遍历链表，转移数据 } } } }

参考资料

敖丙-HashMap系列

Hollis-HashMap默认容量的选择