Java 中 HashMap 的那些事

答案参考自：

• 看完还不懂HashMap算我输（附职场面试常见问题）_黛色翩翩的博客-CSDN博客
• hashmap为什么用红黑树_HashMap面试必问的6个点，你知道几个？_weixin_39603469的博客-CSDN博客

JDK 1.8 中 HashMap 更改了什么内容？

1. 将存储方式更改为了 数组 + 链表/红黑树。
2. 优化了高位运算的hash算法：h & (h >>> 16)。
3. 扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变。

HashMap 原理

几个重要的变量

• DEFAULT_INITIAL_CAPACITY

  Table数组的初始化长度： 1 << 4 。

• MAXIMUM_CAPACITY

  Table数组的最大长度： 1 << 30。

• DEFAULT_LOAD_FACTOR

  负载因子：默认值为0.75。

  当元素的总个数 > (当前数组的长度 * 负载因子)，数组会进行扩容，扩容为原来的两倍。

• TREEIFY_THRESHOLD

  链表树化阈值： 默认值为 8 。

  表示在一个node（Table）节点下的值的个数大于8时候，会将链表转换成为红黑树。

• UNTREEIFY_THRESHOLD

  红黑树链化阈值： 默认值为 6 。

  表示在进行扩容期间，单个Node节点下的红黑树节点的个数小于6时候，会将红黑树转化成为链表。

• MIN_TREEIFY_CAPACITY = 64

  最小树化阈值，值为 64。

  当Table所有元素超过改值，才会进行树化（为了防止前期阶段频繁扩容和树化过程冲突）。

实现原理

HashMap采⽤Entry数组来存储key-value对，每⼀个键值对组成了⼀个Entry实体，Entry类实际上是⼀个单向的链表结构，它具有Next指针，可以连接下⼀个Entry实体。 只是在JDK1.8中，链表⻓度⼤于8的时候，链表会转成红黑树。

为什么使用 链表 + 数组 的存储方式？

由于我们的数组的值是限制死的，我们在对key值进行散列取到下标以后，放入到数组中时，难免出现两个key值不同，但是却放入到下标相同的格子中，此时我们就可以使用链表来对其进行链式的存放。

用LinkedList代替数组结构可以吗？

可以的。

既然可以使用进行替换处理，为什么偏偏使用到数组呢？

因为使用数组效率最高。

在HashMap中，定位节点的位置是通过 i = (n - 1) & hash 得到。此时，我们已得到节点的位置。显然数组的查找效率比LinkedList更优（底层是链表结构）。

那ArrayList，底层也是数组，查找也快啊，为啥不⽤ArrayList?

因为采用基本数组结构，扩容机制可以自己定义，HashMap中数组扩容刚好是2的次幂，方便原数组中的元素的位置变动， 而ArrayList的扩容机制是1.5倍扩容。

HashMap中如何计算出存放位置的？hash函数怎么实现的?

该问题解析同下问。

为什么不直接将hashcode作为哈希值去做取模,而是要先高16位异或低16位

// HashMap#putVal 计算位置并存放
if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

通过图做进一步的了解 i = (n - 1) & hash：

这里我们也就得知为什么Table数组的长度要一直都为 $2^n$，只有这样，减一进行与操作时候，才能够达到最大的n-1值。

通过反例验证一下：

我们现 数组的长度为 15 ，减一为 14 ，二进制表示 0000 1110 。进行与操作时候，最后一位永远是0，这样就可能导致不能够完完全全的进行Table数组的使用。违背了我们最开始的想要对Table数组进行最大限度的无序使用的原则，因为HashMap为了能够存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表⻓度⼤致相同。

此时还有一点需要注意的是： 我们对key值进行hashcode以后，进行相与时候都是只用到了后四位，前面的很多位都没有能够得到使用,这样也可能会导致我们所生成的下标值不能够完全散列。

解决方案：

将生成的hashcode值的高16位于低16位进行异或运算，这样得到的值再进行与操作，得散列的下标值，异或的1或0的结果都是1/2，使得散列更均匀。

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

