java容器源码分析--HashMap（JDK1.8）

JAVA_java容器 源码分析

本篇结构：

• 前言
• 数据结构
• 常用方法及遍历选择
• 重要参数
• 源码分析
• 疑问解答

一、前言

HashMap在日常软件开发中用得很多，它很方便，使用也简单，这样一个经常陪在我们身边的容器对象，当然应该好好研究一下啦，毕竟了解了本质，才能更好的相处。这和日常处朋友是一样的。

二、数据结构

2.1、基本数据结构

数据结构的知识是薄弱环节，这里就只简单介绍下HashMap的结构。

在JDK1.8之前，HashMap的实现是基于数组+链表的形式，当往一个HashMap中放数据时，根据key计算得到hashCode，经过进一步处理得到数组（Hash表）的下标，然后存放数据。

如果存在两个key，计算出相同的数组下标，即出现hash冲突，这时就通过一个链表来维持这个关系，后put的值放在链表的尾部。

大致是这样的结构：

为解决哈希碰撞后出现链表过程导致索引效率变慢的问题，JDK1.8之后引入了红黑树（链表的时间复杂度是O(n)，红黑树为O(logn)），当链表长度大于8后，链表转为红黑树。

ps:漫画算法：什么是红黑树？

2.2、HashMap数组元素和链表的节点

HashMap中存的是Key-Valve键值对。

1.数组元素和链表节点是采用Node类实现

Node类是HashMap中的一个静态内部类，实现了Map.Entry接口（在JDK1.8之前，是采用Entry类实现）。

可以看看Node类的源码：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // 哈希值，HashMap根据该值确定记录的位置
    final K key; // key
    V value; // 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;
    }
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    // 判断2个Node是否相等的依据是Key和Value都相等
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

2.红黑树节点是采用TreeNode类实现

TreeNode也是HashMap的静态内部类，继承LinkedHashMap.Entry，简单列下TreeNode中的属性：

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);
    }
    /**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
    ...
}

三、常用方法及遍历选择

V get(Object key); // 获得指定键的值
V put(K key, V value); // 添加键值对
void putAll(Map m); // 将指定Map中的键值对 复制到此Map中
V remove(Object key); // 删除该键值对
boolean containsKey(Object key); // 判断是否存在该键的键值对；是 则返回true boolean
containsValue(Object value); // 判断是否存在该值的键值对；是 则返回true
Set keySet(); // 单独抽取key序列，将所有key生成一个Set
Collection values(); // 单独value序列，将所有value生成一个Collection
void clear(); // 清除哈希表中的所有键值对
int size(); // 返回哈希表中所有键值对的数量 = 数组中的键值对 + 链表中的键值对
boolean isEmpty(); // 判断HashMap是否为空；size == 0时 表示为空

public class HashMapTest {
    public static void main(String[] args) {
        // 1. new
        Map<String, Integer> map = new HashMap<String, Integer>();
        // 2. put
        map.put("Android", 1);
        map.put("Java", 2);
        map.put("iOS", 3);
        // 3. get
        System.out.println("key = Java：" + map.get("Java"));
        // 4. 遍历HashMap ------------ start
        // 核心思想：
        // 步骤1：获得key-value对（Entry） 或 key 或 value的Set集合
        // 步骤2：遍历上述Set集合(使用for循环 、 迭代器（Iterator）均可)
        // 方法共有3种：分别针对 key-value对（Entry） 或 key 或 value
        // 4.1：获得key-value的Set集合，再遍历
        iterate1(map);
        // 4.2：获得key的Set集合，再遍历
        iterator2(map);
        // 方法3：获得value的Set集合，再遍历
        iterator3(map);
        // 4. 遍历HashMap ------------ end
    }
    /**
     *  获得key-value的Set集合，再遍历
     *  @param map
     */
    static void iterate1(Map<String, Integer> map){
        System.out.println("method 1: iterate Set<Entry<K, V>> start..........");
        // 1.获得key-value对（Entry）的Set集合
        Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
        // 2.遍历Set集合，从而获取key-value
        // 3.for循环
        for(Map.Entry<String, Integer> entry : entrySet){
            System.out.print(entry.getKey());
            System.out.println(entry.getValue());
        }
        System.out.println("method 1: iterate Set<Entry<K, V>> end..........");
    }
    /**
     * 获得key的Set集合，再遍历
     * @param map
     */
    static void iterator2(Map<String, Integer> map){
        System.out.println("method 2: iterate Set<Key> start..........");
        // 1.获得key的Set集合
        Set<String> keySet = map.keySet();
        // 2.遍历Set集合，从而获取key，再获取value
        // 3.for循环
        for(String key : keySet){
            System.out.print(key);
            System.out.println(map.get(key));
        }
        System.out.println("method 2: iterate Set<Key> end..........");
    }
    /**
     *  获得value的Set集合，再遍历
     * @param map
     */
    static void iterator3(Map<String, Integer> map){
        System.out.println("method 3: iterate Set<Value> start..........");
        // 1. 获得value的Set集合
        Collection valueSet = map.values();
        // 2. 遍历Set集合，从而获取value
        // 2.1 获得values 的Iterator
        Iterator iter = valueSet.iterator();
        // 2.2 通过遍历，直接获取value
        while (iter.hasNext()) {
            System.out.println(iter.next());
        }
        System.out.println("method 3: iterate Set<Value> end..........");
    }
}

