HashMap

1. `HashMap`概述与核心结构

1.1.基本概念

HashMap 是Java中基于哈希表的数据结构，用于存储键值对（key-value pairs），提供快速的插入、删除和查找操作。
主要特点：
- 非线程安全：HashMap不是线程安全的，无法在多线程环境中直接使用，可能导致数据竞争和不一致。在并发场景中，可以使用ConcurrentHashMap。
- 无序存储：HashMap不保证插入顺序和迭代顺序，键值对在内部存储时完全依据哈希值的位置，插入顺序和取出顺序可能不同。
- 支持null键和null值：HashMap允许一个null键和多个null值。null键通常被映射到数组的第一个位置，而null值在键值对中是允许的。

1.2.核心结构

数组 + 链表/红黑树：HashMap的底层数据结构是一个结合了数组、链表和红黑树的混合结构，用来处理存储和哈希冲突问题。

数组（Node<K, V>[] table）：
- HashMap的核心是一个数组，数组中的每个元素被称为“桶”（bucket），每个桶用来存储一个或多个键值对。
- 当HashMap初始化时，会分配一个默认长度为16的数组。通过扩容机制，HashMap可以在需要时增加数组的长度。
- 通过哈希定位数组索引：为了将键映射到数组的某个索引，HashMap使用一个哈希函数计算出键的哈希值，并对数组长度进行位运算。
链表（处理哈希冲突）：
- 当多个键的哈希值映射到相同的数组索引时，就会发生哈希冲突。HashMap使用链表来处理这种冲突。
- 每个桶位可以视为一个链表的头节点。当多个键映射到同一个桶位时，这些键值对会以链表形式存储。
- 查找时，HashMap会首先定位到桶位，然后遍历链表中的每个节点，逐一比较键的equals方法，以找到目标键值对。
红黑树（Java 8 及以后版本）：
- 从Java 8开始，为优化链表在高冲突情况下的查询效率，HashMap在链表长度超过阈值（默认8）时，将链表转为红黑树。红黑树是一种自平衡二叉搜索树，能将查找和插入效率提升至O(log n)。
- 红黑树的优势：在高度冲突的情况下，链表查找效率会下降到O(n)，而红黑树则能保持O(log n)的效率，大幅提升性能。
链表与红黑树的转换条件：
- 转换为红黑树：当同一个桶位上的链表长度达到8时，HashMap会将链表转换为红黑树。
- 退化为链表：当红黑树的节点数量因元素删除而减少至6以下时，红黑树会重新退化为链表，以减少内存占用。

1.3.工作原理

1.插入元素（put方法）：

HashMap首先调用键的hashCode()方法获取哈希值，再通过(n - 1) & hash计算出该键值对在数组中的桶位。

如果桶位为空，则直接将键值对存储在该位置。
如果桶位已有元素，HashMap会遍历该桶位的链表，检查是否存在相同键。如果找到相同键，则更新对应的值；若找不到，则将新元素添加到链表或红黑树中。

2.获取元素（get方法）：

HashMap通过键的哈希值确定桶位，再遍历该位置上的链表或红黑树来查找目标键。

在链表中，HashMap会依次调用链表节点的equals()方法，直到找到匹配的键值对。
在红黑树中，HashMap则利用红黑树的结构特性快速查找目标键，查找效率为O(log n)。

3.删除元素（remove方法）：

通过哈希值计算定位桶位后，HashMap会遍历该位置上的链表或红黑树，找到并删除目标键值对。

如果删除的节点来自红黑树，且节点数量减少到6以下，树结构会退化为链表，以降低维护红黑树的开销。

2. 哈希函数与冲突处理机制

2.3.哈希函数与数组索引计算

1.hashCode() 方法：

hashCode() 是Java中的一种基础方法，定义在Object类中，所有对象都继承此方法。hashCode()返回一个整数哈希值，该值用于确定对象的存储位置。

