[数据结构与算法] 一篇文章弄懂HashMap底层

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 一篇文章弄懂HashMap底层 -> 正文阅读

[数据结构与算法]一篇文章弄懂HashMap底层

文章目录

1、HashMap结构

JDK7与JDK8及以后的HashMap结构与存储原理有所不同：
Jdk1.7：数组 + 链表 ( 当数组下标相同，则会在该下标下使用链表)
Jdk1.8：数组 + 链表 + 红黑树 (预值为8 如果链表长度 >=8则会把链表变成红黑树 )
Jdk1.7中链表新元素添加到链表的头结点,先加到链表的头节点,再移到数组下标位置
Jdk1.8中链表新元素添加到链表的尾结点
(数组通过下标索引查询，所以查询效率非常高，链表只能挨个遍历，效率非常低。jdk1.8及以
上版本引入了红黑树，当链表的长度大于或等于8的时候则会把链表变成红黑树，以提高查询效率)

HashMap中的数组通常被称为桶数组

如下图所示：

数组存放了一个key-value实例，在jdk7中叫Entry在jdk8中叫Node，红黑树中的结点是TreeNode

Node继承与Map.Entry，TreeNode继承于Node

2、HashMap中的常量

//默认的初始化容量为16，必须是2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//最大容量为 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认的加载因子0.75，乘以数组容量得到的值，用来表示元素个数达到多少时，需要扩容。
//为什么设置 0.75 这个值呢，简单来说就是时间和空间的权衡。
//若小于0.75如0.5，则数组长度达到一半大小就需要扩容，空间使用率大大降低，
//若大于0.75如0.8，则会增大hash冲突的概率，影响查询效率。
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//刚才提到了当链表长度过长时，会有一个阈值，超过这个阈值8就会转化为红黑树
static final int TREEIFY_THRESHOLD = 8;

//当红黑树上的元素个数，减少到6个时，就退化为链表
static final int UNTREEIFY_THRESHOLD = 6;

//链表转化为红黑树，除了有阈值的限制，还有另外一个限制，需要数组容量至少达到64，才会树化。
//这是为了避免，数组扩容和树化阈值之间的冲突。
static final int MIN_TREEIFY_CAPACITY = 64;

//存放所有Node节点的数组
transient Node<K,V>[] table;

//存放所有的键值对
transient Set<Map.Entry<K,V>> entrySet;

//map中的实际键值对个数，即数组中元素个数
transient int size;

//每次结构改变时，都会自增，fail-fast机制，这是一种错误检测机制。
//当迭代集合的时候，如果结构发生改变，则会发生 fail-fast，抛出异常。
transient int modCount;

//数组扩容阈值
int threshold;

//加载因子
final float loadFactor;					

//普通单向链表节点类
static class Node<K,V> implements Map.Entry<K,V> {
	//key的hash值，put和get的时候都需要用到它来确定元素在数组中的位置
	final int hash;
	final K key;
	V value;
	//指向单链表的下一个节点
	Node<K,V> next;

	Node(int hash, K key, V value, Node<K,V> next) {
		this.hash = hash;
		this.key = key;
		this.value = value;
		this.next = next;
	}
}

//转化为红黑树的节点类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
	//当前节点的父节点
	TreeNode<K,V> parent;  
	//左孩子节点
	TreeNode<K,V> left;
	//右孩子节点
	TreeNode<K,V> right;
	//指向前一个节点
	TreeNode<K,V> prev;    // needed to unlink next upon deletion
	//当前节点是红色或者黑色的标识
	boolean red;
	TreeNode(int hash, K key, V val, Node<K,V> next) {
		super(hash, key, val, next);
	}
}

这里就引申而来几个问题：

问题一：为什么HashMap的默认负载因子是0.75，而不是0.5或者是整数1呢？

阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) 根据HashMap的扩容机制，他会保证容量(capacity)的值永远都是2的幂为了保证负载因子x容量的结果是一个整数，这个值是0.75(4/3)比较合理，因为这个数和任何2的次幂乘积结果都是整数。
理论上来讲，负载因子越大，导致哈希冲突的概率也就越大，负载因子越小，费的空间也就越大,这是一个无法避免的利弊关系，所以通过一个简单的数学推理，可以测算出这个数值在0.75左右是比较合理的

问题二：为什么HashMap初始化大小是16呢？

首先需要明确：HashMap的容量只能是2的幂次方，扩容的策略也是原来的容量 * 2，就算构造函数传入初始容量不是2的幂次方，构造函数中也会将传入的初始容量转为第一个 > = 的2的幂作为容量。

为什么容量要求是一个2的幂呢？

