[数据结构与算法]HashMap底层源码及常见问题，再也不怕面试官在这方面的逼问了

HashMap的底层源码

JDK 1.8 对 HashMap 进行了比较大的优化，底层实现由之前的 “数组+链表” 改为 “数组+链表+红黑树”，本文就 HashMap 的几个常用的重要方法和 JDK 1.8 之前的死循环问题展开学习讨论。

JDK 1.8 的 HashMap 的数据结构如下图所示，当链表节点较少时仍然是以链表存在，当链表节点较多时（大于8）会转为红黑树。

参数

 // 初始容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表节点转换红黑树节点的阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 转红黑树时table的最小长度
static final int MIN_TREEIFY_CAPACITY = 64;
// 链表节点, 继承自Entry
static class Node<K,V> implements Map.Entry<K,V> {  
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
 
    // ... ...
}

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
}
 

属性

// 哈希表的负载因子。
final float loadFactor;

// 键值对的数量
transient int size;

// 表示修改的次数
transient int modCount;

//该表在首次使用时初始化，并根据需要调整大小。分配时，长度始终是 2 的幂。
transient Node<K,V>[] table;

构造方法

	//构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空HashMap 
	public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

	//
	public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
	// this 方法就是该方法
	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;
        // 如果进来10 threshold值将被赋值为16
        this.threshold = tableSizeFor(initialCapacity);
    }

    // 获取比给定容量大的最小二次方
	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;
    }

get 方法

返回指定键映射到的值，如果此映射不包含该键的映射，则返回null 。

	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且哈希对应的索引位置的table不为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 检查first节点的hash值和key是否和入参的一样，如果一样则first即为目标节点，直接返回first节点
            if (first.hash == hash && 
                ((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;
    }	

如果是红黑树节点，则调用红黑树的查找目标节点方法 getTreeNode

final TreeNode<K,V> getTreeNode(int h, Object k) {
    // 首先找到红黑树的根节点；使用根节点调用find方法
    return ((parent != null) ? root() : this).find(h, k, null);
}

/**
 * 从调用此方法的节点开始查找, 通过hash值和key找到对应的节点
 * 此方法是红黑树节点的查找, 红黑树是特殊的自平衡二叉查找树
 * 平衡二叉查找树的特点：左节点<根节点<右节点
 */
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    // 将p节点赋值为调用此方法的节点，即为红黑树根节点
    TreeNode<K,V> p = this;
    // 从p节点开始向下遍历
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        // 如果传入的hash值小于p节点的hash值，则往p节点的左边遍历
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h) // 如果传入的hash值大于p节点的hash值，则往p节点的右边遍历
            p = pr;
        // 如果传入的hash值和key值等于p节点的hash值和key值,则p节点为目标节点,返回p节点
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)    // p节点的左节点为空则将向右遍历
            p = pr;
        else if (pr == null)    // p节点的右节点为空则向左遍历
            p = pl;
        // 将p节点与k进行比较
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) && //  kc不为空代表k实现了Comparable
                 (dir = compareComparables(kc, k, pk)) != 0)//  k<pk则dir<0, k>pk则dir>0
            // k<pk则向左遍历(p赋值为p的左节点), 否则向右遍历
            p = (dir < 0) ? pl : pr;
        // 代码走到此处, 代表key所属类没有实现Comparable, 直接指定向p的右边遍历
        else if ((q = pr.find(h, k, kc)) != null) 
            return q;
        // 代码走到此处代表“pr.find(h, k, kc)”为空, 因此直接向左遍历
        else
            p = pl;
    } while (p != null);
    return null;
}

put 方法

// 将指定的值与此映射中的指定键相关联。如果映射先前包含键的映射，则替换旧值。
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

传进来的key会通过调用hash()方法来计算出哈希值(先用本地hashcode方法，与其右移16位进行异或操作，进行扰动扰动),目的是为了降低 hash 冲突的概率。

让高位也参加到运算当中来

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