在HashMap中，键的哈希值是通过hashCode()方法生成的,该哈希值用于决定键值对存储在数组中的哪个桶位。不同的键可能会产生相同的哈希值，这称为“哈希冲突”。因此，HashMap会进一步对hashCode()的值进行处理，以降低冲突发生的概率。

2.通过(n - 1) & hash确定数组索引：

HashMap使用(n - 1) & hash的位运算将哈希值映射到数组的某个位置。

n表示当前数组的长度，(n - 1)确保生成的索引值在0到n-1之间。
例如，假设n = 16，即数组长度为16，n - 1 = 15（二进制为1111），此时hash & 15可以保留hash的低4位，从而得到一个0到15之间的索引值。

由于HashMap的数组长度始终为2的幂次方（例如16、32等），因此n-1的二进制表现形式全部为1。这种位运算（&操作）能快速将哈希值限制在数组范围内，并且均匀分布在数组各个位置，提高访问效率。

3.位运算优化（(hash(key) ^ (hash(key) >>> 16))）：

HashMap在计算最终哈希值时，还会将高位和低位混合，以减少高位和低位值的相似性带来的冲突。

hash(key)：首先调用键的hashCode()方法，生成一个整数哈希值。
hash(key) >>> 16：将哈希值右移16位（无符号右移，填充高位为0）。
hash(key) ^ (hash(key) >>> 16)：将原哈希值hash(key)和右移后的哈希值(hash(key) >>> 16)进行按位异或操作。

(hash(key) ^ (hash(key) >>> 16)) 的目的是通过混合哈希值的高位和低位，降低哈希值在不同对象之间相似的概率，可以避免冲突集中在某些低位，从而让哈希值分布更均匀。

2.2.哈希冲突处理

2.2.1. 链表法

当两个或多个键的哈希值映射到同一个桶位时，HashMap会使用链表来存储这些冲突的键值对。

1.工作原理：

如果某个键的哈希值与其他键冲突，即多个键被映射到相同的桶位，则HashMap会在该桶位创建一个链表，将所有冲突的键值对以链表节点的形式链接在一起。
链表的结构：每个链表节点是一个Node对象，包含键、值、哈希值以及下一个节点的引用。链表的头节点就是桶位，后续的冲突元素依次挂在该链表上。

2.插入过程：

当新键值对映射到已经被占用的桶位时，HashMap会沿着链表遍历每个节点，逐一调用equals()方法检查当前链表中是否已有相同的键。
如果找到相同的键，则直接替换其值；如果没有找到，则将新键值对作为新的节点，插入链表末尾（Java 7及之前版本是在链表头部插入）。

3.查找过程：

在查找时，HashMap首先定位到对应的桶位，如果该桶位包含链表，则沿着链表逐个节点查找目标键。
每次都调用equals()方法逐一比较节点中的键与目标键是否匹配。

4.链表的性能：

在低冲突的情况下，链表的性能较好，因为链表长度较短，查找、插入的时间复杂度接近O(1)。
但是在高冲突的情况下，链表长度会增加，查找和插入的时间复杂度会退化为O(n)，降低性能。

2.2.2. 红黑树优化（Java 8 引入）

为了解决高冲突情况下链表效率低的问题，Java 8在HashMap中引入了红黑树结构，当链表长度超过一定阈值时，链表会自动转换为红黑树，以提高查询和插入效率。

1.红黑树简介：

红黑树是一种自平衡的二叉搜索树，具有以下特点：

每个节点都被标记为红色或黑色。
根节点必须为黑色。
红色节点不能有红色子节点（即不能有连续的红色节点）。
从任一节点到其每个叶子节点的路径上，经过的黑色节点数量必须相同。
通过这些规则，红黑树能够保持自平衡，保证在最坏情况下查找和插入的时间复杂度为O(log n)。

2.链表转换为红黑树的条件：

