HashMap 面试题解析

HashMap 是 Java 中非常重要的类,在面试中经常被提及。本文将通过介绍 HashMap 基本原理以及经典面试问题进行分析。

工作原理

HashMap 属于 Map 接口的一种实现,其基本实现原理是拉链法。
其内部主要包含了两个组成部分:数组table 和 桶(链表)bucket。
当对 HashMap 放入一个<key,value> 键值对时,会先对 key 调用 hashCode() 方法计算出一个哈希值,再通过一种散列函数将哈希值映射到 table 数组中的一个位置 index,随后将<key,value> 添加到 index 处的 bucket 中。
如对于 key1 来说:

1. int hash = key1.hashCode();
2. int index = hash & (table.length - 1);
3. 将<key1, value1>添加到table[index]链表上。
   当使用 get() 方法获取键值对时,也会先计算 index,再从对应的链表中找寻键的具体位置。

容量相关

• 1. 容量大小:HashMap 的容量为一个桶数组 table 的长度,table 的初始大小为 16,并且都是 2 的幂次方。
• 2. 容量变化:当存放元素超过负载因子(默认 0.75)时,HashMap 会进行 resize 操作,扩大桶数组 table 的容量。
• 3. 扩容步骤:
  1. 创建一个容量为旧容量两倍的新桶数组
  2. 遍历旧桶数组中的每个元素,重新计算 index,并放入新桶数组,这一步需要较多时间。
  3. 将旧桶数组指向新桶数组。

碰撞问题

冲突(Collision) 是 HashMap 中的一个重要问题。我们知道相同 key 会映射到同一个 index,造成链表的多条记录。

• 1. 开放地址法:链地址法。新元素不断找下一个空的位置插入。
• 2. 拉链法:新元素直接加入链表尾部,HashMap 采用的就是这种方法。
• 3. 再哈希法:重新计算 hash 值,再得到一个不同的 index。
     解决冲突有利于提高 HashMap 中搜索的效率。

1. HashMap 的基本原理

HashMap 的核心原理是哈希函数，它通过一个哈希函数将键映射到一个索引位置，然后在该索引位置上存储对应的值。哈希函数的设计需要满足均匀分布，以确保哈希冲突的概率最小。HashMap 中使用了一种叫做“开放地址”的策略来解决哈希冲突，即当两个键映射到同一个位置时，不直接覆盖原有的值，而是通过链表、红黑树等数据结构将这两个值存储在一起。

2. HashMap 的存储结构

HashMap 的存储结构包括两部分：哈希表和链表/红黑树。哈希表是一部分，它存储了所有的键值对，每个键值对都由一个哈希值和一个指向链表或红黑树的指针组成。链表或红黑树是另一部分，它们用于存储具有相同哈希值的键值对。当哈希冲突发生时，HashMap 会根据哈希冲突的位置将键值对插入到链表或红黑树中。

3. HashMap 的插入、查找、删除操作

HashMap 的插入操作分为两个步骤：计算哈希值和插入键值对。计算哈希值的目的是确定键值对在哈希表中的存储位置，这一步可以通过哈希函数来完成。插入键值对的过程分为两种情况：

• 当哈希值对应的位置为空时，直接将键值对插入到该位置。
• 当哈希值对应的位置不为空时，需要遍历链表或红黑树，查找是否存在相同的键值对。如果不存在，则插入键值对；如果存在，则根据键值对的比较结果进行更新。
  HashMap 的查找操作也是基于哈希函数的，它首先计算键的哈希值，然后根据哈希值在哈希表中查找对应的键值对。如果找到了，则直接返回对应的值；否则，返回 null。
  HashMap 的删除操作与插入操作类似，也需要遍历链表或红黑树。在遍历过程中，需要根据键值对的比较结果进行更新，以保持链表或红黑树的有序性。

4. HashMap 的并发访问问题