真正的put方法

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        /
        //初始化变量 tab用来存放数组，n用来存放长度  i表示数组的下标
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 为什么不直接用table操作  因为用tab会让堆中变量引入到栈中来，操作更快
        // 初始化数组复制给table(resize 方法里包括初始化数组和扩容)
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 计算出下标 i（哈希值和数组长度与运算） 判断该下标下有没有值，没有值就新建node放进去
        // (n - 1) & hash  限制了HashMap的数组只能是2的幂次方
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 判断键是都相同，
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // TreeNode 是 Node的子类  不仅仅是棵树，也是双向链表
            else if (p instanceof TreeNode)
                // 红黑树的插入方法
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 是链表的情况
            else {
                // for循环找到最后一个结点  binCount 表示我们走过几个结点
                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;
                    }
                    // 比较结点是否相等
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 如果键相同，先保存老值
            if (e != null) {
                V oldValue = e.value;
                // onlyIfAbsent 为传入的布尔参数，如果他为true并且value不为空，才不会改变原来的值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 记录操作数
        ++modCount;
        // 看是否大于阈值，判断扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

resize 方法

resize 方法里包括初始化数组和扩容

	final Node<K,V>[] resize() {
        // 传入原数组
        Node<K,V>[] oldTab = table;
        // 给定数组长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 传入扩容量
        int oldThr = threshold;
        int newCap, newThr = 0;
        // 如果原数组不为空
        if (oldCap > 0) {
            // 判断老表的容量是否超过最大容量值：如果超过则将阈值设置为Integer.MAX_VALUE，并直接返回老表
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 将新表的容量赋值为原表的两倍，如果它小于最大容量且员表容量大于16，那么将新阈值设置为原来的两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        // 如果原表容量为0但是扩容量不为0，那就把新表容量设置为源表的容量
        else if (oldThr > 0)
            newCap = oldThr;
        else {
            // 无参构造创建的空表，将阈值和扩容量都设置为默认值
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 如果新表阈值为空，则通过容量*负载因子计算阈值
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 将当前阈值设置为刚计算出来的新的阈值，定义新表，容量为刚计算出来的新容量，将table设置为新定义的表
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // 如果原表不为空，那么需要遍历所有结点，将结点值赋值给新表
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                // 将索引值为j的原表头节点赋值给e
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;//把表头设置为空
                    // 如果没有下个结点了，直接移动到新表中
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    // 如果有结点且是红黑树结点，则进行红黑树的重hash分布
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 否则就是链表的重哈希
                    else { 
                        Node<K,V> loHead = null, loTail = null;//存储索引为原位置的结点
                        Node<K,V> hiHead = null, hiTail = null;//存储索引为新位置的结点
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // 如果e的hash值与老表的容量进行与运算为0,则扩容后的索引位置跟老表的索引位置一样
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)// 如果loTail为空, 代表该节点为第一个节点
                                    loHead = e;// 则将loHead赋值为第一个节点
                                else
                                    loTail.next = e; // 否则将结点添加在loTail后面
                                loTail = e;// 并将loTail赋值为新增的节点
                            }
                            // 如果e的hash值与老表的容量进行与运算为非0,则扩容后的索引位置为:老表的索引位置＋oldCap
                            else {
                                if (hiTail == null) // 如果高位尾为空，代表该节点为第一个结点
                                    hiHead = e; // 则将头赋值为第一个结点
                                else
                                    hiTail.next = e; // 否则将结点添加在 hiTail后面
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 如果loTail不为空（说明老表的数据有分布到新表上“原索引位置”的节点），则将最后一个节点的next设为空，并将新表上索引位置为“原索引位置”的节点设置为对应的头节点
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 同低位
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

红黑树的重新hash方法 split()

/**
 * 扩容后，红黑树的hash分布，只可能存在于两个位置：原索引位置、原索引位置+oldCap
 */
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;	// 拿到调用此方法的节点
    TreeNode<K,V> loHead = null, loTail = null; // 存储索引位置为:“原索引位置”的节点
    TreeNode<K,V> hiHead = null, hiTail = null; // 存储索引位置为:“原索引+oldCap”的节点
    int lc = 0, hc = 0;
    // 1.以调用此方法的节点开始，遍历整个红黑树节点
    for (TreeNode<K,V> e = b, next; e != null; e = next) {	// 从b节点开始遍历
        next = (TreeNode<K,V>)e.next;   // next赋值为e的下个节点
        e.next = null;  // 同时将老表的节点设置为空，以便垃圾收集器回收
        // 2.如果e的hash值与老表的容量进行与运算为0,则扩容后的索引位置跟老表的索引位置一样
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)  // 如果loTail为空, 代表该节点为第一个节点
                loHead = e; // 则将loHead赋值为第一个节点
            else
                loTail.next = e;    // 否则将节点添加在loTail后面
            loTail = e; // 并将loTail赋值为新增的节点
            ++lc;   // 统计原索引位置的节点个数
        }
        // 3.如果e的hash值与老表的容量进行与运算为非0,则扩容后的索引位置为:老表的索引位置＋oldCap
        else {
            if ((e.prev = hiTail) == null)  // 如果hiHead为空, 代表该节点为第一个节点
                hiHead = e; // 则将hiHead赋值为第一个节点
            else
                hiTail.next = e;    // 否则将节点添加在hiTail后面
            hiTail = e; // 并将hiTail赋值为新增的节点
            ++hc;   // 统计索引位置为原索引+oldCap的节点个数
        }
    }
    // 4.如果原索引位置的节点不为空
    if (loHead != null) {   // 原索引位置的节点不为空
        // 4.1 如果节点个数<=6个则将红黑树转为链表结构
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            // 4.2 将原索引位置的节点设置为对应的头节点
            tab[index] = loHead;
            // 4.3 如果hiHead不为空，则代表原来的红黑树(老表的红黑树由于节点被分到两个位置)
            // 已经被改变, 需要重新构建新的红黑树
            if (hiHead != null)
                // 4.4 以loHead为根节点, 构建新的红黑树
                loHead.treeify(tab);
        }
    }
    // 5.如果索引位置为原索引+oldCap的节点不为空
    if (hiHead != null) {   // 索引位置为原索引+oldCap的节点不为空
        // 5.1 如果节点个数<=6个则将红黑树转为链表结构
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            // 5.2 将索引位置为原索引+oldCap的节点设置为对应的头节点
            tab[index + bit] = hiHead;
            // 5.3 loHead不为空则代表原来的红黑树(老表的红黑树由于节点被分到两个位置)
            // 已经被改变, 需要重新构建新的红黑树
            if (loHead != null)
                // 5.4 以hiHead为根节点, 构建新的红黑树
                hiHead.treeify(tab);
        }
    }
}