当同一桶位的链表长度超过8时，HashMap会将该链表自动转换为红黑树，以提高查询和插入的效率。
这个阈值的设定是为了平衡性能和内存使用：链表在长度较短时性能尚可，转换为红黑树会带来额外的内存消耗，因此只有在链表长度较长时才转化。

3.红黑树的操作流程：

插入：当链表长度超过8时，HashMap会将链表转化为红黑树，并将新元素插入到红黑树中。
查找：在红黑树中查找某个键时，使用二叉搜索的方式，大大提高了效率，查找时间复杂度从O(n)降为O(log n)。
删除：在删除红黑树中的节点时，HashMap会维持红黑树的平衡性。如果节点数量减少到6以下，红黑树会退化回链表，以减少不必要的内存开销。

4.性能优化：

红黑树在高冲突时显著提升了HashMap的性能。即使大量元素映射到相同的桶位，红黑树依然可以保持O(log n)的查找、插入和删除效率。
通过红黑树优化，HashMap在处理冲突时的效率更加稳定，避免了链表退化为O(n)性能的情况。

链表与红黑树转换的条件

转换为红黑树：当链表长度达到8时，HashMap会将该链表转换为红黑树。
退化为链表：当红黑树节点数量因删除操作而减少至6以下时，红黑树会重新退化为链表。这一转换机制确保了HashMap在高冲突时有较好的性能，在低冲突时保持较低的内存占用。

3. 负载因子、初始容量与扩容机制

HashMap 的性能和效率与负载因子、初始容量以及扩容机制密切相关。理解这些概念可以帮助我们优化 HashMap 的使用，避免不必要的性能开销。

3.1. 负载因子（Load Factor）

负载因子定义：负载因子是 HashMap 中的一项关键参数，决定了在当前容量下 HashMap 能够容纳的最大元素数量。负载因子是一个介于 0 和 1 之间的浮点数，用于表示桶的装载比例。
默认值：HashMap 的默认负载因子是 0.75。这意味着，当 HashMap 中的元素数量达到其容量的 75% 时，将会触发扩容。
如何工作：当 HashMap 的填充度超过负载因子设定的阈值（即 容量 * 负载因子）时，HashMap 会触发扩容操作。通过合理设置负载因子，可以在 HashMap 中平衡空间效率和性能：
- 较低的负载因子（如 0.5）：更早触发扩容，能保证较少的哈希冲突，减少链表或红黑树的使用，从而提高查找效率，但会消耗更多内存。
- 较高的负载因子（如 1.0）：可以延迟扩容，节省内存，但会增加哈希冲突的可能，导致查找效率降低。
如何选择负载因子：通常默认的 0.75 可以平衡查找性能和内存占用。负载因子越高意味着空间利用率越高，但冲突和链表/红黑树的复杂度增加。因此，若数据量较多且较为稳定，且对性能要求较高，可以考虑降低负载因子；反之若内存紧张，且对性能要求较低，可以提高负载因子。

3.2. 初始容量

定义：初始容量是 HashMap 创建时桶（bucket）的数量。每个桶可以存放一个链表或红黑树来解决哈希冲突。
默认初始容量：HashMap 默认的初始容量为 16。也就是说，刚创建的 HashMap 会有 16 个桶。
重要性：合理的初始容量设置有助于减少扩容次数，避免不必要的性能开销。假如我们事先知道 HashMap 的大致数据量，最好在创建时设置适当的初始容量来容纳预期的数据量，从而减少扩容次数，提高性能。
设置初始容量的计算公式：
- 如果预计 HashMap 的键值对数量为 N，建议的初始容量为 N / 负载因子，并将该值向上取整为最接近的 2 的幂次方。
- 例如，若预计 HashMap 需要存储 1000 个元素，使用默认的负载因子 0.75，建议初始容量为 1000 / 0.75 ≈ 1333，最近的 2 的幂次方是 2048，因此可以将初始容量设为 2048。

