HashMap源码解析

本文目录

• HashMap的设计思想
• HashMap的底层结构
• 为什么不一开始就使用HashMap结构
• 为什么Map中的节点超过8个时才转换成红黑树
• HashMap初始化
• 为什么HashMap初始化的容量一定是2的整数次幂
• 为什么HashMap不是线程安全的
• 同时put碰撞导致数据丢失
• 扩容期间取出的值不准确
• HashMap在java7和java8中的区别
• 底层数据结构对比
• 插入方式对比
• 扩容方式对比
• ConcurrentHashMap在java7和java8中的区别
• 数据结构
• 并发程度
• 遇到Hash碰撞

HashMap的设计思想

HashMap的底层结构

本文主要是讲解jdk1.8中的HashMap源码，会对jdk1.7中的HashMap做一些简单的讲解用来和jdk1.8中的HashMap进行对比。

我们先通过下图来理解HashMap的底层结构：

编辑搜图

请点击输入图片描述（最多18字）

首先我们通过上面的内容我们可以看到HashMap结构都是这样一个特点：最开始Map时空的，然后往里面放元素 时会计算hash值，计算hash值之后，第一个value值会占用一个桶（也就是槽点），以后再来相同hash值的value那么便会用链表的形式在该槽点后继续延伸 这就是拉链法。

当链表的长度大于或者等于阙值的（默认是8）的时候，并且同时还满足当前HashMap的容量大于或等于MINTREEIFYCAPACITY(默认64)的要求，就会把链表转成 红黑树结构，如果后续由于删除或者其它原因调整了大小，当红黑树的节点小于或等于6个以后，又会恢复链表结构。

为什么不一开始就使用HashMap结构

官方给出的解释是：

翻译就是：因为TreeNodes的大小大约是普通Node节点的两倍， 所以只有在节点足够多的情况下才会把Nodes节点转换成TreeNodes节点， 是否足够多又由TREEIFY_THRESHOLD决定，而当桶中的节点的数量由于移除或者调整大小变少后， 它们又会被转换回普通的链表结构以节省空间。

通过源码中得知，当链表长度达到8就转成红黑树结构，当树节点小于等于6时就转换回去，此处体现了时间和空间的平衡思想。

为什么Map中的节点超过8个时才转换成红黑树

这个问题官方给的解释是：

上面的意思是：在使用分布良好的用户的hashCodes时，很少使用红黑树结构，因为在理想情况下，链表的节点频率遵循泊松分布（意思就是链表各个长度的命中率依次递减），当命中第8次的时候， 链表的长度是8，此时的概率仅为0.00000006，小于千万分之一。

但是，HashMap中决定某一个元素落到哪一个桶中，是和某个对象的hashCode有关的，如果我们自己定义一个极其不均匀的hashCode，例如：

由于上述的hashCode方法返回的hash值全部都是1，那么就会导致HashMap中的链表比那的很长，如果数据此时我们向HashMap中放很多节点的话，HashMap就会转换成红黑树结构，所以链表长度超过8就转换成红黑树的设计更多的是为了防止用户自己实现了不好的哈希算法 而导致链表过长，影响查询效率，而此时通过转换红黑树结构用来保证极端情况下的查询效率。

HashMap初始化

HashMap的默认初始化大小是16，加载因子是0.75，扩容的阙值就是12（16*0.75），如果进行HashMap初始化的时候传入了自定义容量大小参数size，那么初始化的大小就是正好大于size的2的整数次方，比如传入10，大小就是16，传入30大小就是32，源码如下：

上述源码中，通过将n的高位第一个1不断的右移，然后把高位1后面的全变为1，在最后return的时候返回n+1，就符合HashMap容量都是2的整数次幂了。 例如下图：

为什么HashMap初始化的容量一定是2的整数次幂

不管我们传入的参数是怎么样的数值，HashMap内部都会通过tableSizeFor方法计算出一个正好大于我们传入的参数的2的整数次幂的数值，那么为什么一定要是2的整数次幂呢？ 我们先来看看计算key的hash方法如下：

得到了key的hash值后，在计算key在table中的位置索引的时候，代码如下：

正是因为n是2的整数次幂，比如当n是2时，它的二进制是10，4时是100，8时是1000，16时是10000….，那么（n-1）的二进制与之对应就是（2-1）是1，（4-1）是11，（8-1）是111，（16-1）是1111，为什么要用(n – 1) & hash 来计算数组的位置索引呢，正是因为(n – 1) & hash的索引一定是落在0～（n-1）之间的位置，而不用管hash值是多少，因为“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例， 16-1=15，2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。