如果红黑树的结点小于等于6转回链表结构

final Node<K,V> untreeify(HashMap<K,V> map) {
    // hd 指向头结点，tl 指向尾结点
    Node<K,V> hd = null, tl = null; 
    // 从调用该方法的头结点开始遍历，将所有结点转为链表结点
    for (Node<K,V> q = this; q != null; q = q.next) {
        // 调用replacementNode方法构建链表节点
        Node<K,V> p = map.replacementNode(q, null);
        // 如果tl为null, 则代表当前节点为第一个节点, 将hd赋值为该节点
        if (tl == null)
            hd = p;
        // 否则, 将尾节点的next属性设置为当前节点p
        else
            tl.next = p;
        // 每次都将tl节点指向当前节点, 即尾节点
        tl = p; 
    }
    // 返回转换后的链表的头节点
    return hd;
}

HashMap常见问题

HashMap 和 Hashtable 的区别

• HashMap 允许 key 和 value 为 null，Hashtable 不允许。

• HashMap 的默认初始容量为 16，Hashtable 为 11。

• HashMap 的扩容为原来的 2 倍，Hashtable 的扩容为原来的 2 倍加 1。

• HashMap 是非线程安全的，Hashtable是线程安全的。

• HashMap 的 hash 值重新计算过，Hashtable 直接使用 hashCode。

• HashMap 去掉了 Hashtable 中的 contains 方法。

• HashMap 继承自 AbstractMap 类，Hashtable 继承自 Dictionary 类。

HashMap的底层数据结构是什么

? 在jdk1.7之前，由数组加链表的形式组成，数组是主体，链表是为了解决哈希冲突存在的。

? 在jdk1.8中，它由数组+链表+红黑数组成，因为如果链表过程，会严重影响HashMap的性能，红黑数搜索的时间复杂度是O(logn)，而链表是O(n)，

转换条件

? 当链表长度大于8且数组长度（数据总量）超过64才会转换为红黑数

? 如果树立量小于64，那么先选择对数组进行扩容，而不是转换为红黑数，减少搜索时间。

说一下HashMap的特点

• HashMap是无序的

• 可以存储一个null值

1. 键是唯一的

• jdk1.8之前底层是数组+链表 1.8之后是数组+链表+红黑数

• 阈值>8并且数组长度大于64才会转换为红黑数，实现高效查询。

