hashmap 常见面试题

为什么说 HashMap 是线程不安全的？

在接近临界点时，若此时两个或者多个线程进行 put 操作，都会进行 resize（扩容）和 reHash（为 key 重新计算所在位置），而 reHash 在并发的情况下可能会形成链表环。总结来说就是在多线程环境下，使用 HashMap 进行 put 操作会引起死循环，导致 CPU 利用率接近 100%，所以在并发情况下不能使用 HashMap。为什么在并发执行 put 操作会引起死循环？是因为多线程会导致 HashMap 的 Entry 链表形成环形数据结构，一旦形成环形数据结构，Entry 的 next 节点永远不为空，就会产生死循环获取 Entry。jdk1.7 的情况下，并发扩容时容易形成链表环，此情况在 1.8 时就好太多太多了。因为在 1.8 中当链表长度大于阈值（默认长度为 8）时，链表会被改成树形（红黑树）结构。

1.7 和 1.8 的不安全

1.7 是容易形成环

1.8 假设两个线程 A、B 都在进行 put 操作，并且 hash 函数计算出的插入下标是相同的，当线程 A 要执行插入的时候由于时间片耗尽导致被挂起，而线程 B 得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程 A 获得时间片，由于之前已经进行了 hash 碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程 B 插入的数据被线程 A 覆盖了，从而线程不安全。

何时转红黑树？

hash 冲突默认采用单链表存储，当单链表节点个数大于 8 时，会转化为红黑树存储。

但是有一个前提：要求数组长度大于 64，否则不会进行转化

1.7 为什么 cpu100%?

假设两个线程同时进行扩容，然后线程一再准备的扩容的时候被挂起，然后线程二进行了扩容，假设 rehash 的值，又进行了一个碰撞，所以线程二扩容之后，顺序已经改变了，相反，但是线程一这时候被唤醒了，然后他最初的指向没有变，e 指向 3，next 指向 2，这时候，进行扩容，会出现环状。就会导致 cpu%100 的情况。

为什么阈值为 8 加载因子为 0.75？

在理想情况下,使用随机哈希码，节点出现的频率在 hash 桶中遵循泊松分布。0.0000006 源码写的

对照桶中元素个数和概率的表，可以看到当用 0.75 作为加载因子时，桶中元素到达 8 个的时候，概率已经变得非常小，因此每个碰撞位置的链表长度超过 8 个是几乎不可能的，因此在链表节点到达 8 时才开始转化为红黑树。当然为了防止编程人员自己重新 hashcode，让 hash 冲突增加，还是设置了红黑树的设定。

因为负载因为会使用在扩容上，0.5 会使数组不停的扩容，扩容需要复制内容，牺牲了空间，换取了时间，而 1.0 会使红黑树一直处于修补树状态，会造成时间的浪费。而取舍是 两边各一半，0.75

为什么不直接使用红黑树？

因为红黑树的结点存储是普通结点的两倍，红黑树虽然查询效率比链表高，但是结点占用的空间大，只有达到一定的数目才有树化的意义，这是基于时间和空间的平衡考虑。

因为红黑树需要进行左旋，右旋操作， 而单链表不需要，

以下都是单链表与红黑树结构对比。

如果元素小于 8 个，查询成本高，新增成本低

如果元素大于 8 个，查询成本低，新增成本高

鱼和熊掌不能兼得

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

上面说到，当链表长度达到阈值 8 的时候会转为红黑树，但是红黑树退化为链表的阈值却是 6，为什么不是小于 8 就退化呢？比如说 7 的时候就退化，偏偏要小于或等于 6？

主要是一个过渡，避免链表和红黑树之间频繁的转换。如果阈值是 7 的话，删除一个元素红黑树就必须退化为链表，增加一个元素就必须树化，来回不断的转换结构无疑会降低性能，所以阈值才不设置的那么临界。

算出在数组的位置

1.首先计算 key 的 hash 值（不是单纯的调用 key 的 hashCode 方法）(h = key.hashCode()) ^ (h >>> 16)足够散列，高低位的异或

2.hash 值和（数组空间大小 - 1）做与运算，计算元素在数组中的索引。

为什么数组大小一定是 2 的 n 次幂？