这是为了方便计算!当获取到一个key的hash值后，我们需要将hash值映射到数组中，常规的思路就是将 hash%n 获取桶数组的索引，但是取余操作需要消耗大量的时间，如果能够使用&操作替代%操作就能加快计算。因此下标计算使用以下式子：

int index=key.hashCode()&(n-1) 获取桶中的下标。而只有当n为2的幂，(n-1)&key.hashCode() 才能使hash值在数组下标中均匀分配，获得的index就能减少重复，这样就能减少冲突和提高HashMap的查找效率。

那么为什么是16呢？32、8就不行吗？

因为是8的话很容易导致map扩容影响性能，如果分配的太大的话又会浪费资源，所以就使用16作为初始大小。

3、HashMap的构造函数

//默认无参构造，指定一个默认的加载因子
public HashMap() {
	this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

//可指定容量的有参构造，但是需要注意当前我们指定的容量并不一定就是实际的容量，下面会说
public HashMap(int initialCapacity) {
	//同样使用默认加载因子
	this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//可指定容量和加载因子，但是笔者不建议自己手动指定非0.75的加载因子
public HashMap(int initialCapacity, float loadFactor) {
	if (initialCapacity < 0)
		throw new IllegalArgumentException("Illegal initial capacity: " +
										   initialCapacity);
	if (initialCapacity > MAXIMUM_CAPACITY)
		initialCapacity = MAXIMUM_CAPACITY;
	if (loadFactor <= 0 || Float.isNaN(loadFactor))
		throw new IllegalArgumentException("Illegal load factor: " +
										   loadFactor);
	this.loadFactor = loadFactor;
	//这里就是把我们指定的容量改为一个大于它的的最小的2次幂值，如传过来的容量是14，则返回16
	//注意这里，按理说返回的值应该赋值给 capacity，即保证数组容量总是2的n次幂，为什么这里赋值给了 threshold 呢？
	//先卖个关子，等到 resize 的时候再说
	this.threshold = tableSizeFor(initialCapacity);
}

//可传入一个已有的map
public HashMap(Map<? extends K, ? extends V> m) {
	this.loadFactor = DEFAULT_LOAD_FACTOR;
	putMapEntries(m, false);
}

//把传入的map里边的元素都加载到当前map
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
	int s = m.size();
	if (s > 0) {
		if (table == null) { // pre-size
			float ft = ((float)s / loadFactor) + 1.0F;
			int t = ((ft < (float)MAXIMUM_CAPACITY) ?
					 (int)ft : MAXIMUM_CAPACITY);
			if (t > threshold)
				threshold = tableSizeFor(t);
		}
		else if (s > threshold)
			resize();
		for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
			K key = e.getKey();
			V value = e.getValue();
			//put方法的具体实现，后边讲
			putVal(hash(key), key, value, false, evict);
		}
	}
}

需要注意的是：

使用默认的构造器，阈值被默认设置为了0，也就是在第一次添加元素时，就会进行扩容。
无论如何创建一个HashMap实例，在resize扩容之前，其capacity值一定是0!!!
给定初始容量、初始载入因子的构造方法，返回的容量值没有直接给capacity，而是赋值给了threshold，在第一次resize时根据该值修改capacity

tableSizeFor()

上边的第三个构造函数中，调用了 tableSizeFor 方法，这个方法是怎么实现的呢？

