有关 HashMap 必须知道的原理

的👋大家好！我是你们的老朋友 Java 学术趴，今天小编研究了一下 HashMap，给大家整理了一下有关 HashMap 的核心知识点以及底层的原理。

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

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

2. 说说 HashMap 的工作原理？

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

3. 使用 HashMap 时，当两个对象的 hashcaode 相同怎么办？

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

4. HashMap 的哈希函数是怎么设计的？

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

之所以这么做存在两个好处：

1. 一定要尽可能降低 hash 碰撞，越分散越好；

2. 算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；

5. HashMap 遍历方法有几种？

• Iterator 迭代器

• 最常见的使用方式，可同时得到 key、value 的值。

• 使用 foreach 方法

• 通过 key 的 set 集合遍历。

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

因为 key.hashCode()函数调用的是 key 键值类型自带的哈希函数，返回 int 型散列值。int 值范围为-2147483648~2147483647，前后加起来大概 40 亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。

设想，如果 HashMap 数组的初始大小才 16，用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。

7. 解决 hash 冲突有几种方式？

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

  但有 2 个缺点：

  比较浪费空间，消耗效率。根本原因还是数组的长度是固定不变的，不断 hash 找出空的 index，可能越界，这时就要创建新数组，而老数组的数据也需要迁移。随着数组越来越大，消耗不可小觑。

  get 不到，或者说 get 算法复杂。进是进去了，想出来就没那么容易了。

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

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

• 链式地址法： 把产生 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. 当链表长度 >= 8 时，为什么要将链表转换成红黑树？

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

12. 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; }复制代码

13. 说说 resize 扩容的过程

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

14. 说说 hashMap 中 get 是如何实现的？

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

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

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

16. 说说你对红黑树的了解

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

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

• 节点是红色或黑色。

• 根是黑色。

• 所有叶子都是黑色（叶子是 NIL 节点）。

• 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）

• 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。

17. JDK8 中对 HashMap 做了哪些改变？

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

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

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

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

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

• 如果类重写了 equals 方法，它也应该重写 hashCode 方法。

• 类的所有实例需要遵循与 equals 和 hashCode 相关的规则。

• 如果一个类没有使用 equals，你不应该在 hashCode 中使用它。

• 咱们自定义 key 类的最佳实践是使之为不可变的，这样，hashCode 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode 和 equals 在未来不会改变，这样就会解决与可变相关的问题了。

19. HashMap 的长度为什么是 2 的 N 次方呢？

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

20. HashMap，LinkedHashMap，TreeMap 有什么区别？

• LinkedHashMap 是继承于 HashMap，是基于 HashMap 和双向链表来实现的。

• HashMap 无序；LinkedHashMap 有序，可分为插入顺序和访问顺序两种。如果是访问顺序，那 put 和 get 操作已存在的 Entry 时，都会把 Entry 移动到双向链表的表尾(其实是先删除再插入)。

• LinkedHashMap 存取数据，还是跟 HashMap 一样使用的 Entry[]的方式，双向链表只是为了保证顺序。

• LinkedHashMap 是线程不安全的。

21. 说说什么是 fail-fast？

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

22. HashMap 和 HashTable 有什么区别？

• HashMap 是线程不安全的，HashTable 是线程安全的；

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

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

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

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

23. HashMap 是线程安全的吗？

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

24. 如何规避 HashMap 的线程不安全？

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

25. HashMap 和 ConcurrentHashMap 的区别？

• 都是 key-value 形式的存储数据；

• HashMap 是线程不安全的，ConcurrentHashMap 是 JUC 下的线程安全的；

• HashMap 底层数据结构是数组 + 链表（JDK 1.8 之前）。JDK 1.8 之后是数组 + 链表 + 红黑树。当链表中元素个数达到 8 的时候，链表的查询速度不如红黑树快，链表会转为红黑树，红黑树查询速度快；

• HashMap 初始数组大小为 16（默认），当出现扩容的时候，以 0.75 * 数组大小的方式进行扩容；

• ConcurrentHashMap 在 JDK 1.8 之前是采用分段锁来现实的 Segment + HashEntry，Segment 数组大小默认是 16，2 的 n 次方；JDK 1.8 之后，采用 Node + CAS + Synchronized 来保证并发安全进行实现。

26. 说说 ConcurrentHashMap 中 锁机制

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

①、Segment 继承 ReentrantLock（重入锁） 用来充当锁的角色，每个 Segment 对象守护每个散

列映射表的若干个桶；

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

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

• JDK 1.8 中，采用 Node + CAS + Synchronized 来保证并发安全。取消类 Segment，直接用 table 数

组存储键值对；当 HashEntry 对象组成的链表长度超过 TREEIFY_THRESHOLD 时，链表转换为红

黑树，提升性能。底层变更为数组 + 链表 + 红黑树。

27. 熟悉 ConcurrentHashMap 的并发度吗？

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

如果需要全部的 Java 八股文的，点击星球进行免费获取 星球 (Github 地址)如果没有 Github 的小伙伴儿。可以关注本人微信公众号：Java 学术趴，发送八股文，第一时间获取全部的通关八股文。最后：祝大家都能拿到满意的 offer，前程似锦