对于遍历方式，具体的情况有不同的选择：

1. 如果只是遍历key，使用keySet是最好的选择，遍历Map.Entry效率相差不大；
2. 如果只遍历Value，遍历Map.Entry和valueSet都可，而通过keySet的方式效率会稍差，因为要通过get(key)的方式获取value（get的时间复杂度取决于for循环的次数），会多出一部分消耗；
3. 如果既要Key，又要Value，遍历Map.Entry。

四、重要参数

// 默认容量16（1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
// 最大容量 =  2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 实际加载因子
final float loadFactor; 
// 默认加载因子 = 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f; 
// 空的存储实体  
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;  
// 扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量） 
// a. 扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
// b. 扩容阈值 = 容量 x 加载因子
int threshold;
// 存储数据的Node类型数组，长度 = 2的幂；数组的每个元素 = 1个单链表 
transient Node<K,V>[] table;  
// HashMap中存储的键值对的数量
transient int size;
//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
transient int modCount;
/** 
* 与红黑树相关的参数
*/
// 1. 桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树
static final int TREEIFY_THRESHOLD = 8; 
// 2. 桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红黑树转换成链表
static final int UNTREEIFY_THRESHOLD = 6;
// 3. 最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）
// 否则，若桶内元素太多时，则直接扩容，而不是树形化
// 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;

五、源码分析

5.1、构造方法

在常规构造器中，并没有马上为数组table分配内存空间（有一个入参为指定Map的构造器例外），事实上是在执行第一次put操作的时候才真正构建table数组。

先看看如何实例化一个HashMap：

public class HashMapConstructor {
    public static void main(String[] args) {
        Map<String, String> map = constructorMap1();
    }
    static <K, V> Map<K, V> constructorMap1(){
        return new HashMap<>();
    }
    static <K, V> Map<K, V> constructorMap2(int capacity){
        // 实际上是调用指定“容量大小”和“加载因子”的构造函数
        return new HashMap<>(capacity);
    }
    static <K, V> Map<K, V> constructorMap3(int capacity, float loadFactor){
        return new HashMap<>(capacity, loadFactor);
    }
    static <K, V> Map<K, V> constructorMap4(Map<K, V> map){
        return new HashMap<>(map);
    }
}

再来看具体的源码：

/**
 *  构造函数1：默认构造函数（无参）
 *  加载因子 & 容量（默认） = 0.75、16
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}
/**
 *  构造函数2：指定“容量大小”的构造函数
 *  加载因子（默认）= 0.75 、容量 = 指定大小
 *  注：此处不是真正的阈值，仅仅只是将传入的容量大小转化为：>传入容量大小的最小的2的幂，该阈值后面会重新计算
 */