• 初始值为16，扩容的负载因子为0.75

解决哈希冲突的方法有哪些？HashMap用的哪种？

开放定址法，再哈希法，链地址法，简历公共溢出区

HashMap中采用的是链地址法

开放定址法也被称为再散列法，基本思想就是p=H(key)出现冲突时，以p为基础再次哈希，p1=H§，如果p1再次出现冲突，则以p1为基础，一次类推，知道一个不冲突的哈希地址pi。因此开放地址法需要hash表的长度大于所需要存放的元素。

因为存在再次哈希，只能在删除的结点上做标记，而不能真正删除结点。

再哈希法又称为双重散列，多重散列，提供了多个不同的hash函数，R1=H1(key1)发生冲突时，再计算R2=H2(key1)，知道没有冲突为止，这样虽然不容易产生堆集，但增加了计算的时间。

链地址法也叫做拉链法，将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行，链表法适用于经常进行插入和删除的情况。

建立公共溢出区，将哈希表分别为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

为什么负载因子设置为0.75，初始化临界值为12？

? 负载因子是什么时候触发扩容的一个条件，负载因子越大，它一次扩容所能容纳的容量就越多，loadFactory越趋近1，那么数组中存放的数据（entry也就越来越多）越多，数据也就越密集，也会有更多的链表长度处于更长的数据，我们的查询效率就会越低，当我们添加数据，产生hash冲突的概率也就越高。

? 默认的loadFactory是0.75，loadFactory越小，越趋近于0，数组中个存放的数据(entry)也就越少，表现得更加稀疏

? 0.75是对空间和时间效率的一种平衡选择。

如果负载因子小一些的话，比如是0.4，那么初始化长度16*0.4=6，数组占满6个空间就进行扩容，会造成大量空 间的浪费 。

如果大一些是0.9，这样会导致扩容之前查找元素的效率变低，

loadfactory设置为0.75是经过多重计算检验得到的可靠值，可以最大程度的减少rehash的次数，避免过多的性能消耗。

哈希表底层采用何种算法计算hash值？还有哪些算法可以计算出hash值？

? hashCode方法是Object中的额方法，所有的类都可以对其进行使用，首先底层调用hashCode方法生成的初始hash值h1，然后将h1无符号右移16位得到h2，只有将h1与h2进行按位异或（^）运算得到最终hash值h3，之后将h3与（length-1)进行按位与（&）运算得到hash表索引。

当两个hashCode相等时会怎么样？

? hsahCode相当于产生hash碰撞，hashCode相等会调用equals方法比较内容是否相等，内容相等则会进行覆盖，如果内容不相等则会连接到链表后方，当链表长度超过8且数组长度超过64会由链表转换为红黑数结点。

合适发生哈希碰撞和什么是哈希碰撞，如何解决哈希碰撞？

? 当两个元素的key计算出的哈希值相等时，就产生了哈希碰撞，如果元素相同则进行覆盖操作，如果不相同，jdk8之前使用的是数组+链表的方式，1.8之后使用的是数组+链表+红黑树方式解决哈希碰撞。

HashMap的put方法流程

以jdk8为例，简要流程如下：

• 首先根据key计算hash值，找到钙元素在数组中存储的下标
• 如果数组是空的吗，则调用resize进行初始化
• 如果没有哈希冲突则直接放进对对应的下标中
• 如果有冲突，且key已经存在，则进行覆盖操作
• 如果冲突后是链表，则判断链表是否大于8，如果大于8并且数组容量小于64，就进行扩容；如果链表数量大于8并且数组的容量大于64，则将这个结构转换成红黑树；否则，链表插入键值对，若key存在，就覆盖掉value
• 如果冲突发生后发现该节点是红黑树，就将该节点挂在树上。

HashMap的扩容方式

? HashMap的容量在超过负载因子所定义的容量后就会进行扩容操作。

? java中的数组是无法自己扩容的，将HashMap的大小扩大为原来数组的两倍。

一般用什么作为HashMap的key？

一般使用String、Integer这种不可变的类来当HashMap的key

• 因为String是不了可变的，当他创建字符串时，它的hashCode被缓存下来，不需要再次计算，相对于其他对象更快
• 因为获得对象时要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的，这些类的规范的重写了hashCode()以及equals()方法8

为什么Map桶中结点个数超过8才转红黑树？