HashMap 在多线程并发访问时，可能会导致数据不一致或死循环等问题。这是因为 HashMap 的插入、查找、删除操作都需要遍历链表或红黑树，而遍历过程是一个线性的过程，无法并行执行。因此，在多线程环境下，需要对 HashMap 进行同步，以确保数据的安全和一致性。

5. HashMap 的泛型参数

HashMap 有一个泛型参数，用于指定键和值的类型。这个泛型参数可以是任何类型，包括基本类型、引用类型和数组类型等。在使用 HashMap 时，需要指定键和值的类型，并且键的类型不能为 null。

6. HashMap 与 TreeMap 的比较

HashMap 和 TreeMap 都是 Java 中常用的映射类型，它们之间有几个重要的区别：

• 存储结构：HashMap 使用哈希表和链表/红黑树存储数据，而 TreeMap 使用二叉树存储数据。
• 访问性能：由于 HashMap 使用了哈希函数，因此它的访问速度更快，尤其是针对特定的键值对。TreeMap 的访问性能则依赖于二叉树的高度。
• 插入、删除操作：HashMap 的插入、删除操作比较快，因为它们只需要修改链表或红黑树。TreeMap 的插入、删除操作需要修改整个二叉树，因此性能相对较差。
• 空间需求：HashMap 的空间需求与键值对的数量有关，而 TreeMap 的空间需求与二叉树的高度有关。因此，在键值对数量较小的情况下，HashMap 的空间需求更小；而在键值对数量较大的情况下，TreeMap 的空间需求更小。

HashMap: 实现原理及优化

1. HashMap的数据结构

HashMap是一种以键值对（key-value）形式存储数据的数据结构，它基于哈希表的实现。其中，键（key）用于唯一标识元素，值（value）则是与键相关联的数据。在HashMap中，键是唯一的，而值可以重复。

2. HashMap的工作原理

HashMap通过将键的哈希值映射到一个数组的索引位置来存储和获取数据。具体来说，当将一个键值对放入HashMap时，首先会计算键的哈希值，并根据哈希值找到对应的索引位置。如果该位置还没有元素，就直接将键值对存储在该位置上；如果该位置已经有元素，就使用链表或红黑树等数据结构将新的键值对追加到该位置上，以解决哈希冲突问题。

3. 当两个对象的hashCode相同会发生什么？

当两个不同的对象的hashCode相同时，会产生哈希冲突。这意味着这两个对象在HashMap中可能会被分配到相同的索引位置上。为了解决这个问题，HashMap使用链表或红黑树等数据结构将发生哈希冲突的元素链接在一起。

4. hash的实现及其原因

hash是将任意长度的输入通过哈希函数转换为固定长度的输出的过程。在HashMap中，哈希函数（Hash Function）负责计算键的哈希值。一个好的哈希函数应具备以下特点：

• 快速计算。哈希函数应该能够在常数时间（O(1)）内计算出哈希值，以保证高效的插入、查找和删除操作。
• 均匀分布。哈希函数应该将键的各种组合均匀地映射到哈希表的各个位置，以尽量减少哈希冲突。
• 随机性。哈希函数应该在一定程度上随机化，以防止恶意攻击者构造特定的输入来导致大量哈希冲突，并影响HashMap的性能。

5. HashMap的容量确定及loadFactor

HashMap的容量由table数组的长度决定，一般为2的幂次方。loadFactor（负载因子）是一个比例，默认为0.75。当HashMap中已存储的元素数量超过loadFactor乘以容量时（即负载因子阈值），就会触发数组的扩容操作。

容量的变化涉及两个相关的指标：扩容阈值（threshold）和加载因子（loadFactor）。扩容阈值等于容量乘以加载因子。当元素数量超过扩容阈值时，HashMap会进行扩容，将容量翻倍，然后重新计算扩容阈值。

6. HashMap中put方法的过程

当调用HashMap的put方法时，它会按照以下步骤进行操作：