为什么HashMap不是线程安全的

我们先来看HashMap中的put方法的源码，如下：

上图部分源码中可以看出HashMap的put方法中有一行代码是++modCount， 我们都知道这段代码并不是一个原子操作，它实际上是三个操作， 执行步骤分为三步：读取、增加、保存，而且每步操作之间可以穿插其它线程的执行， 所以导致线程不安全。另外还有导致线程不安全的情况还有：

同时put碰撞导致数据丢失

比如上面的源码中，假如现在有两个线程A和B，它们的key的hash值正好一样，然后它们同时执行到了这个if判断，并且都发现tab中i的位置是空，那么线程A就将自己的元素放到该位置，但是线程B之前也是判断到这个位置为空， 所以他在A之后也将自己的元素放到了该位置而覆盖了之前线程A的元素，这就是多线程同时put碰撞导致数据丢失的场景，所以HashMap是非线程安全的

扩容期间取出的值不准确

我们先来看看HashMap的取值方法get的源码，源码如下：

上面的get方法的源码中可以看出get方法主要是以下步骤：

1. 计算Hash值，并由此值找到对应的槽点。
2. 如果数组是空的或者该位置为null，那么直接返回null就可以了。
3. 如果该位置处的节点刚好就是我们需要的，直接返回该节点的值。
4. 如果该位置节点是红黑树或者正在扩容，就用find方法继续查找。
5. 否则那就是链表，就进行遍历链表查找。

首先HashMap的get方法是从table中查询我们要查找的key是否存在，如果存在则返回，不存在则直接返回null， 那么如果是在扩容期间，为什么获取的结果不准确呢？我们再来看看HashMap的扩容方法resize()，部分源码如下：

上面的源码是HashMap的resize方法的一小部分，首先我们知道HashMap的扩容会把旧数组的数据迁移到新数组中（怎么迁移的我们后面再说），在搬迁的过程中会把旧数组正在迁移的桶置为空比如，正如 上面代码oldTab[j] = null这一行代码，正是把索引j的桶（或者槽点）置为空了，但是如果此时还没有完成所有的数据的迁移，那么HashMap中仍然是使用的旧数组， 此时我们通过get方法查询的key的所以正好在这个旧数组中索引位置是oldTab[j]的位置，因为这个位置已经置空了，所以就会返回null，所以发生了扩容期间读取数据不准确。

HashMap在java7和java8中的区别

底层数据结构对比

java7的HashMap的结构示意图如下：

上图中可以看出jdk1.7中HashMap采用的数据结构是数组+链表的结构。

java8中的HashMap结构示意图如下：

从图中我们可以看出，java8中的HashMap有三种数据结构：

1. 第一种结构是就是数组，数组中空着的位置（槽）代表当前没有数据来填充
2. 第二种是和jdk1.7HashMap类似的拉链结构，在每一个槽中会首先填入第一个节点，后续如果计算出相同的Hash值，就用链表的形式往后延伸
3. 第三种是红黑树结构，这个是java7中HashMap中没有的数据结构，当第二种情况的链表长度大于某一个阙值（默认为8）的时候，HashMap便会把这个链表从链表结构转化为红黑树的形式，目的是为了保证查找效率，

这里简单介绍一下红黑树，红黑树是一种不严格的平衡二叉查找树,主要解决二叉查找树因为动态更新导致的性能退化,其中的平衡的意思代表着近似平衡,等价于性能不会退化.红黑树中的节点分为两类:黑色节点和红色节点,一颗红黑树需要满足:

1. 根节点是黑色。
2. 每个叶子节点都是黑色的空节点(null)。
3. 任何相邻的节点都不能同时为红色,也就是说红色节点是被黑色分开的。
4. 每个节点，从该节点到达其可达到的叶子节点的所有路径，都包含相同数目的黑色节点。

由于红黑树的自平衡特点，所以其查找性能近似于二分查找，时间复杂度是O(log(n))，相比于链表结构， 如果发生了最坏的情况，可能需要遍历整个链表才能找到目标元素，时间复杂度为O(n)，远远大于红黑树的O(log(n))， 尤其是在节点越来越多的情况下，O(log(n))

插入方式对比

jdk1.7中插入新节点采用的是头查法，就是如果来了新节点，将新节点插入到数组中，原数组中的原始节点作为新节点的后继节点，而且是先判断是否需要扩容，在插入。

jdk1.8中插入新节点的方式是尾查法，就是将新来的节点插入到数组中对应槽点的尾部，插入时先插入，在判断是否需要扩容。