? 树结点占用的空间是普通Node的两倍，如果链表结点不够多却转换为红黑树，无疑会耗费大量的空间资源，并且在随机hash算法下的所有结点分布遵从泊松分布，概率很低，几乎不可能达到8。

• 从平均查找长度来看，红黑树的平均查找长度是logn，如果长度为8，则logn=3，而链表的平均查找长度为n/4，长度为8时，n/2=4，所以阈值8能大大提高搜索速度。
• 当长度为6时红黑树退化为链表是因为logn=log6约等于2.6，而n/2=6/2=3，两者相差不大，而红黑树结点占用更多的内存空间，所以此时转换最好。

什么HashMap线程不安全？

• 多线程下容易死循环。jdk1.7中的HashMap使用头插法插入元素，在多线程环境下，扩容的时候可能导致环形链表的产生，形成死循环。因此jdk1.8之后使用尾插法插入元素，在扩容时会保持元素的原本顺序买不回产生环形链表。
• 多线程的put可能会导致元素丢失。多线程同时执行put操作，如果计算出的索引位置相同，可能造成前一个key被后一个key覆盖，从而导致元素的丢失。此问题在1.7和1.8中都存在。
• put和get并发时，可能导致get为null。线程1执行put时，因为元素个数超出threshold而导致rehash，线程2此时执行get，有可能会导致这个问题。

计算hash值时为什么要让低16bit和高16bit进行异或处理？

? 如果数组很小，比如16，这样的值和hashCode做异或或实际上只有hashCode值的后4位进行运算，hash值是一个随机值，而如果产生的hashCode高位变化很大，而低位变化很小，那么有很大概率造成哈希冲突，所以我们为了使元素更好的散列，将hash值的高位也利用起来。

总结

借鉴博客：https://blog.csdn.net/v123411739/article/details/78996181

• HashMap 的底层是个 Node 数组（Node<K,V>[] table），在数组的具体索引位置，如果存在多个节点，则可能是以链表或红黑树的形式存在。

• 增加、删除、查找键值对时，定位到哈希桶数组的位置是很关键的一步，源码中是通过下面3个操作来完成这一步：1）拿到 key 的 hashCode 值；2）将 hashCode 的高位参与运算，重新计算 hash 值；3）将计算出来的 hash 值与 “table.length - 1” 进行 & 运算。

• HashMap 的默认初始容量（capacity）是 16，capacity 必须为 2 的幂次方；默认负载因子（load factor）是 0.75；实际能存放的节点个数（threshold，即触发扩容的阈值）= capacity * load factor。

• HashMap 在触发扩容后，阈值会变为原来的 2 倍，并且会对所有节点进行重 hash 分布，重 hash 分布后节点的新分布位置只可能有两个：“原索引位置” 或 “原索引+oldCap位置”。例如 capacity 为16，索引位置 5 的节点扩容后，只可能分布在新表 “索引位置5” 和 “索引位置21（5+16）”。

• 导致 HashMap 扩容后，同一个索引位置的节点重 hash 最多分布在两个位置的根本原因是：1）table的长度始终为 2 的 n 次方；2）索引位置的计算方法为 “(table.length - 1) & hash”。HashMap 扩容是一个比较耗时的操作，定义 HashMap 时尽量给个接近的初始容量值。

• HashMap 有 threshold 属性和 loadFactor 属性，但是没有 capacity 属性。初始化时，如果传了初始化容量值，该值是存在 threshold 变量，并且 Node 数组是在第一次 put 时才会进行初始化，初始化时会将此时的 threshold 值作为新表的 capacity 值，然后用 capacity 和 loadFactor 计算新表的真正 threshold 值。

• 当同一个索引位置的节点在增加后达到 9 个时，并且此时数组的长度大于等于 64，则会触发链表节点（Node）转红黑树节点（TreeNode），转成红黑树节点后，其实链表的结构还存在，通过 next 属性维持。链表节点转红黑树节点的具体方法为源码中的 treeifyBin 方法。而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容。

• 当同一个索引位置的节点在移除后达到 6 个时，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点。红黑树节点转链表节点的具体方法为源码中的 untreeify 方法。

• HashMap 在 JDK 1.8 之后不再有死循环的问题，JDK 1.8 之前存在死循环的根本原因是在扩容后同一索引位置的节点顺序会反掉。

• HashMap 是非线程安全的，在并发场景下使用 ConcurrentHashMap 来代替。