JDK错误？？HashMap中的死循环问题！转载本文请联系石山架构笔记公众号。一、前言HashMap是java工程师最常用的数据结构之一，但真正深入掌握其原理的同学却寥寥无几。尤其是这篇文章的主题，据一些常年负责招聘的朋友说。HashMap的死循环是面试中的通病，但很少有面试官能说清楚，即使这些应聘者工作时间更长。原因是虽然解释这个问题的文章很多，但是好的文章却不多。也有一些文章讲解的不错，但是内容太费脑筋，读起来基本是雾里看花。鉴于目前的情况，这篇文章是根据我个人对源码的熟练程度，跳出源码，因为太费脑筋了，把核心链接都摘出来了。尝试用白话的形式一步步呈现底层原理。本文理论基础基于jdk1.8以下版本。死循环问题也主要存在于jdk1.8以下版本。2、HashMap的数据结构jdk1.7版本的HashMap底层结构是一个数组，数组中的每一项都可以是一个链表。一开始，我们使用数组来保存元素。当添加元素遇到冲突，即相同位置有多少元素时，有元素时，将这些元素添加到对应的链表中，所以HashMap的底层结构可以认为是由数组和链表组成列表。如果在构建HashMap时没有指定数组大小，那么默认情况下，数组大小为16，但限于空间。下面我们只画了一个大小为8的数组数组，在索引2处有一个链表，里面存放了3个元素，分别是Entry1、Entry2、Entry3。这三个元素的哈希运算结果相同，都是2，所以数组中index=2构成链表。3、插入数据在向HashMap中添加元素时，例如需要在上面的HashMap中添加一个节点Entry4(k4,v4)。首先，它会根据它的key值k4计算出hashcode值，然后对hashcode值做一些复杂的计算，得到数组中的目标索引，比如4。此时，由于数组索引的位置4为空，可以直接设置该元素插入到其底层数组中。因为完全有可能不同的key有相同的hashcode值，当然也完全有可能在数组中有相同的目标索引。比如新增一个元素Entry5(k5,v5)，对k5进行操作得到的目标索引为4。但是因为数组对应位置已经有一个元素Entry4，所以我们知道无法存储两个元素连续出现在一个数组的同一个索引处，没有被覆盖，那么这时候怎么处理呢？这时候链表就派上用场了。将这两个元素构造成索引为4的链表可以完美解决冲突问题。但是需要注意的是jdk1.7使用的是header插入方式。就是把新的节点Entry5作为链表的头节点放入数组中，去掉原来的Entry4作为它的下一个节点。如下图：为什么我们总是强调jdk1.7版本，因为在jdk1.8中HashMap结构发生了较大的变化，1.8版本的HashMap使用了尾部插入方式，底层结构也发生了变化.4.扩展Java工程师都知道jdk1.7中HashMap的初始默认长度是16，也可以自己定义，但是无论是自定义还是选择默认长度，随着元素个数的增加，达到一定的阈值，它会一直被扩展。扩容是通过加倍大小来进行的，也就是创建一个两倍大小的数组，将原来的元素重新哈希，计算出新的索引，放入新的数组+链表结构中。5、高并发下的扩容问题HashMap的结构和扩容机制可以保证在大数据量的情况下，读写性能依然能够保持优秀的性能。插入时使用头部插入方式会很快，读取时不会因为链表过长而影响读取性能。看到这里，你是不是觉得Hash是一个完美的设计，其实不然，因为HashMap并不是一个线程安全的数据结构。尤其是在扩容的时候，如果并发量不大，通常是没有问题的，但是在高并发的情况下，扩容就可能会出现严重的问题。下面模拟一个高并发下扩容的例子。1）假设有一个HashMap，它的负载因子为1，有两个元素（7，x）和（11，y），它们的hash运算结果都是1，所以都在1号链中list（即index为1指向的链表中，为了描述方便，以下简称），如下图。2）这时候需要给它添加一个节点（15，z）。此时有3个节点，因为已经达到扩容阈值，需要扩容。3）首先，线程2过来。根据展开的底层源码，需要将e指针指向链表的头节点(7,x)，next指针指向下一个节点(11,y)，如图下图中：其中e表示当前线程即将迁移的节点，next表示下一个需要迁移的节点。如果e指向的节点迁移完成，则进入下一个循环，e指针再次指向节点（11，y），next指针再次指向节点（15，z）。4）但是当线程2刚刚标记了e和next这两个指针，准备迁移第一个节点时。线程1过来并完成迁移。5）我们之前说过，HashMap进入链表采用的是头部插入方式，所以三个元素rehash迁移后链表的顺序是（15,z）—>（11,y）—>（7,x)图中的e和next指针属于线程2，仍然停留在原节点上。这一阶段的结构如下图所示：此时线程2中的表有节点(7,x)。6)然后将next指向的节点(11,y)添加到线程2代表的HashMap中，因为采用了head插入方式，所以(11,y)成为了链表的头节点，而原来的(7,x)成为它的下一个节点被选中。此时线程2中的表有(11,y)---->(7,x)这几个节点，链表的头节点为(11,y)。7)继续循环迁移元素，将e指向(7,x)，则next为null。然后将线程2的数组下标索引3指向e指向的节点，即在头节点上加上(7,x)（头插值法）。此时线程2中的表有(7,x)—>(11,y)---->(7,x)，形成一个环，如图：6.问题很严重.如果上面的迁移过程最后使用线程2的表作为新的hashmap，最终的迁移结果如下图所示：7.循环链表的后果是什么？假设我要检查上面的HashMap是否包含节点(7,x)。首先根据hash运算目标索引为3，所以将搜索目标转移到3号链表，然后根据key值11判断key恰好等于头节点(7,x)的链表，然后判断他们的值也相等。表示HashMap中包含我们要查询的点，返回true。假设我现在要查询节点(11,y)，经过hash运算后，搜索目标也转移到3号链表，然后根据11的key值，判断不是等于头节点的key(7,x)，然后转下一个节点。通过比较，如果发现下一个节点的key和value相等，则直接返回true。好像没什么问题，然后我们再查另一个节点（15，m），经过哈希运算，搜索目标也转移到3号链表中。首先不等于头结点(7,x)，再不等于下一个结点(11,y)比较也不相等。然后判断下一个节点。此时链表中的节点为(7,x)实际返回头节点，其下一个节点为(11,y)。快速飙升到100%，后果很严重。其实无论搜索什么节点，只要路由到了链表3，而且搜索的key不是7或者11，就会出现死循环。