3.3. 扩容机制

负载因子为 0.75 看起来确实意味着每个桶平均只有不到一个元素。然而，HashMap 中的冲突（即不同键映射到同一个桶位）并非完全均匀分布，而是受到 哈希函数、数据的散列特性、以及随机性等因素的影响。因此，尽管负载因子为 0.75，HashMap 中的某些桶仍可能会比其他桶容纳更多元素，从而形成 局部高密度 的情况。

触发条件：当 HashMap 中的元素数量达到 容量 * 负载因子 时，HashMap 会触发扩容操作。默认情况下，容量为 16，负载因子为 0.75，因此在插入第 13 个元素时（16 * 0.75 = 12），会触发第一次扩容。
扩容过程：
- 容量翻倍：每次扩容时，HashMap 的容量会翻倍。例如，第一次扩容后容量从 16 扩展到 32。
- 重新哈希与数据迁移：扩容后，HashMap 会重新计算每个键的哈希值，将所有键值对重新分布到新的桶中。此过程称为“重新哈希”或“rehash”。
  - 在扩容前，HashMap 中每个键值对的桶索引是根据 hash % 容量 计算的（通过位运算）。
  - 扩容后，容量改变了，因此每个键的桶索引也可能会变化。
  - 重新哈希和重新分布需要重新遍历所有键值对，将它们放入新的桶中，这一过程相对耗时。
性能影响：
- 重新计算哈希值与数据迁移：扩容操作会重新计算所有元素的哈希值并分配新的位置，这是一个较为耗时的操作，尤其在存储了大量数据时，扩容操作的性能开销较大。
- 频繁扩容的影响：如果初始容量设置较小且负载因子较低，HashMap 会频繁扩容，导致频繁的数据迁移和重新哈希。为了减少这种开销，建议在构建HashMap 时预估数据量并设置适当的初始容量。
扩容带来的链表/红黑树优化：扩容后，哈希表中原有的高冲突桶会被重新分布，减少了链表和红黑树的长度，从而提升查找和插入效率。

4. `HashMap`的核心操作及方法的功能与作用

1. put(K key, V value) - 插入元素

功能：将键值对（key 和 value）插入到 HashMap 中。如果该键已存在，则更新其对应的值。
作用：用于添加新的键值对或更新已有键的值。

2. get(Object key) - 获取元素

功能：根据指定的键返回其对应的值。如果键不存在，则返回 null。
作用：用于快速查找并获取指定键的值。

3. remove(Object key) - 删除元素

功能：根据指定的键删除对应的键值对，并返回被删除的值。如果键不存在，返回 null。
作用：用于从 HashMap 中移除指定的键值对。

4. containsKey(Object key) - 检查键是否存在

功能：检查 HashMap 中是否包含指定的键，返回布尔值 true 或 false。
作用：用于验证某个键是否已存在于 HashMap 中。

5. containsValue(Object value) - 检查值是否存在

功能：检查 HashMap 中是否包含指定的值，返回布尔值 true 或 false。
作用：用于验证某个值是否存在于 HashMap 中的任意键值对。

5. `HashMap`的线程安全性与并发问题

在多线程环境中使用 HashMap 时，可能会遇到一些潜在的并发问题，因为 HashMap 本身并不是线程安全的。下面详细介绍 HashMap 的线程不安全性、替代方案和快速失败机制。

5.1. 线程不安全性

HashMap 在多线程环境下可能会导致数据不一致甚至导致程序崩溃的现象，尤其是在高并发插入和扩容过程中。以下是一些常见的线程安全问题：

