分享一些 Java HashMap 高级面试题！

今年以来，我面试过很多候选人。其中也有不少人背过面试题，但是经过我的这套面试题套餐，基本上没啥人能通过。

在 Java 面试中，HashMap 基本必问，只是问法各有不同而已。HashMap 有非常多的知识点，学好它对整个编程思想有非常大的帮助。不幸的是，很大部分人都拜倒在 HashMap 的石榴裙底下!

HashMap为什么如此受面试官青睐？

我觉得其中有4个原因：

• HashMap 在我们工作中使用频率相当高
• HashMap 的知识点比较多
• HashMap 线程安全问题
• 大厂都在问，岂能不问？

下面就是我给大家准备的 HashMap 连环炮，这个连环炮就相当于高考真题演练一样，可能没有完全一样的，只是问法不同罢了，这个主要得益于咱们汉语博大精深。

下面是HashMap的25连环炮：

1. 说说 HashMap 底层数据结构是怎样的？
2. 谈一下 HashMap的特性？
3. 使用 HashMap 时，当两个对象的 hashCode 相同怎么办？
4. HashMap 的哈希函数怎么设计的吗？
5. HashMap 遍历方法有几种？
6. 为什么采用 hashcode 的高 16 位和低 16 位异或能降低 hash 碰撞？hash 函数能不能直接用 key 的 hashcode？
7. 解决 hash 冲突的有几种方法？
8. 为什么要用异或运算符？
9. HashMap 的 table 的容量如何确定？
10. 请解释一下 HashMap 的参数 loadFactor，它的作用是什么
11. 说说 HashMap 中 put 方法的过程
12. 当链表长度 >= 8 时，为什么要将链表转换成红黑树？
13. new HashMap(18);此时 HashMap 初始容量为多少？
14. 说说 resize 扩容的过程
15. 说说 hashMap 中 get 是如何实现的？
16. 拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？
17. 说说你对红黑树的了解
18. JDK8 中对 HashMap 做了哪些改变？
19. HashMap 中的 key 我们可以使用任何类作为 key 吗？
20. HashMap 的长度为什么是 2 的 N 次方呢？
21. HashMap，LinkedHashMap，TreeMap 有什么区别？
22. 说说什么是 fail-fast？
23. HashMap 和 HashTable 有什么区别？
24. HashMap 是线程安全的吗？
25. 如何规避 HashMap 的线程不安全？
26. HashMap 和 ConcurrentHashMap 的区别？
27. 为什么 ConcurrentHashMap 比 HashTable 效率要高？
28. 说说 ConcurrentHashMap 中的锁机制
29. 在 JDK 1.8 中，ConcurrentHashMap 为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？
30. 能对 ConcurrentHashMap 做个简单介绍吗？
31. 熟悉 ConcurrentHashMap 的并发度吗？

java集合知识总结

下面我们正式开始连环炮

1、说说 HashMap 底层数据结构是怎样的？

HashMap 底层是 hash 数组和单向链表实现，jdk8 后采用数组+链表+红黑树的数据结构。

2、说说 HashMap 的工作原理

如果第一题没问，直接问原理，那就必须把 HashMap 的数据结构说清楚。

HashMap 底层是 hash 数组和单向链表实现，JDK8 后采用数组+链表+红黑树的数据结构。

我们通过 put 和 get 存储和获取对象。当我们给 put()方法传递键和值时，先对键做一个 hashCode() 的计算来得到它在 bucket 数组中的位置来存储 Entry 对象。当获取对象时，通过 get 获取到 bucket 的位置，再通过键对象的 equals() 方法找到正确的键值对，然后在返回值对象。

3、HashMap 中，hashCode 相同怎么办？

因为 HashCode 相同，不一定就是相等的（equals 方法比较），所以两个对象所在数组的下标相同，”碰撞”就此发生。又因为 HashMap 使用链表存储对象，这个 Node 会存储到链表中。

4、HashMap 的哈希函数怎么设计的吗？

hash 函数是先拿到通过 key 的 hashCode ，是 32 位的 int 值，然后让 hashCode 的高 16 位和低 16 位进行异或操作。两个好处：

1. 一定要尽可能降低 hash 碰撞，越分散越好；
2. 算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；

5、HashMap遍历方法有几种？

• Iterator 迭代器
• 最常见的使用方式，可同时得到 key、value 值
• 使用 foreach 方式（JDK1.8 才有）
• 通过 key 的 set 集合遍历

6、为什么采用 hashcode 的高 16 位和低 16 位异或能降低 hash 碰撞？

因为 key.hashCode() 函数调用的是 key 键值类型自带的哈希函数，返回 int 型散列值。int 值范围为-2147483648 ~ 2147483647。