static final int tableSizeFor(int cap) {
	int n = cap - 1;
	n |= n >>> 1;
	n |= n >>> 2;
	n |= n >>> 4;
	n |= n >>> 8;
	n |= n >>> 16;
	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

我们以传入参数为14 来举例，计算这个过程。i

首先，14传进去之后先减1，n此时为13。然后是一系列的无符号右移运算>>>。

//13的二进制
0000 0000 0000 0000 0000 0000 0000 1101 
//无右移1位，高位补0
0000 0000 0000 0000 0000 0000 0000 0110 
//然后把它和原来的13做或运算得到，此时的n值
0000 0000 0000 0000 0000 0000 0000 1111 
//再以上边的值，右移2位
0000 0000 0000 0000 0000 0000 0000 0011
//然后和第一次或运算之后的 n 值再做或运算，此时得到的n值
0000 0000 0000 0000 0000 0000 0000 1111
...
//我们会发现，再执行右移 4,8,16位，同样n的值不变
//当n小于0时，返回1，否则判断是否大于最大容量，是的话返回最大容量，否则返回 n+1
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
//很明显我们这里返回的是 n+1 的值，
0000 0000 0000 0000 0000 0000 0000 1111
+                                     1
0000 0000 0000 0000 0000 0000 0001 0000

将它转为十进制，就是 2^4 = 16 。我们会发现一个规律，以上的右移运算使得从值为1的最高位开始后所有位的值设置为1。计算结束后一定再加1，就是1 0000 这样的结构，它一定是 2的n次幂。因此，这个方法返回的就是大于当前传入值的最小（最接近当前值）的一个2的n次幂的值。

4、put方法详解

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // 桶数组
    Node<K,V>[] tab;
    // key、value包装了一个Node对象，用于存储
    Node<K,V> p;
    // i ---> 所处桶的索引
    // n ---> 桶的大小
    int n, i;
    // 桶数组为空，进行resize扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 判断如果桶数组该下标为空
    // 此时该桶中没有任何的结点，新建一个Node放进去
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 出现了hash冲突
    else {
        // e表示需要覆盖的结点
        Node<K,V> e;
        // k为key值
        K k;
        // 第一个Node结点是否与put的Node相同
        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);
        // 循环查找桶中的链表
        else {
            for (int binCount = 0; ; ++binCount) {
                // 已经到了末尾
                if ((e = p.next) == null) {
                    // jdk8.0以上都是使用尾插法添加元素
                    p.next = newNode(hash, key, value, null);
                    // 桶中结点数量 > 8, 调用treeifyBin 转化为红黑树或扩容
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 判断相同
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // hash值与key值均相同，将添加的value替换该结点曾经的value
        // 需要覆盖
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 判断容量是否需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

首先将k,v封装到Node对象当中（节点）。
然后它的底层会调用K的hashCode()方法得出hash值。
通过哈希表函数/哈希算法，将hash值转换成数组的下标(使用hashcode&(n-1))，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equals。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。

5、get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 返回找到的结点，没有找到就返回null
final Node<K,V> getNode(int hash, Object key) {
    //Entry对象数组
    Node<K,V>[] tab;
    //tab数组中经过散列的第一个位置
    Node<K,V> first, e;
    int n;
    K k;
    // 当前桶数组有元素就查找，没有元素直接返回
    if ((tab = table) != null && (n = tab.length) > 0 &&
        //first=tab[(n-1)&hash] 找到桶数组中的具体下标，接着在链表或红黑树中查找
        (first = tab[(n - 1) & hash]) != null) {
        // 检查第一个Node是否是查找的Node
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 查找first后面的Node
        if ((e = first.next) != null) {
            //如果已经转换为红黑树进行红黑树查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //继续查找链表的下一个结点直到找到的话为空
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。

6、hash()计算原理

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

这里，会先判断key是否为空，若为空则返回0。这也说明了hashMap是支持key传 null 的。若非空，则先计算key的hashCode值，赋值给h，然后把h右移16位，并与原来的h进行异或处理。这里就引申出下面几个问题：

为什么不直接调用key.hashCode()而还需让高16位与低16位执行异或操作？

答：为了增加随机性。上面式子其实是将高16位与低16位进行了一个异或操作，因为根据哈希值确定数组位置的方法时hash&(n-1),n-1的大小不会很大，也就是说只有低位的hash值才影响数组的位置，而hash值原本有32位，高位的哈希特征全部都消失了，出现哈希冲突的概率就增加了，因此使用异或操作使得低位和高位均能够影响数组的位置。所以，异或运算之后，可以让结果的随机性更大，而随机性大了之后，哈希碰撞的概率当然就更小了。

为什么一定是异或操作？

能够确保结果足够分散：

7、resize()扩容机制

在添加一个新的元素后，会判断当前数组的容量是否超过阈值，如果容量>=阈值则会进行扩容。同样当开始数组为空时也同样会进行扩容。

final Node<K,V>[] resize() {
	//旧数组
	Node<K,V>[] oldTab = table;
	//旧数组的容量
	int oldCap = (oldTab == null) ? 0 : oldTab.length;
	//旧数组的扩容阈值，注意看，这里取的是当前对象的 threshold 值，下边的第2种情况会用到。
	int oldThr = threshold;
	//初始化新数组的容量和阈值，分三种情况讨论。
	int newCap, newThr = 0;
	//1.当旧数组的容量大于0时，说明在这之前肯定调用过 resize扩容过一次，才会导致旧容量不为0。
	//为什么这样说呢，之前我在 tableSizeFor 卖了个关子，需要注意的是，它返回的值是赋给了 threshold 而不是 capacity。
	//我们在这之前，压根就没有在任何地方看到过，它给 capacity 赋初始值。
	if (oldCap > 0) {
		//容量达到了最大值
		if (oldCap >= MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return oldTab;
		}
		//新数组的容量和阈值都扩大原来的2倍
		else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
				 oldCap >= DEFAULT_INITIAL_CAPACITY)
			newThr = oldThr << 1; // double threshold
	}
	//2.到这里，说明 oldCap <= 0，并且 oldThr(threshold) > 0，这就是 map 初始化的时候，第一次调用 resize的情况
	//而 oldThr的值等于 threshold，此时的 threshold 是通过 tableSizeFor 方法得到的一个2的n次幂的值(我们以16为例)。
	//因此，需要把 oldThr 的值，也就是 threshold ，赋值给新数组的容量 newCap，以保证数组的容量是2的n次幂。
	//所以我们可以得出结论，当map第一次 put 元素的时候，就会走到这个分支，把数组的容量设置为正确的值（2的n次幂)
	//但是，此时 threshold 的值也是2的n次幂，这不对啊，它应该是数组的容量乘以加载因子才对。别着急，这个会在③处理。
	else if (oldThr > 0) // initial capacity was placed in threshold
		newCap = oldThr;
	//3.到这里，说明 oldCap 和 oldThr 都是小于等于0的。也说明我们的map是通过默认无参构造来创建的，
	//于是，数组的容量和阈值都取默认值就可以了，即 16 和 12。
	else {               // zero initial threshold signifies using defaults
		newCap = DEFAULT_INITIAL_CAPACITY;
		newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
	}
	//③ 这里就是处理第2种情况，因为只有这种情况 newThr 才为0，
	//因此计算 newThr（用 newCap即16 乘以加载因子 0.75，得到 12） ，并把它赋值给 threshold
	if (newThr == 0) {
		float ft = (float)newCap * loadFactor;
		newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
				  (int)ft : Integer.MAX_VALUE);
	}
	//赋予 threshold 正确的值，表示数组下次需要扩容的阈值（此时就把原来的 16 修正为了 12）。
	threshold = newThr;
	@SuppressWarnings({"rawtypes","unchecked"})
	//我们可以发现，在构造函数时，并没有创建数组，在第一次调用put方法，导致resize的时候，才会把数组创建出来。这是为了延迟加载，提高效率。
	Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
	table = newTab;
	//如果原来的数组不为空，那么我们就需要把原来数组中的元素重新分配到新的数组中
	//如果是第2种情况，由于是第一次调用resize，此时数组肯定是空的，因此也就不需要重新分配元素。
	if (oldTab != null) {
		//遍历旧数组
		for (int j = 0; j < oldCap; ++j) {
			Node<K,V> e;
			//取到当前下标的第一个元素，如果存在，则分三种情况重新分配位置
			if ((e = oldTab[j]) != null) {
				oldTab[j] = null;
				//1.如果当前元素的下一个元素为空，则说明此处只有一个元素
				//则直接用它的hash()值和新数组的容量取模就可以了，得到新的下标位置。
				if (e.next == null)
					newTab[e.hash & (newCap - 1)] = e;
				//2.如果是红黑树结构，则拆分红黑树，必要时有可能退化为链表
				else if (e instanceof TreeNode)
					((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
				//3.到这里说明，这是一个长度大于 1 的普通链表，则需要计算并
				//判断当前位置的链表是否需要移动到新的位置
				else { // preserve order
					// loHead 和 loTail 分别代表链表旧位置的头尾节点
					Node<K,V> loHead = null, loTail = null;
					// hiHead 和 hiTail 分别代表链表移动到新位置的头尾节点
					Node<K,V> hiHead = null, hiTail = null;
					Node<K,V> next;
					do {
						next = e.next;
						//如果当前元素的hash值和oldCap做与运算为0，则原位置不变
						if ((e.hash & oldCap) == 0) {
							if (loTail == null)
								loHead = e;
							else
								loTail.next = e;
							loTail = e;
						}
						//否则，需要移动到新的位置
						else {
							if (hiTail == null)
								hiHead = e;
							else
								hiTail.next = e;
							hiTail = e;
						}
					} while ((e = next) != null);
					//原位置不变的一条链表，数组下标不变
					if (loTail != null) {
						loTail.next = null;
						newTab[j] = loHead;
					}
					//移动到新位置的一条链表，数组下标为原下标加上旧数组的容量
					if (hiTail != null) {
						hiTail.next = null;
						newTab[j + oldCap] = hiHead;
					}
				}
			}
		}
	}
	return newTab;
}

这里还有一个重要的运算需要注意,使用这个判断用于将原来的链表分为两个链表，分别位于原来位置和一个新的位置

//如果当前元素的hash值和oldCap做与运算为0，则原位置不变
if ((e.hash & oldCap) == 0) {
    if (loTail == null)
        loHead = e;
    else
        loTail.next = e;
    loTail = e;
}

这里拿原容量为16，扩容后容量为32为例，判断数组具体位置的(n-1)&key.hashCode()

//16容量判断具体位置
1111 & key.hashCode()
//32容量判断具体位置
11111 & key.hashCode()

16容量时是不考虑第5位的值，无论其实1或0都是放在这个位置上，但是现在容量被扩充为32位，需要考虑哈希值的第5位值，如果为0也跟16容量时获得的位置相同，如果为1得到一个新的位置，因此e.hash & oldCap 直接判断第5位的值即可知道其是否能留在原位置。其他情况也类似

8、常见的一些面试问题

问题1：jdk1.7的HashMap扩容时为什么会出现死循环？

先看看jdk1.7的HashMap的扩容代码，核心思路是遍历所有的桶元素并将其插入到适合的位置，插入时使用**头插法**插入。

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for(Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if(rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //计算在新table中的位置
            int i = indexFor(e.hash, newCapacity);
            //一下三行就实现了头插法
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

出现问题的核心位置就是这句：Entry<K,V>next=e.next，当然正常情况下是不会出现问题的，问题只会在多线程操作Map时出现。

举例说明，假设桶的大小为2，同种的元素如下所示：

假设现在有两个线程：线程1与线程2，这两个线程均需要对HashMap进行扩容操作。

假设线程1先执行扩容方法，在执行完Entry<K,V>next=e.next之后，因为时间片用完被操作系统挂起，轮线程2执行，此时线程1中的e与next分别如上面图所示。

线程1被挂起后并没有完成扩容，因此线程2进入后同样会执行扩容方法，并且线程2将扩容方法执行完成，HashMap已经成功被扩容！但是线程1中e、next所指向的元素没有改变，线程2扩容后两个指向如图所示：

线程1中还没有开始扩容，所以newTable还只是一个长度为4的空数组，如上图左侧所示。table是已经被线程2扩容后的桶数组，如上图右侧图所示。

随后开始执行e.next=newTable[i]、newTable[i]=e，因为newTable此时是空数组，因此e.next==null，此时newTable[i]=e，随后执行e=next让指针e与指针next都指向同一个元素key(7)，如下图所示:
第二次循环执行Entry<K,V>next=e.next，next指向key(3)：
执行e.next=newTable[i]、newTable[i]=e，将key(7)用头插法插入到第三号桶中：继续执行e=next，此时e再一次指向了key(3)
第三次循环执行Entry<K,V>next=e.next，此时next == null，执行e.next=newTable[i]也就是将左侧线程1中的key(3)指向线程1中的头结点key(7)，这样形成了循环链表！继续执行newTable[i]=e并没有产生变化。随后e=next让e为空结束循环。
此时扩容已经结束，可以看到桶数组中存放的链表已经变成了循环链表，任何的操作都可能导致死循环。这也就是为什么在jdk8.0之后HashMap的扩容方式改为了尾插法。

问题2：HashMap与HashTable有什么区别？

1、继承的类不同

HashMap继承自abstractHashMap而HashTable继承自Dictionary，两者均实现了Map接口。Dictionary是一个相当古老的类，官方已经废弃了这个类的使用。

2、HashMap线程不安全，HashTable线程安全

HashMap不是一个线程安全的数据结构，在前面也说到多线程情况下jdk1.7的HashMap可能出现循环链表导致查询时出现死循环。同时HashMap因为没有数据上锁机制因此put方法可能覆盖其他线程的修改。总体来说HashMap线程不安全。

HashTable通过synchornized关键字实现线程安全，但是这种实现方法需要大量的上锁、解锁工作，性能较差，因此也不推荐使用HashTable保证线程安全。

3、HashTable不允许存放空值

HashMap允许存放一个null的key值，value值没有null值限制，但是HashTable键值对均不能为空。

4、计算Hash的方式不同

HashMap计算Hash值的方法：

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

HashTable计算Hash值的方法：

int index = (e.hash & 0x7FFFFFFF) % newCapacity;

5、扩容方式不同

HashMap的扩容是原始容量的两倍
HashTable的扩容方式是原始容量的两倍+1

6、解决Hash冲突的方式不同

HashMap中如果出现Hash冲突时，如果冲突数量小于8 则会以尾部添加的链表方式存储，冲突数量大于8且桶数组数量大于64则会将链表转为红黑树存储，当数量又小于6时就会将红黑树转为链表存储，平均查询时间复杂度： $O (l g n)$
HashTable中出现Hash冲突只有链表解决方式，将冲突的结点添加到链表，解决Hash冲突，时间复杂度较高。