还有哪些hash函数的实现方式？

先说⼀下hash算法⼲嘛的，hash函数是指把⼀个⼤范围映射到⼀个⼩范围。把⼤范围映射到⼀个⼩范围的⽬的往往是为了 节省空间，使得数据容易保存。

⽐较出名的有MurmurHash、MD4、MD5等等。

String中hashcode的实现

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

hash冲突有哪些解决办法

答案参考自：

• 解决哈希冲突（四种方法）_君诀的博客-CSDN博客_解决哈希冲突的方法

有三个方法：

1. 开放定址法
2. 再哈希法
3. 链地址法

解决hash冲突的时候，为什么用红黑树？

当链表过长的时候，如果仍旧使用链表进行搜索和删改，时间复杂度为$O(n)$，所消耗的时间叫较大。

如果采用了红黑树的设计，则可以使得在数据量较大的情况下，以$O(logn)$的时间复杂度进行搜索和删改，大幅减少使用的时间。

红黑树的效率高，为什么一开始不用红黑树存储？

答案参考自：

• JDK1.8以后的hashmap为什么在链表长度为8的时候变为红黑树_向日葵班学霸的博客-CSDN博客

因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。

源码中的注释写的很清楚，因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树。

不用红黑树，用二叉查找树可以不？

可以。但是二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。

为什么阈值是8才转为红黑树

答案参考自：

• JDK1.8以后的hashmap为什么在链表长度为8的时候变为红黑树_向日葵班学霸的博客-CSDN博客

源码上说，为了配合使用分布良好的hashCode，树节点很少使用。并且在理想状态下，受随机分布的hashCode影响，链表中的节点遵循泊松分布，而且根据统计，链表中节点数是8的概率已经接近千分之一，而且此时链表的性能已经很差了。

所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。因为链表转换为红黑树也是需要消耗性能的，特殊情况特殊处理，为了挽回性能，权衡之下，才使用红黑树，提高性能。

也就是大部分情况下，hashmap还是使用的链表，如果是理想的均匀分布，节点数不到8，hashmap就自动扩容了。为什么这么说呢？

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
	else {
        // ...
    }
    
   	return ;
}

在链表转变为红黑树方法中，有这样一个判断，数组长度小于MIN_TREEIFY_CAPACITY = 64，就会扩容，而不是直接转变为红黑树，可不是什么链表长度为8就变为红黑树，要仔细看代码，还有别的条件。

现在回头想想，为啥用8？

因为通常情况下，链表长度很难达到8，但是特殊情况下链表长度为8，哈希表容量又很大，造成链表性能很差的时候，只能采用红黑树提高性能，这是一种应对策略。

为什么退化为链表的阈值是6

答案参考自：

• HashMap系列：树化阀值8，退化阀值6 - 简书 (jianshu.com)

如果不设退化阀值，只以8来树化与退化：
那么8将成为一个临界值，时而树化，时而退化，此时会非常影响性能，因此，我们需要一个比8小的退化阀值；

UNTREEIFY_THRESHOLD = 7
同样，与上面的情况没有好多少，仅相差1个元素，仍旧会在链表与树之间反复转化；

那为什么是6呢？
源码中也说了，考虑到内存（树节点比普通节点内存大2倍，以及避免反复转化），所以，退化阀值最多为6。

HashMap中put如何实现的

put 方法中会实现以下的过程：

1. 如果 table 没有初始化，就先进行初始化（resize）操作。
2. 对 key 进行 hash，并计算出存放位置 index (i = (n - 1) & hash)。
3. 如果没碰撞直接放到bucket中。
4. 如果发生碰撞了，就遍历链表：
   1. 如果出现了key相同，value不同的节点，就替换该value(保证key的唯⼀性)。
   2. 否则直接加入到链表的结尾（尾插法）。
5. 如果链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树(JDK1.8中的改动)。
6. 如果bucket满了(超过DEFAULT_LOAD_FACTOR * CAPACITY)，就要resize。