因为如果不是 2 的 n 次幂，比如 14，1110，你会发现，你转二进制的时候，总会有的位数是 0，这时候去 &那个 hashcode 出来的值，这个位置上的值永远是 0，会导致散列到你的数组时候，永远有一个地方空着的。

大小是 2^n（2 的 n 次幂）

说是 2 的倍数并不严谨，就算你是个偶数，比如说 12，那么 12-1=11,11 的二进制是 1011，并不符合设计

为什么要数组长度 64？

当链表长度大于 8 并且数组长度大于 64 时，才会转换为红黑树。

如果链表长度大于 8，但是数组长度小于 64 时，还是会进行扩容操作，不会转换为红黑树。因为数组的长度较小，应该尽量避开红黑树。因为红黑树需要进行左旋，右旋，变色操作来保持平衡，

所以当数组长度小于 64，使用数组加链表比使用红黑树查询速度要更快、效率要更高

hashmap1.7 和 hashmap1.8put 区别？

1.7：

计算 h = key.hashCode()) ^ (h >>> 16)然后对数组长度取模运算。把 put 进来的 key 和 value 封装成一个 entry 对象，计算出在数组长度的位置，然后判断该位置是否有数据，没数据直接存储，有数据，先判断链表中是否有相同的数据，没有直接把数据插入该链表中。有相同的直接覆盖。使用的是头插法

1.8：

计算 h = key.hashCode()) ^ (h >>> 16)然后对数组长度取模运算，算出数组的位置。先判断是否为空。

为空，直接将封装的 entry 赋值给该数组的位置

不为空，先判断是否等于该位置的元素，

等于当前直接覆盖，

不等于，说明 hash 碰撞，再进行判断是否为 treenode 类型

是代表直接是一个红黑树，直接进行插入，判断是否重复

不是就说明是链表，然后进行一个遍历，同时会进行一个计数，查询是否有结点跟我 put 的结点相同，相同继续覆盖，如果没有，插入到尾部，判断我插入的这个结点之后链表长度是否大于了 8，大于了 8 转为红黑树

这里面所有的重复的，都调用 onlyIfAbsent 标记来判断是否需要更新 value 值

就直接简化为四种情况

1.slot 等于 null 直接占用

2.slot 不等于 null 而且没有链化

判断 key 是否相等，然后相等进行覆盖，不相等为尾节点插入

3.slot 已经链化了

依次遍历链表有重复 的进行覆盖，没有就插入到尾节点，在判断插入的时候是否大于 8，数组大于 64，进行一个转红黑树，树化

4.slot 是红黑树

遍历红黑树，然后也判断 key 是否重复，重复覆盖，不重复，进行一个插入。基于红黑树的插入。就不涉及了

hashmap1.7 和 hashmap1.8get

先判断数组是否为空。为空直接返回

计算 h = key.hashCode()) ^ (h >>> 16)然后对数组长度取模运算，算出数组的位置，先判断第一个位置的元素是否等于我传过来的 key

是，就直接返回该元素的 value

不是，再进行判断是否有下一个元素

没有，直接返回空

有，判断该结点的类型是 treenode 还是链表结点

然后对应分别进行遍历，判断是否存在 key，不存在返回 null

hashmap1.7 和 hashmap1.8 扩容

数组的扩容，新建一个 2 倍大小的数组，然后遍历老数组的元素，如果是链表，直接把这个链表转移到新数组上去

这个过程就是设计到 1.7 和 1.8 的实现

1.7 只是简单的遍历原数组的每一个元素，然后重新 hash 计算，然后存放到新的数组里面去。这样链表会缩短，提高查询效率

1.8，因为涉及到红黑树。所以他底层用了一个双向链表(高低位链表)来维护这个红黑树(减少扩容的迁移量)，如果该结点是一个红黑树，然后遍历整个红黑树，计算出哪些结点在原数组的位置，哪些结点在新数组的位置。这样就会生成两个子链表，然后再判断原数组和新数组的位置是否存在元素。

不存在，就直接存储。

存在，判断两个子链表的长度是否超过 8

超过，转成红黑树放到对应的位置

不超过，把单链表放到对应的位置

1.8 的扩容

分 4 种情况

1.null 不变

2.存储的是一个单个 node

直接计算 hash 进行迁移

3.存储的是一个链表

高位链和低位链