扩容方式对比

jdk1.8中采用的是原位置不变或者位置变为索引+旧容量大小，resize()方法部分源码如下：

jdk1.7中的HashMap扩容的时候需要对原数组中的元素进行重新Hash定位在新数组中的位置，transfer方法的源码如下：。

同时因为jdk1.7中HashMap的扩容方法中调用的transfer方法内采用的是头插法，头插法会使链表发生反转，多线程环境下，会产生循环链表， 上面代码我们结合图来理解头插法和为什么多线程环境下会产生循环链表： 首先假设此时有原HashMap表的内部数据存储如下图：

此时达到了扩容要求，然后线程1和线程2此时同时进行扩容，线程1和线程2扩容时的新数组（newTable）如下图：

假设线程2先执行transfer方法，并且当它正好执行完了Entrynext = e.next;这行代码后，cpu时间片切换到了线程1来执行，并且线程1执行完了transfer方法，如下图：
线程1插入A节点到自己的新表中　　　

线程1插入B节点到自己的新表中　　

线程1插入C节点到自己的新表中　　

当线程1执行完了transfer方法后，还没有执行table = newTable这行代码，此时cpu时间片有切换到了线程2，那么线程2继续接着之前的位置执行，此处需要注意由于 由于之前线程2切换线程1之前已经执行完了Entrynext = e.next这行代码，因此在线程2中 变量e存的是A节点了，变量next存的是B节点，而且又由于线程1执行完了transfer方法后，原数组的节点指向如上图可以看出是C指向B，B是指向A的，所以切换到线程2的时候，线程2中的节点指向如下图：

线程2插入A节点到自己的新表中　

线程2插入B节点到自己的新表中

由于B节点指向A节点，所以下次插入产生了链表循环，如下图：

综上就是HashMap采用头插法的时候产生链表循环的场景。

ConcurrentHashMap在java7和java8中的区别

数据结构

jdk1.8中在对HashMap进行扩容的时候放弃头插法而改为尾插法了，扩容代码我已经在上面的扩容方式代码中标出，通过尾插法就避免了因为链表反转导致多线程环境下产生链表循环的情况。

我们先看一下jdk1.7中ConcurrentHashMap的底层数据结构，如下图：

​图中我们可以看出concurrentHashMap内部进行了Segment分段，Segment继承了ReentrantLock，可以理解为一把锁， 各个Segment之间相互独立上锁，互不影响，相比HashTable每次操作都需要锁住整个对象而言，效率大大提升，正是因为concurrentHashMap 的锁粒度是针对每个Segment而不是整个对象。

每个Segment的底层数据结构又和HashMap类似，还是数组和链表组成的拉链结构，默认有0～15共16个Segment，所以最多 可以同时支持16个线程并发操作（每个线程分别分布在不同的Segment上）。16这个默认值可以在初始化的时候设置为其他值，一旦设置确认初始化 之后，是不可以扩容的。

jdk1.8中的ConcurrentHashMap的底层数据结构，如下图：

通过上面两个图中可以看出，jdk1.8中的ConcurrentHashMap在数据结构上比jdk1.7中多了红黑树结构，引入红黑树结构是为了防止查询效率降低。

这里我们简单通过java7和java8的ConcurrentHashMap的含参构造函数看一下对比，首先java7的ConcurrentHashMap的构造函数代码如下：

并发程度

jdk1.7中的并发等级（concurrencyLevel）用Segment的数量来确定，Segment的个数为大于等于concurrencyLevel的第一个2的n次方的整数，例如当concurrencyLevel为12,13,14,15,16时，此时的Segment的数量为16

java8中的源码汇总保留了Segment片段，但是并没有使用，构造函数如下：

通过上面的代码的对比可以得出一下结论：

1. java7中采用Segment分段锁来保证安全，每个Segment独立加锁，最大并发数就是Segment的个数，默认是16。
2. java8中放弃了Segment设计，采用Node+CAS+synchronized保证线程安全，锁粒度更新，理想情况下table数组元素的个数（也就是数组长度）就是支持并发的最大个数。

遇到Hash碰撞

1. java7中遇到Hash冲突，采用拉链法，查找时间复杂度是O(n)，n是链表的长度。
2. java8中遇到Hash冲突，先采用拉链法，查找时间复杂度是O(n)，当链表长度超过一定阙值时， 将链表转换为红黑树结构，来保证查找效率，查找时间复杂度降低为O(log(n))，n为树中的节点个数。

​