HashMap中get如何实现的

get 方法中会实现以下的过程：

1. 判断table是否为null，若为null，则直接返回null。
2. 计算key的hash，并计算存放位置。
3. 直接判断第一个元素是否为自己所需要的元素。如果是，则直接返回该节点。
4. 如果有冲突，则通过key.equals(k)去查找对应的Entry。
   1. 若为树，则在树中通过key.equals(k)查找，时间复杂度为 $O(logn)$。
   2. 若为链表，则在链表中通过key.equals(k)查找，时间复杂度为 $O(n)$。

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 判断 表是否为空，表重读是否大于零，并且根据此 key 对应的表内是否存在 Node节点。    
    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))))
            // 检查第一个Node 节点，若是命中则不需要进行do... whirle 循环。
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                //树形结构，采用 对应的检索方法，进行检索。
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                //链表方法 做while循环，直到命中结束或者遍历结束。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

链表的查找的时间复杂度是多少

时间复杂度为 $O(n)$。

HashMap在什么条件下扩容

答案参考自：

• 深入理解HashMap的扩容机制 - 颜子歌 - 博客园 (cnblogs.com)

Java8不再像Java7中那样需要满足两个条件，Java8中扩容只需要满足一个条件：

当前存放新值（注意不是替换已有元素位置时）的时候已有元素的个数大于等于阈值（已有元素等于阈值，下一个存放后必然触发扩容机制）

注：

1. 扩容一定是放入新值的时候，该新值不是替换以前位置的情况下（说明：put("name","zhangsan")，而map里面原有数据<"name","lisi">，则该存放过程就是替换一个原有值，而不是新增值，则不会扩容）。
2. 扩容发生在存放后，即是数据存放后（先存放后扩容），判断当前存入对象的个数，如果大于阈值则进行扩容。

为什么扩容是2的次幂

答案参考自：

• HashMap初始容量为什么是2的n次幂及扩容为什么是2倍的形式？_喜欢敲代码的Apollo的博客-CSDN博客

1. 得到的新的数组索引和老数组索引只有最高位区别，更快地得到新索引。

2. rehash 时的取余操作，hash % length == hash & (length - 1) 这个关系只有在 length 等于二的幂次方时成立，位运算能比%高效得多。

HashMap#resize 源码

// HashMap#resize

void resize(int newCapacity) {
    HashMapEntry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    HashMapEntry[] newTable = new HashMapEntry[newCapacity]; // 新建一个数组
    transfer(newTable); // 完成新旧数组拷贝
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}


void transfer(HashMapEntry[] newTable) {
    int newCapacity = newTable.length;
    for (HashMapEntry<K,V> e : table) { // 遍历整个数组
        while(null != e) { // 将同一个位置的元素按链表顺序取出
            HashMapEntry<K,V> next = e.next; // 先将当前元素指向的下一个元素存起来，一个一个存放到新表的位置中，记住不一定是同一位置，因为长度变了
            int i = indexFor(e.hash, newCapacity); // 根据新数组长度，重新生成数组索引
            e.next = newTable[i]; // 将当前位置的元素链表头指向即将新加入的元素，
            newTable[i] = e; // 然后放入数组中，完成同一位置元素链表的拼接，最先添加的元素总在链表末尾
            e = next; // 然后继续循环，拿出下一个元素
        }
    }
}

为什么HashMap线程不安全

HashMap 没有通过锁的方式使得同一时间只有一个线程可以访问，如果多个线程同一时间对同一个元素进行修改，便会出现结果错误的情况。

处理HashMap线程不安全

1. 在之前使用HashTable。 在每一个函数前面都加上了 synchronized 但是效率太低我们现在不常用了。
2. 使用 ConcurrentHashmap。用于提高效率。

---

ConcurrentHashMap

答案参考自：

• ConcurrentHashMap（JDK8） - 云+社区 - 腾讯云 (tencent.com)