数据不一致：多个线程并发地对同一个 HashMap 进行插入、删除等修改操作，可能导致数据丢失或不一致。由于没有同步控制，某些键值对可能被覆盖或丢失，导致操作的最终结果不可预测。
死循环（Java 7 中的 Rehash 问题）：在 Java 7 中，HashMap 在扩容时会进行 rehash 操作（即重新分配所有键值对）。如果多个线程同时触发扩容，在 rehash 过程中可能会形成循环链表，从而导致线程进入无限循环状态，使程序卡死。
- Java 8 引入了红黑树以及改进的扩容机制，避免了这种死循环现象，但 HashMap 仍然不是线程安全的，无法解决所有并发问题。

5.2. 线程安全的替代方案

为了在多线程环境下安全地使用哈希表，Java 提供了 ConcurrentHashMap，一个适用于并发场景的线程安全哈希表实现。

ConcurrentHashMap 的特点：
- 线程安全：ConcurrentHashMap 是线程安全的，适用于高并发环境。在多线程环境下，它能够安全、高效地执行读写操作。
- 高效的锁机制：ConcurrentHashMap 使用了一种高效的锁机制，不会像传统同步锁那样锁住整个表，而是实现了更细粒度的控制。
实现细节：
- Java 7 中的分段锁：在 Java 7 中，ConcurrentHashMap 使用分段锁机制（Segment），将整个哈希表分为多个段，每个段相当于一个独立的小哈希表。读写操作只会锁住其中一个段，从而允许其他段的并发访问。
- Java 8 中的 CAS 和细粒度锁：从 Java 8 开始，ConcurrentHashMap 取消了分段锁，使用 CAS（Compare-And-Swap）和细粒度锁来管理桶（bucket）或链表/红黑树。这样可以进一步提高并发性能，因为不同的线程可以访问不同的桶，而不需要锁住整个 HashMap。
使用示例：