因为是链表。所以这个链表所计算出来的低位链都是相同的，就是这个链表的所有数据 &老表的长度-1 都是相同的，这时候的低位链都是相同的(假设老数组为 16，1111)。但这时候的高位(第五位)可能不同有得为 1 有得为 0，因为扩容计算肯定会多一位嘛，所以迁移到新表得位置也不一样，假设为 0，就说明在原来的位置没有变，但是是 1 的话，就是当前的位置加老数组的位置，这就是在新数组的位置例如原来是 8 数组 16 现在的位置就是 24

4.存储的是红黑树

其实差不多。主要是看一下长度，高低位的链表的长度，如果是小于 6 的话，转为链表来进行一个存放。如果是 8 的话还是会进行一个重新构建红黑树。

为什么 Java8 中 HashMap 链表使用红黑树而不是 AVL 树？

在 CurrentHashMap 中是加锁了的，实际上是读写锁，如果写冲突就会等待，如果插入时间过长必然等待时间更长，而红黑树相对 AVL 树他的插入更快！

因为 AVL 的查询很快，但是增删比红黑树慢，整体性能红黑树好一点

红黑树整体的查询和增加删除更加稳定，虽然 AVL 查询更快，但是它的增删比红黑树慢

HashMap 是先插入还是先扩容？

HashMap 初始化后首次插入数据时，先发生 resize 扩容再插入数据，之后每当插入的数据个数达到 threshold 时就会发生 resize，此时是先插入数据再 resize。

为什么要右移 16 位？

其实是为了减少碰撞，进一步降低 hash 冲突的几率。int 类型的数值是 4 个字节(32 位)的，右移 16 位异或可以同时保留高 16 位于低 16 位的特征

为什么要异或运算？

首先将高 16 位无符号右移 16 位与低十六位做异或运算。如果不这样做，而是直接做 &运算那么高十六位所代表的部分特征就可能被丢失 将高十六位无符号右移之后与低十六位做异或运算使得高十六位的特征与低十六位的特征进行了混合得到的新的数值中就高位与低位的信息都被保留了 ，而在这里采用异或运算而不采用 & ，| 运算的原因是 异或运算能更好的保留各部分的特征，如果采用 &运算计算出来的值会向 1 靠拢，采用|运算计算出来的值会向 0 靠拢

HashMap 以 null 作为 key 时，总是存储在 table 数组的第一个节点上，它是根据 key 的 hashCode 来寻找存放位置的，在 put 方法里头，其实第一行就处理了 key=null 的情况。当 HashMap 的 put 方法，第二个判断就是 key 为 null 的判断后进入 putForNullKey(V value)这个方法 putForNullKey 个 for 循环，是在 talbe[0]链表中查找 key 为 null 的元素，如果找到，则将 value 重新赋值给这个元素的 value，并返回原来的 value。如果上面 for 循环没找到则将这个元素添加到 talbe[0]链表的表头。通过构造初始化的参数，会动态的生成该参数的最小二倍数

hashmap 通过构造设置得初始值会动态得扩容到 2 得 n 次幂

例如想要用 HashMap 存放 1k 条数据，应该设置 1000 / 0.75，实际传递进去的值是 1333，然后会被 tableSizeFor() 方法调整到 2048，足够存储数据而不会触发扩容。

当想用 HashMap 存放 1w 条数据时，依然设置 10000 / 0.75，实际传递进去的值是 13333，会被调整到 16384，和我们直接传递 10000 效果是一样的。

这儿用的 tableSizeFor 的算法（核心思想是生成大于数字的最小 2 倍数）

static final int tableSizeFor(int cap) {

int n = cap - 1;

n |= n >>> 1; //或右移 1 位的算法使 最高位的"非零 0 第 1 位"变 1

n |= n >>> 2; // 或右移 2 位的算法使 最高位的"非零 0 第 1,2 位"变 1

n |= n >>> 4;// 或右移 2 位的算法使 最高位的"非零 0 第 1~4 位"变 1

n |= n >>> 8;// 或右移 2 位的算法使 最高位的"非零 0 第 1~8 位"变 1

n |= n >>> 16;//或右移 2 位的算法使 最高位的"非零 0 第 1~16 位"变 1

//算法结束后，得到 cap 的非 0 位的 1+2+4+8+16 = 31 位变 1 基本上覆盖了最大值 Integer.MaxValue;

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

}

使用位运算：位运算确实比取模运算快得多，大约快了 27 倍。