对比

与 HashMap 的区别是什么？

ConcurrentHashMap 是 HashMap 的升级版，HashMap 是线程不安全的，而 ConcurrentHashMap 是线程安全。而其他功能和实现原理和 HashMap 类似。

与 Hashtable 的区别是什么？

Hashtable 也是线程安全的，但每次要锁住整个结构，并发性低。相比之下，ConcurrentHashMap 获取 size 时才锁整个对象。

Hashtable 对 get/put/remove 都使用了同步操作。ConcurrentHashMap 只对 put/remove 同步。

Hashtable 是快速失败的，遍历时改变结构会报错 ConcurrentModificationException。ConcurrentHashMap 是安全失败，允许并发检索和更新。

JDK8 的 ConcurrentHashMap 和 JDK7 的 ConcurrentHashMap 有什么区别？

1. JDK8 中新增了红黑树
2. JDK7 中使用的是头插法，JDK8 中使用的是尾插法
3. JDK7 中使用了分段锁，而 JDK8 中没有使用分段锁了
4. JDK7 中使用了ReentrantLock，JDK8 中没有使用 ReentrantLock 了，而使用了 Synchronized
5. JDK7 中的扩容是每个 Segment 内部进行扩容，不会影响其他 Segment，而 JDK8 中的扩容和 HashMap 的扩容类似，只不过支持了多线程扩容，并且保证了线程安全

特性

ConcurrentHashMap 是如何保证并发安全的？

JDK7 中 ConcurrentHashMap 是通过 ReentrantLock+CAS+分段思想 来保证的并发安全的，ConcurrentHashMap 的 put 方法会通过 CAS 的方式，把一个 Segment 对象存到 Segment 数组中，一个 Segment 内部存在一个 HashEntry 数组，相当于分段的 HashMap，Segment 继承了 ReentrantLock，每段 put 开始会加锁。

在 JDK7 的 ConcurrentHashMap 中，首先有一个 Segment 数组，存的是 Segment 对象，Segment 相当于一个小 HashMap，Segment 内部有一个 HashEntry 的数组，也有扩容的阈值，同时 Segment 继承了 ReentrantLock 类，同时在 Segment 中还提供了 put、get 等方法，比如 Segment 的 put 方法在一开始就会去加锁，加到锁之后才会把 key、value 存到 Segment 中去，然后释放锁。同时在ConcurrentHashMap 的 put 方法中，会通过 CAS 的方式把一个 Segment 对象存到 Segment 数组的某个位置中。同时因为一个 Segment 内部存在一个 HashEntry 数组，所以和 HashMap 对比来看，相当于分段了，每段里面是一个小的 HashMap，每段公用一把锁，同时在ConcurrentHashMap 的构造方法中是可以设置分段的数量的，叫做并发级别 concurrencyLevel。

JDK8 中 ConcurrentHashMap 是通过 synchronized+CAS 来实现了。在 JDK8 中只有一个数组，就是 Node 数组，Node 就是 key、value、hashcode 封装出来的对象，和 HashMap 中的 Entry 一样，在 JDK8 中通过对 Node 数组的某个 index 位置的元素进行同步，达到该 index 位置的并发安全。同时内部也利用了 CAS 对数组的某个位置进行并发安全的赋值。

JDK8 中的 ConcurrentHashMap 为什么使用 synchronized 来进行加锁？

JDK8 中使用 synchronized 加锁时，是对链表头结点和红黑树根结点来加锁的，而 ConcurrentHashMap 会保证，数组中某个位置的元素一定是链表的头结点或红黑树的根结点，所以 JDK8 中的 ConcurrentHashMap 在对某个桶进行并发安全控制时，只需要使用 synchronized 对当前那个位置的数组上的元素进行加锁即可，对于每个桶，只有获取到了第一个元素上的锁，才能操作这个桶，不管这个桶是一个链表还是红黑树。