import java.util.concurrent.ConcurrentHashMap;public class ConcurrentHashMapSimpleExample {public static void main(String[] args) {// 创建一个 ConcurrentHashMapConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();// 创建并启动两个线程向 ConcurrentHashMap 插入元素Thread thread1 = new Thread(() -> {concurrentMap.put("apple", 10);System.out.println("Thread1 put: apple=10");});Thread thread2 = new Thread(() -> {concurrentMap.put("banana", 20);System.out.println("Thread2 put: banana=20");});thread1.start();thread2.start();// 等待两个线程完成操作try {thread1.join();thread2.join();} catch (InterruptedException e) {e.printStackTrace();}System.out.println("Final map: " + concurrentMap);}
}

5.3. 快速失败机制（Fail-Fast）与迭代器的使用

在 HashMap 和其他非线程安全的集合中，迭代器（Iterator）是用于遍历集合元素的工具。但在多线程或并发修改的情况下，HashMap 的迭代器提供了 快速失败机制（Fail-Fast），以避免并发修改带来的数据不一致问题。下面详细介绍快速失败机制、迭代器的使用以及注意事项。

什么是快速失败机制（Fail-Fast）

定义：快速失败机制是一种保护措施，用于在集合结构被修改时，防止迭代过程中出现数据不一致。当 HashMap 的迭代器检测到集合结构发生变化（如插入、删除操作）时，会抛出 ConcurrentModificationException 异常，以提醒用户不要在迭代时修改集合。
原理：
- HashMap 的迭代器维护一个修改计数器 modCount，用来记录集合结构的修改次数（例如 put 或 remove 操作）。
- 每次迭代操作都会检查 modCount 是否发生变化。
- 如果在迭代期间发现 modCount 的值不一致，意味着集合结构被修改，迭代器会立即抛出 ConcurrentModificationException 异常，终止遍历。这一机制称为快速失败机制。
目的：快速失败机制并不是完全的线程安全措施，而是为了提醒用户不要在单线程的迭代过程中修改集合。它主要用于防止单线程环境下的意外修改，避免出现数据不一致的情况。

HashMap 的迭代器（Iterator）

HashMap 提供了多种方式来获取迭代器，可以用于遍历键、值或键值对。

获取迭代器的方法：
- keySet().iterator()：返回键的迭代器，用于遍历 HashMap 中的所有键。
- values().iterator()：返回值的迭代器，用于遍历 HashMap 中的所有值。
- entrySet().iterator()：返回键值对的迭代器，用于遍历 HashMap 中的所有键值对。

迭代器的使用示例

以下示例展示了如何使用 HashMap 的迭代器来遍历键、值和键值对。同时说明了在迭代期间尝试修改集合结构时如何触发快速失败机制。

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;public class HashMapIteratorExample {public static void main(String[] args) {// 创建一个 HashMap 并添加一些键值对Map<String, Integer> map = new HashMap<>();map.put("apple", 10);map.put("banana", 20);map.put("cherry", 30);// 1. 使用 entrySet().iterator() 遍历键值对System.out.println("遍历键值对：");Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator();while (entryIterator.hasNext()) {Map.Entry<String, Integer> entry = entryIterator.next();System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());// 在迭代过程中尝试修改结构会抛出 ConcurrentModificationExceptionif (entry.getKey().equals("banana")) {map.put("date", 40);  // 尝试修改 HashMap}}}
}

结果说明

在此示例中，我们使用 entrySet().iterator() 获取 HashMap 的键值对迭代器，然后遍历每个键值对。

快速失败示例：当 iterator 遍历到键 banana 时，我们尝试向 HashMap 中插入新键值对 ("date", 40)。由于 HashMap 的结构被修改，modCount 发生了变化，触发快速失败机制，ConcurrentModificationException 异常被抛出，程序终止。

注意事项

快速失败机制的局限性：快速失败机制不能保证线程安全，它主要用于提醒在单线程中避免意外修改集合结构。即使抛出异常，也可能无法在高并发情况下完全防止数据不一致问题。
如何避免快速失败：
- 在多线程环境中，建议使用 ConcurrentHashMap，因为它支持并发访问，不会抛出 ConcurrentModificationException。
- 如果需要在单线程中安全地修改集合，可以使用 Iterator 的 remove() 方法，该方法可以安全地移除当前元素，不会触发快速失败。

6. 常见面试问题与高频考点

1. HashMap 的内部实现

结构：HashMap 底层结构是数组 + 链表 + 红黑树的组合。

数组：用于存储每个桶的地址，查找效率高。
链表：当哈希冲突时，同一桶位的元素形成链表。
红黑树：当链表长度超过 8 时转换为红黑树，查找效率提升至 O(log n)。

2. 如何解决 HashMap 中的哈希冲突？

冲突处理：HashMap 使用链表和红黑树解决哈希冲突。

链表：当多个键映射到相同桶位时形成链表，查找效率为 O(n)。
红黑树：当链表长度达到 8 时，链表会转换为红黑树，将查找效率提升至 O(log n)。

3. 为什么使用自定义对象作为键时需要重写 equals 和 hashCode 方法？

hashCode 作用：hashCode 方法用于生成哈希值，确定键在 HashMap 中的桶位位置。自定义对象需要保证相同对象返回相同的哈希值，以确保相同对象映射到相同的桶。
equals 作用：当 hashCode 冲突（即不同对象的哈希值相同）时，HashMap 通过 equals 方法确认是否为同一键。equals 确保不同对象不会被认为是相同的键，从而保证键的唯一性。

4. 扩容机制及其影响

扩容触发条件：HashMap 在元素数量达到 容量 * 负载因子 时触发扩容。默认负载因子为 0.75。
扩容过程：容量翻倍，所有键重新计算哈希值并重新分布。
性能影响：扩容导致重新哈希和数据迁移，影响性能。合理设置初始容量和负载因子可以减少扩容次数，优化性能。

5. 线程安全性与 ConcurrentHashMap

问题：HashMap 在多线程环境中可能会导致数据丢失或死循环（特别是 Java 7 的 rehash 过程），因此不适用于并发场景。
解决方案：使用 ConcurrentHashMap，它是线程安全的哈希表实现。
- Java 7：分段锁机制，将哈希表分成多个段，降低锁竞争。
- Java 8：使用 CAS 和细粒度锁替代分段锁，进一步提升并发性能。

7. 高频面试算法题

1. 统计字符串中每个字符出现的次数

问题描述：给定一个字符串，统计每个字符出现的次数，并返回一个键值对的映射，其中键是字符，值是出现次数。

解决思路：

创建一个 HashMap，其中字符作为键，出现次数作为值。
遍历字符串，对于每个字符：
- 如果字符已存在于 HashMap 中，更新其出现次数。
- 如果字符不存在于 HashMap 中，将其添加并初始化次数为 1。

代码示例：

import java.util.HashMap;
import java.util.Map;public class CharacterFrequency {public static void main(String[] args) {String input = "hello world";Map<Character, Integer> frequencyMap = new HashMap<>();for (char c : input.toCharArray()) {// 获取字符当前计数，若字符不存在则默认为0，然后+1更新计数frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);}System.out.println(frequencyMap);  // 输出每个字符的出现次数}
}

分析：

该算法的时间复杂度为 O(n)，其中 n 是字符串的长度。
使用 HashMap 能快速查找和更新字符频率。

2. 查找两个数组的交集

问题描述：给定两个数组，找到它们的交集，即返回在两个数组中都出现的元素。

解决思路：

使用 HashMap 存储第一个数组的元素，并记录其出现的次数（或简单地记录其存在）。
遍历第二个数组，对于每个元素检查是否存在于 HashMap 中。
如果存在，说明该元素是交集的一部分，可以将其添加到结果集合中。

代码示例：

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;public class ArrayIntersection {public static void main(String[] args) {int[] nums1 = {1, 2, 2, 1};int[] nums2 = {2, 2};Set<Integer> result = new HashSet<>();HashMap<Integer, Integer> map = new HashMap<>();// 将第一个数组的元素存入 HashMapfor (int num : nums1) {map.put(num, map.getOrDefault(num, 0) + 1);}// 遍历第二个数组，检查交集元素for (int num : nums2) {if (map.containsKey(num) && map.get(num) > 0) {result.add(num);           // 交集元素map.put(num, map.get(num) - 1); // 更新出现次数}}System.out.println(result);  // 输出交集}
}

分析：

时间复杂度为 O(m + n)，其中 m 和 n 是两个数组的长度。
使用 HashMap 可以快速检查每个元素是否在第一个数组中出现过。
注意：此方法适用于不计较元素重复出现次数的交集。如果需要记录重复次数，可将 HashMap 值设为出现次数。

3. 判断一个数组中是否存在重复元素

问题描述：给定一个数组，判断是否存在重复元素。如果存在任意一个重复元素，返回 true，否则返回 false。

解决思路：

使用 HashMap 来记录数组中已经遍历过的元素。
遍历数组，对于每个元素：
- 如果该元素已经存在于 HashMap 中，则返回 true。
- 如果该元素不存在，则将其添加到 HashMap。
如果遍历结束没有发现重复元素，返回 false。

代码示例：

import java.util.HashMap;public class ContainsDuplicate {public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 1};boolean hasDuplicate = false;HashMap<Integer, Boolean> map = new HashMap<>();for (int num : nums) {if (map.containsKey(num)) {hasDuplicate = true;  // 找到重复元素break;}map.put(num, true);}System.out.println("Contains duplicate: " + hasDuplicate);  // 输出是否存在重复}
}

分析：

时间复杂度为 O(n)，其中 n 是数组长度。
使用 HashMap 可以在 O(1) 的时间复杂度内检查每个元素是否已存在，提高查找效率。

8.手撕HashMap

1. 类结构

public class MyHashMap<K, V> {// 哈希表的默认容量private static final int DEFAULT_CAPACITY = 16;private static final float LOAD_FACTOR = 0.75f;private Node<K, V>[] table;private int size;

MyHashMap 是一个泛型类，用于存储键值对，K 表示键的类型，V 表示值的类型。
DEFAULT_CAPACITY 设置默认的哈希表大小为 16；LOAD_FACTOR 是装载因子，用来控制何时扩容。
table 是存储节点的数组（称为“桶数组”），存储哈希表的数据。
size 表示哈希表中实际存储的元素个数。

2. 内部节点类（Node）

static class Node<K, V> {final K key;V value;Node<K, V> next;public Node(K key, V value) {this.key = key;this.value = value;}
}

Node 是一个内部类，代表哈希表中的单个节点。
每个 Node 包含 key 和 value，以及一个 next 指针，构成链表结构，用于解决哈希冲突。
next 用来连接同一个索引位置的下一个节点。

3. 构造函数

public MyHashMap() {table = new Node[DEFAULT_CAPACITY];
}

这是默认构造函数，初始化一个 Node 数组，大小为 DEFAULT_CAPACITY。

4. 哈希函数

private int hash(K key) {return (key == null) ? 0 : Math.abs(key.hashCode()) % table.length;
}

hash 函数将 key 转换为一个数组索引。若 key 是 null，则返回 0，否则根据哈希值计算索引位置。
使用 hashCode() 生成哈希值，再取模来得到数组索引。这是哈希表的核心，通过哈希函数使键均匀地分布在数组中，减少冲突。

5. 添加元素 - put 方法

public void put(K key, V value) {int index = hash(key);Node<K, V> head = table[index];// 检查是否已存在该键，若存在则更新值while (head != null) {if (head.key.equals(key)) {head.value = value;return;}head = head.next;}// 创建新的节点并插入链表头部Node<K, V> newNode = new Node<>(key, value);newNode.next = table[index];table[index] = newNode;size++;// 扩容检查if (size >= table.length * LOAD_FACTOR) {resize();}
}

put 方法用于添加键值对。

获取索引：通过 hash 函数得到存放键值对的数组索引。
冲突检查：检查该索引是否有链表。如果该链表中已有相同键，直接更新值并返回。
新节点插入：如果没有相同键，新建一个 Node 节点，并将其插入链表的头部（表明我们采用链地址法解决冲突）。
扩容检查：判断当前元素数量 size 是否超过 LOAD_FACTOR * 数组容量，若超过则扩容。

6. 获取元素 - get 方法

public V get(K key) {int index = hash(key);Node<K, V> head = table[index];while (head != null) {if (head.key.equals(key)) {return head.value;}head = head.next;}return null;
}

get 方法用于根据键查找对应的值。

获取索引：通过 hash 函数定位到对应的数组索引。
链表遍历：遍历该索引位置的链表，查找键是否存在。若找到相同键则返回值，否则继续查找。
返回值：如果遍历结束后没有找到，返回 null 表示该键不存在。

7. 删除元素 - remove 方法

public void remove(K key) {int index = hash(key);Node<K, V> head = table[index];Node<K, V> prev = null;while (head != null) {if (head.key.equals(key)) {if (prev != null) {prev.next = head.next;} else {table[index] = head.next;}size--;return;}prev = head;head = head.next;}
}

remove 方法用于删除指定键的节点。

定位索引：通过 hash 函数计算数组索引。
查找节点：遍历链表，查找指定键的节点。
删除节点：如果找到该节点，通过调整链表指针将其从链表中移除。如果该节点是链表的第一个节点，则直接修改 table[index]；否则通过 prev 将 next 指向删除节点的下一个节点。

8. 扩容方法 - resize

private void resize() {Node<K, V>[] oldTable = table;table = new Node[oldTable.length * 2];size = 0;for (Node<K, V> headNode : oldTable) {while (headNode != null) {put(headNode.key, headNode.value);headNode = headNode.next;}}
}