1. 根据键的哈希值计算出对应的数组索引。
2. 如果该索引位置上没有元素，则直接将键值对存储在该位置上。
3. 如果该索引位置上已有元素，则使用链表或红黑树等数据结构追加到该位置上。
4. 如果追加的元素个数达到一定阈值（一般为8），并且HashMap中的总元素数量超过扩容阈值，就会触发数组的扩容操作。
5. 如果添加的键已存在于HashMap中，则新的值会覆盖旧的值。

7. 数组扩容的过程

数组的扩容是为了解决哈希冲突和提高HashMap的性能。当HashMap中的元素数量超过扩容阈值时，会触发数组的扩容操作。扩容过程分为以下几个步骤：

1. 创建一个新的数组，长度是原数组长度的两倍。
2. 将原数组中的元素逐个重新计算哈希值，并根据新的数组长度找到对应的位置。
3. 将元素按照新的索引位置重新插入新的数组中。
4. 扩容完成后，HashMap中的table引用指向新的数组。

8. 红黑树与链表

在HashMap中，当哈希冲突较严重时，链表的长度可能会变得很长，这会导致查找的时间复杂度从O(1)变为O(n)，严重影响性能。为了解决这个问题，Java 8引入了红黑树来替代链表。

红黑树是一种自平衡二叉查找树，它的插入、删除和查找操作的平均时间复杂度为O(log n)。当链表长度超过一个阈值（默认为8）时，HashMap会将链表转换为红黑树。当红黑树的节点数量减少到一定程度（阈值为6），又会将红黑树转换回链表。

选择红黑树而不是二叉查找树的原因在于红黑树具有更好的平衡性，能够保证最坏情况下的性能。而二叉查找树在某些情况下可能会退化，导致查找操作的时间复杂度为O(n)。

9. 对红黑树的见解

红黑树是一种自平衡的二叉查找树，它在插入、删除和查找操作上具有良好的平均和最坏情况性能。以下是对红黑树的一些见解：

• 红黑树的高度是不超过2log(n+1)的，其中n是树中节点的数量。这保证了红黑树的操作的时间复杂度为O(log n)。
• 红黑树的自平衡性是通过四个主要性质来实现的：树的节点是红色或黑色的，根始终是黑色的，每个叶节点（NIL节点）是黑色的，如果一个节点是红色的，则它的两个子节点都是黑色的，不能有两个连续的红色节点。
• 红黑树的旋转操作用于保持树的平衡性，包括左旋和右旋。通过旋转，可以将红黑树的节点重新调整，使之满足红黑树的性质。
• 红黑树在很多高级数据结构和算法中都有应用，如平衡二叉查找树、区间树等。

10. jdk8中对HashMap的改变

在JDK 8中，Java对HashMap做了一些改变，主要包括以下两个方面：

1. 引入红黑树。为了解决在哈希冲突严重时，链表长度过长导致性能下降的问题，将链表转换为红黑树，提高了查找的效率。
2. 对哈希算法的优化。在JDK 8中，对哈希函数的计算进行了改进，使得哈希值更加均匀分布，减少了哈希冲突的概率。

这些改变使得HashMap在处理大量数据时具有更好的性能和可扩展性。同时，在实际应用中，我们也可以根据需求选择使用其他具有类似功能的数据结构，如ConcurrentHashMap等。

结论

HashMap作为一个常用的数据结构，在实际应用中扮演着重要角色。选择合适的哈希函数实现、优化扩容策略、使用红黑树解决哈希冲突等都是为了提高HashMap的性能和可靠性。

通过深入理解HashMap的工作原理和优化策略，我们可以更好地使用HashMap，并在需要的时候根据实际需求选择合适的数据结构和算法，以获得更好的性能和效果。

其他问题

• HashMap 不是线程安全的,在多线程中需要进行同步或者使用 ConcurrentHashMap。
• HashMap 允许是 key 为 null,但只有一个 null key。
• 不保证元素的顺序,可以使用 LinkedHashMap 来保持元素的插入顺序。