public HashMap(int initialCapacity) {
    // 实际上是调用指定“容量大小”和“加载因子”的构造函数
    // 只是在传入的加载因子参数 = 默认加载因子
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
 *  构造函数3：指定“容量大小”和“加载因子”的构造函数
 *  注：此处不是真正的阈值，仅仅只是将传入的容量大小转化为：>传入容量大 小的最小的2的幂，该阈值后面会重新计算
 */
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;
    this.threshold = tableSizeFor(initialCapacity);
}
/**
 * 将传入的容量大小转化为：>大于传入容量大小的最小的2的幂
 */
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;
}
/**
 *  构造函数4：包含“子Map”的构造函数
 *  即 构造出来的HashMap包含传入Map的映射关系
 *  加载因子 & 容量（默认） = 0.75、16
 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    // 将传入的子Map中的全部元素逐个添加到HashMap中
    putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 判断table是否已经初始化
        if (table == null) { // pre-size
            // 未初始化，s为m的实际元素个数
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // 计算得到的t大于阈值，则初始化阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 已初始化，并且m元素个数大于阈值，进行扩容处理
        else if (s > threshold)
            resize();
        // 将m中的所有元素添加至HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

5.2、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; Node<K,V> p; int n, i;
    // 1.table未初始化或者长度为0，进行扩容
    // 这里可以发现初始化哈希表的时机 = 第1次调用put函数时，即调用resize() 初始化创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2.计算插入存储的数组索引i：(n - 1) & hash 
    // 3.取出数组中该索引处的元素（也是链表中的第一个Node元素），若为空，则直接在该数组位置新建节点，插入完毕
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 4.若不为空，即该索引处已经有节点元素存在，需判断是否有hash冲突
    else {
        Node<K,V> e; K k;
        // a.如果桶中第一个元素(即链表中的第一个节点，也即数组中的节点)和新加入的元素的hash值相等，key相等，会直接用新值替换旧值
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 将第一个元素赋值给e
            e = p;
        // b.若新插入的元素与桶中第一个元素hash值不相等，即key不相等，需判断是链表还是红黑树
        // 若为红黑树，调用相应方法加入
        else if (p instanceof TreeNode)
            // 放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 若是为链表
        else {
            // 遍历链表
            for (int binCount = 0; ; ++binCount) {
                // (e = p.next) == null表示到达链表的尾部，如果成立，说明链表中没有节点的Key值和新加入的元素的Key值相同
                if ((e = p.next) == null) {
                    // 在链表最末插入结点
                    p.next = newNode(hash, key, value, null);
                    // 结点数量达到阈值，转化为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 跳出循环    
                    break;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        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;
}

put方法大致过程：

1.如果是第一次调用put，会先调用resize方法初始化table数组，默认容量16；
2.计算插入存储的数组索引i，判断该索引下数组是否有Node节点，若没有，直接插入；
3.若存在，需判断是否有hash冲突：
a.若新插入的Key和数组中该索引下的Node元素Key（链表中的第一个Node元素）相同（hash相同，Key也相同），则直接替换；
b.若新插入的Key与链表中的第一个Node元素Key不相同，就接着遍历，分链表和红黑树两种形式，都是存在就替换，不存在就加入；
4.插入成功后，判断实际存在的键值对数量size > 最大容量threshold，进而决定是否需要扩容。

5.3、get

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // table已经初始化，长度大于0，并且根据hash寻找table中的项（也即链表中的首节点）也不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 桶中第一项(数组元素)相等，直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 否则遍历桶中的节点
        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;
}

5.4、resize

final Node<K,V>[] resize() {
    // 保存之前table为old table
    Node<K,V>[] oldTab = table;
    // 保存之前table大小
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 保存之前table阈值 
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 之前table大小大于0
    if (oldCap > 0) {
        // 之前table大于最大容量
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 阈值为最大整形，直接返回
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 容量翻倍（使用左移，效率更高）后，小于最大容量
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 阈值翻倍，使用左移，效率更高
            newThr = oldThr << 1; // double threshold
    }
    // 之前阈值大于0
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 之前容量oldCap = 0并且之前阈值oldThr = 0，使用缺省值（如使用HashMap()构造函数，之后再插入一个元素会调用resize函数，会进入这一步）
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 新阈值为0
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 更新阈值
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 新初始化一个newCap容量大小的table
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 更新table数组
    table = newTab;
    // 之前的table已经初始化过
    if (oldTab != null) {
        // 复制元素，重新进行hash
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        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分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。

六、疑问解答

6.1、HashMap的长度为什么要是2的n次方？

1.效率更高

一般利用hash码计算出一个数组的索引，常用方式是"h % length"，也就是求余的方式，但这种方式效率不如位运算，恰好又有"当容量是2^n时，h & (length - 1) == h % length"。

2.更符合Hash算法均匀分布，减少碰撞

length-1的值是所有二进制位全为1，这种情况下，index 的结果等同于 HashCode 后几位的值，只要输入的 HashCode 本身分布均匀，Hash 算法的结果就是均匀的。

HashMap的长度为什么设置为2的n次方

6.2、modCount变量的作用

public void forEach(BiConsumer<? super K, ? super V> action) {
    Node<K,V>[] tab;
    if (action == null)
        throw new NullPointerException();
    if (size > 0 && (tab = table) != null) {
        int mc = modCount;
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next)
                action.accept(e.key, e.value);
        }
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

从forEach循环中可以发现 modCount 参数的作用。就是在迭代器迭代Map中的元素时，不能编辑（增加，删除，修改）Map中的元素。如果在迭代时修改，则抛出ConcurrentModificationException异常。

6.3、为什么在计算数组下标前，需对哈希码进行二次处理：扰动处理？

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

这是JDK1.8中根据Key计算hash值的方法，然后用这个hash值去计算数组下标(hash & (length-1))，观察上面的 hash 方法，发现并不是直接用 hashCode 与 length-1 做位运算，而是(h = key.hashCode()) ^ (h >>> 16)，为什么这么处理？

是为了加大哈希码低位的随机性（因为 length 是2的n次方， length-1 的二进制全是1，这样同 hash 值与运算时，数组下标就取决于 hash 值的低位），使得分布更均匀，从而提高对应数组存储下标位置的随机性 & 均匀性，最终减少Hash冲突。

6.4、为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键

因为String是不可变的，而且已经重写了equals()和hashCode()方法了。其他的包装类也有这个特点。

不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。

不可变性还有其他的优点如线程安全。如果可以仅仅通过将某个field声明成final就能保证hashCode是不变的，那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。

6.5、重新调整HashMap大小存在什么问题吗？

当多线程的情况下，可能产生条件竞争，如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。

JDK1.7中，在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。

此时若（多线程）并发执行 put（）操作，一旦出现扩容情况，则 容易出现 环形链表，从而在获取数据、遍历链表时 形成死循环（Infinite Loop），即 死锁的状态。

JDK1.7相关扩容：

void resize(int newCapacity) {  
    // 1. 保存旧数组（old table） 
    Entry[] oldTable = table;  
    // 2. 保存旧容量（old capacity ），即数组长度
    int oldCapacity = oldTable.length; 
    // 3. 若旧容量已经是系统默认最大容量了，那么将阈值设置成整型的最大值，退出    
    if (oldCapacity == MAXIMUM_CAPACITY) {  
        threshold = Integer.MAX_VALUE;  
        return;  
    }  
    // 4. 根据新容量（2倍容量）新建1个数组，即新table  
    Entry[] newTable = new Entry[newCapacity];  
    // 5. （重点分析）将旧数组上的数据（键值对）转移到新table中，从而完成扩容 ->>分析1.1 
    transfer(newTable); 
    // 6. 新数组table引用到HashMap的table属性上
    table = newTable;  
    // 7. 重新设置阈值  
    threshold = (int)(newCapacity * loadFactor); 
} 
/**
 * 作用：将旧数组上的数据（键值对）转移到新table中，从而完成扩容
 * 过程：按旧链表的正序遍历链表、在新链表的头部依次插入
 */