设想，HashMap 数组的初始大小为 16，假设我现在有一个 key 的 hash 值为2147483647，不进行位运算的话，存储的下标就会超过当前数组的长度。

对数组的长度取模运算，得到的余数才能用来访问数组下标。

7、解决 hash 冲突的有几种方法？

1、「再哈希法」：如果 hash 出的 index 已经有值，就再 hash，不行继续hash，直至找到空的 index 位置，要相信瞎猫总能碰上死耗子。这个办法最容易想到。但有2个缺点：

• 比较浪费空间，消耗效率。根本原因还是数组的长度是固定不变的，不断 hash 找出空的 index，可能越界，这时就要创建新数组，而老数组的数据也需要迁移。随着数组越来越大，消耗不可小觑。
• get 不到，或者说 get 算法复杂。进是进去了，想出来就没那么容易了。

2、「开放地址方法」：如果 hash 出的 index 已经有值，通过算法在它前面或后面的若干位置寻找空位，这个和再 hash 算法差别不大。

3、「建立公共溢出区：」 把冲突的 hash 值放到另外一块溢出区。

4、「链式地址法：」 把产生 hash 冲突的 hash 值以链表形式存储在 index 位置上。HashMap 用的就是该方法。优点是不需要另外开辟新空间，也不会丢失数据，寻址也比较简单。但是随着 hash 链越来越长，寻址也是更加耗时。好的 hash 算法就是要让链尽量短，最好一个 index 上只有一个值。也就是尽可能地保证散列地址分布均匀，同时要计算简单。

8、为什么要用异或运算符？

保证了对象的 hashCode 的 32 位值只要有一位发生改变，整个 hash() 返回值就会改变。尽可能的减少碰撞。

9、HashMap 的 table 的容量如何确定？

①、table 数组大小是由 capacity 这个参数确定的，默认是 16，也可以构造时传入，最大限制是 1 << 30；

②、loadFactor 是装载因子，主要目的是用来确认 table 数组是否需要动态扩展，默认值是 0.75，比如 table 数组大小为 16，装载因子为 0.75 时，threshold 就是 12，当 table 的实际大小超过 12 时，table 就需要动态扩容；

③、扩容时，调用 resize() 方法，将 table 长度变为原来的两倍（注意是 table 长度，而不是 threshold）；

④、如果数据很大的情况下，扩展时将会带来性能的损失，在性能要求很高的地方，这种损失很可能很致命。

10、请解释一下 HashMap 的参数 loadFactor，它的作用是什么

loadFactor 表示 HashMap 的拥挤程度，影响 hash 操作到同一个数组位置的概率。

默认 loadFactor 等于0.75，当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时，表示 HashMap 太挤了，需要扩容，在 HashMap 的构造器中可以定制 loadFactor。

11、说说 HashMap 中 put 方法的过程

由于 JDK 版本中 HashMap 设计上存在差异，这里说说 JDK7 和 JDK8 中的区别：

具体 put 流程，请参照下图进行回答：

12、当链表长度 >= 8 且数组长度 >= 64 时，为什么要将链表转换成红黑树？

因为红黑树的平均查找长度是 log(n)，长度为 8 的时候，平均查找长度为 3，如果继续使用链表，平均查找长度为 8/2=4，所以，当链表长度 >= 8 且数组长度 >= 64 时，有必要将链表转换成红黑树。

13、new HashMap(18) 此时 HashMap 初始容量为多少？

容量为 32。

在 HashMap 中有个静态方法 tableSizeFor ，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 = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

14、说说 resize 扩容的过程

创建一个新的数组，其容量为旧数组的两倍，并重新计算旧数组中结点的存储位置。结点在新数组中的位置只有两种，原下标位置或原下标+旧数组的大小。

15、说说 hashMap 中 get 是如何实现的？

对 key 的 hashCode 进行 hash 值计算，与运算计算下标获取 bucket 位置，如果在桶的首位上就可以找到就直接返回，否则在树中找或者链表中遍历找，如果有hash 冲突，则利用 equals 方法去遍历链表查找节点。

16、拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于 8 的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

17、说说你对红黑树的了解

红黑树是一种自平衡的二叉查找树，是一种高效的查找树。

红黑树通过如下的性质定义实现自平衡：

• 节点是红色或黑色。
• 根是黑色。
• 所有叶子都是黑色（叶子是 NIL 节点）。
• 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
• 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。

18、JDK8 中对 HashMap 做了哪些改变？

1.在 java 1.8 中，如果链表的长度超过了 8，那么链表将转换为红黑树。（桶的数量必须大于 64，小于 64 的时候只会扩容）

2.发生 hash 碰撞时，java 1.7 会在链表的头部插入，而 java 1.8 会在链表的尾部插入