相比于 JDK7 中使用 ReentrantLock 来加锁，因为 JDK7 中使用了分段锁，所以对于一个 ConcurrentHashMap 对象而言，分了几段就得有几个 ReentrantLock 对象，表示得有对应的几把锁。

而 JDK8 中使用 synchronized 关键字来加锁就会更节省内存，并且 JDK 也已经对 synchronized 的底层工作机制进行了优化，效率更好。

JDK7 中的 ConcurrentHashMap 是如何扩容的？

JDK7 中的 ConcurrentHashMap 和 JDK7 的 HashMap 的扩容是不太一样的。首先 JDK7 中也是支持多线程扩容的，原因是 JDK7 中的 ConcurrentHashMap 分段了，每一段叫做 Segment 对象，每个 Segment 对象相当于一个 HashMap，分段之后，对于 ConcurrentHashMap 而言，能同时支持多个线程进行操作，前提是这些操作的是不同的 Segment，而 ConcurrentHashMap 中的扩容是仅限于本 Segment，也就是对应的小型 HashMap 进行扩容，所以是可以多线程扩容的。

每个 Segment 内部的扩容逻辑和 HashMap 中一样。

JDK8 中的 ConcurrentHashMap 是如何扩容的？

首先，JDK8 中是支持多线程扩容的，JDK8 中的 ConcurrentHashMap 不再是分段，或者可以理解为每个桶为一段，在需要扩容时，首先会生成一个双倍大小的数组，生成完数组后，线程就会开始转移元素，在扩容的过程中，如果有其他线程在 put，那么这个 put 线程会帮助去进行元素的转移，虽然叫转移，但是其实是基于原数组上的 Node 信息去生成一个新的 Node 的，也就是原数组上的 Node 不会消失，因为在扩容的过程中，如果有其他线程在 get 也是可以的。

JDK8 中的 ConcurrentHashMap 有一个 CounterCell，你是如何理解的？

CounterCell 是 JDK8 中用来统计 ConcurrentHashMap 中所有元素个数的，在统计 ConcurentHashMap 时，不能直接对 ConcurrentHashMap 对象进行加锁然后再去统计，因为这样会影响 ConcurrentHashMap 的 put 等操作的效率，在 JDK8 的实现中使用了 CounterCell+baseCount 来辅助进行统计，baseCount 是 ConcurrentHashMap 中的一个属性，某个线程在调用 ConcurrentHashMap 对象的 put 操作时，会先通过 CAS 去修改 baseCount 的值，如果 CAS 修改成功，就计数成功，如果 CAS 修改失败，则会从 CounterCell 数组中随机选出一个 CounterCell 对象，然后利用 CAS 去修改 CounterCell 对象中的值，因为存在 CounterCell 数组，所以，当某个线程想要计数时，先尝试通过 CAS 去修改 baseCount 的值，如果没有修改成功，则从 CounterCell 数组中随机取出来一个 CounterCell 对象进行 CAS 计数，这样在计数时提高了效率。

所以 ConcurrentHashMap 在统计元素个数时，就是 baseCount 加上所有 CountCeller 中的 value 值，所得的和就是所有的元素个数。

key 可以是 null 吗，value 可以是 null 吗

当然都是可以的，但是对于 key来说只能运行出现一个key值为null，但是可以出现多个value值为null。

一般用什么值作为key值？

一般用 Integer、String 这种不可变类当 HashMap 当 key，⽽且 String 最为常用。

1. 因为字符串是不可变的，所以在它创建的时候 hashcode 就被缓存了，不需要重新计算。 这就使得字符串很适合作为 Map 中的键，字符串的处理速度要快过其它的键对象。 这就是 HashMap 中的键往往都使用字符串。
2. 因为获取对象的时候要用到 equals() 和 hashCode() 方法，那么键对象正确的重写这两个方法是⾮常重要的，这些类已经很规范的覆写了 hashCode() 以及 equals() 方法。

用可变类当 Hashmap 的 key 会有什么问题

hashcode 可能会发生变化，导致 put 进行的值，无法 get 出来。