void transfer(Entry[] newTable) {
    // 1. src引用了旧数组
    Entry[] src = table;
    // 2. 获取新数组的大小 = 获取新容量大小                 
    int newCapacity = newTable.length;
    // 3. 通过遍历 旧数组，将旧数组上的数据（键值对）转移到新数组中
    for (int j = 0; j < src.length; j++) {
        // 3.1 取得旧数组的每个元素  
        Entry<K, V> e = src[j];
        if (e != null) {
            // 3.2 释放旧数组的对象引用（for循环后，旧数组不再引用任何对象）
            src[j] = null;
            do {
                // 3.3 遍历 以该数组元素为首 的链表
                // 注：转移链表时，因是单链表，故要保存下1个结点，否则转移后链表会断开
                Entry<K, V> next = e.next;
                // 3.3 重新计算每个元素的存储位置
                int i = indexFor(e.hash, newCapacity);
                // 3.4 将元素放在数组上：采用单链表的头插入方式 = 在链表头上存放数据 = 将数组位置的原有数据放在后1个指针、将需放入的数据放到数组位置中
                // 即 扩容后，可能出现逆序：按旧链表的正序遍历链表、在新链表的头部依次插入
                e.next = newTable[i];
                newTable[i] = e;
                // 访问下1个Entry链上的元素，如此不断循环，直到遍历完该链表上的所有节点
                e = next;
            } while (e != null);
            // 如此不断循环，直到遍历完数组上的所有数据元素
        }
    }
}

JDK 1.8 转移数据操作 = 按旧链表的正序遍历链表、在新链表的尾部依次插入，所以不会出现链表 逆序、倒置的情况，故不容易出现环形链表的情况。但 JDK 1.8 还是线程不安全，因为无加同步锁保护。

参考博文：

Java源码分析：关于 HashMap 1.8 的重大更新