3.在 java 1.8 中，Entry 被 Node 替代(换了一个马甲)。

19、HashMap 中的 key 我们可以使用任何类作为 key 吗？

平时可能大家使用的最多的就是使用 String 作为 HashMap 的 key，但是现在我们想使用某个自定 义类作为 HashMap 的 key，那就需要注意以下几点：

• 如果类重写了 equals 方法，它也应该重写 hashCode 方法。
• 类的所有实例需要遵循与 equals 和 hashCode 相关的规则。
• 如果一个类没有使用 equals，你不应该在 hashCode 中使用它。
• 咱们自定义 key 类的最佳实践是使之为不可变的，这样，hashCode 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode 和 equals 在未来不会改变，这样就会解决与可变相关的问题了。

20、HashMap 的长度为什么是 2 的 N 次方呢？

为了能让 HashMap 存数据和取数据的效率高，尽可能地减少 hash 值的碰撞，也就是说尽量把数 据能均匀的分配，每个链表或者红黑树长度尽量相等。我们首先可能会想到 % 取模的操作来实现。下面是回答的重点哟：

取余（%）操作中如果除数是 2 的幂次，则等价于与其除数减一的与（&）操作（也就是说 hash % length == hash &(length – 1) 的前提是 length 是 2 的 n 次方）。并且，采用二进 制位操作 & ，相对于 % 能够提高运算效率。

这就是为什么 HashMap 的长度需要 2 的 N 次方了。

21、HashMap，LinkedHashMap 有什么区别？

• LinkedHashMap 是继承于 HashMap，是基于 HashMap 和双向链表来实现的。
• HashMap 无序；LinkedHashMap 有序，可分为插入顺序和访问顺序两种。如果是访问顺序，那 put 和 get 操作已存在的 Entry 时，都会把 Entry 移动到双向链表的表尾(其实是先删除再插入)。
• LinkedHashMap 存取数据，还是跟 HashMap 一样使用的 Entry[] 的方式，双向链表只是为了保证顺序。
• LinkedHashMap 是线程不安全的。

22、说说什么是 fail-fast？

fail-fast 机制是 Java 集合（Collection）中的一种错误机制。当多个线程对同一个集合的内容进行 操作时，就可能会产生 fail-fast 事件。

例如：当某一个线程 A 通过 iterator 去遍历某集合的过程中，若该集合的内容被其他线程所改变 了，那么线程 A 访问集合时，就会抛出 ConcurrentModificationException 异常，产生 fail-fast 事 件。这里的操作主要是指 add、remove 和 clear，对集合元素个数进行修改。

解决办法

建议使用“java.util.concurrent 包下的类”去取代“java.util 包下的类”。可以这么理解：在遍历之前，把 modCount 记下来 expectModCount，后面 expectModCount 去 和 modCount 进行比较，如果不相等了，证明已并发了，被修改了，于是抛出 ConcurrentModificationException 异常。

23、HashMap 和 HashTable 有什么区别？

①、HashMap 是线程不安全的，HashTable 是线程安全的；

②、由于线程安全，所以 HashTable 的效率比不上 HashMap；

③、HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而 HashTable不允许；

④、HashMap 默认初始化数组的大小为16，HashTable 为 11，前者扩容时，扩大两倍，后者扩大两倍+1；

⑤、HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode；

24、HashMap 是线程安全的吗？

不是，在多线程环境下，1.7 会产生死循环、数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题，以 1.8 为例，当 A 线程判断 index 位置为空后正好挂起，B 线程开始往 index 位置的写入节点数据，这时 A 线程恢复现场，执行赋值操作，就把 A 线程的数据给覆盖了；还有 ++size 这个地方也会造成多线程同时扩容等问题。

25、如何规避 HashMap 的线程不安全？

单线程条件下，为避免出现 ConcurrentModificationException，需要保证只通过 HashMap 本身或者只通过 Iterator 去修改数据，不能在 Iterator 使用结束之前使用 HashMap 本身的方法修改数据。因为通过 Iterator 删除数据时，HashMap 的 modCount 和 Iterator 的 expectedModCount 都会自增，不影响二者的相等性。如果是增加数据，只能通过 HashMap 本身的方法完成，此时如果要继续遍历数据，需要重新调用 iterator() 方法从而重新构造出一个新的Iterator，使得新 Iterator 的 expectedModCount 与更新后的 HashMap 的 modCount 相等。

多线程条件下，可使用两种方式：

• Collections.synchronizedMap 方法构造出一个同步 Map
• 直接使用线程安全的 ConcurrentHashMap。

26、HashMap 和 ConcurrentHashMap 的区别？

1. 都是 key-value 形式的存储数据；
2. HashMap 是线程不安全的，ConcurrentHashMap 是 JUC 下的线程安全的；
3. HashMap 底层数据结构是数组 + 链表（JDK 1.8 之前）。JDK 1.8 之后是数组 + 链表 + 红黑 树。当链表中元素个数达到 8 且数组长度大于等于 64 的时候，链表的查询速度不如红黑树快，链表会转为红黑树，红 黑树查询速度快；
4. HashMap 初始数组大小为 16（默认），当出现扩容的时候，以 0.75 * 数组大小的方式进行扩 容；
5. ConcurrentHashMap 在 JDK 1.8 之前是采用分段锁来现实的 Segment + HashEntry， Segment 数组大小默认是 16，2 的 n 次方；JDK 1.8 之后，采用 Node + CAS + Synchronized 来保证并发安全进行实现。

27、为什么 ConcurrentHashMap 比 HashTable 效率要高？

HashTable：使用一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易阻塞；

ConcurrentHashMap：

• JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。
• JDK 1.8 中使用CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry<K,V>）。锁粒度降低了。

28、说说 ConcurrentHashMap 中的锁机制

JDK 1.7 中，采用分段锁的机制，实现并发的更新操作，底层采用数组+链表的存储结构，包括两个核心静态内部类 Segment 和 HashEntry。

①、Segment 继承 ReentrantLock（重入锁） 用来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶；

②、HashEntry 用来封装映射表的键-值对；

③、每个桶是由若干个 HashEntry 对象链接起来的链表

JDK 1.8 中，采用 Node + CAS + Synchronized 来保证并发安全。取消类 Segment，直接用 table 数组存储键值对；当 HashEntry 对象组成的链表长度超过 TREEIFY_THRESHOLD 时，链表转换为红黑树，提升性能。底层变更为数组 + 链表 + 红黑树。

29、在 JDK 1.8 中，ConcurrentHashMap 为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？

①、粒度降低了；

②、JVM 开发团队没有放弃 synchronized，而且基于 JVM 的 synchronized 优化空间更大，更加自然。

③、在大量的数据操作下，对于 JVM 的内存压力，基于 API 的 ReentrantLock 会开销更多的内存。

30、能对 ConcurrentHashMap 做个简单介绍吗？

①、重要的常量：　　

private transient volatile int sizeCtl; 

当为负数时，-1 表示正在初始化，-N 表示 N – 1 个线程正在进行扩容；　　

当为 0 时，表示 table 还没有初始化；　　

当为其他正数时，表示初始化或者下一次进行扩容的大小。

②、数据结构：　　

Node 是存储结构的基本单元，继承 HashMap 中的 Entry，用于存储数据； 

TreeNode 继承 Node，但是数据结构换成了二叉树结构，是红黑树的存储结构，用于红黑树中存储数据；　　

TreeBin 是封装 TreeNode 的容器，提供转换红黑树的一些条件和锁的控制。

③、存储对象时（put() 方法）：　　

1. 如果没有初始化，就调用 initTable() 方法来进行初始化；　　
2. 如果没有 hash 冲突就直接 CAS 无锁插入；　　
3. 如果需要扩容，就先进行扩容；　　
4. 如果存在 hash 冲突，就加锁来保证线程安全，两种情况：一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入；　　
5. 如果该链表的数量大于阀值 8，就要先转换成红黑树的结构，break 再一次进入循环 　　
6. 如果添加成功就调用 addCount() 方法统计 size，并且检查是否需要扩容。

④、扩容方法 transfer()：默认容量为 16，扩容时，容量变为原来的两倍。　　helpTransfer()：调用多个工作线程一起帮助进行扩容，这样的效率就会更高。

⑤、获取对象时（get()方法）：　　

1. 计算 hash 值，定位到该 table 索引位置，如果是首结点符合就返回；　　
2. 如果遇到扩容时，会调用标记正在扩容结点 ForwardingNode.find()方法，查找该结点，匹配就返回；　　
3. 以上都不符合的话，就往下遍历结点，匹配就返回，否则最后就返回 null。

31、熟悉 ConcurrentHashMap 的并发度吗？

程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数。默认为 16，且可以在构造函数中设置。当用户设置并发度时，ConcurrentHashMap 会使用大于等于该值的最小 2 幂指数作为实际并发度（假如用户设置并发度为 17，实际并发度则为 32）。

总结

好了，就写这么多了，文章中很多已经不是 HashMap 知识点了，但，面试很有可能会问这些知识点，多准备点也算是有备无患。

所谓天才，只不过是把别人喝咖啡的功夫都用在工作上了。

——鲁迅

： » 分享一些 Java HashMap 高级面试题！