type
status
date
slug
summary
tags
category
icon
password

浅谈一下HashMap

0.1 什么是数组？

数组（Array）是一块连续的内存区域，支持 O(1) 时间复杂度的索引访问。
示例（长度为 5 的数组）：
特点：
  • 查询：可以直接通过索引访问元素，时间复杂度 O(1)。
  • 插入/删除：如果插入或删除会导致元素移动，平均时间复杂度 O(n)（除非操作的是末尾元素）。
  • 固定大小（在大多数编程语言中，数组的大小通常是固定的）。

0.2 什么是链表？

链表（Linked List）由多个节点组成，每个节点包含数据和指向下一个节点的指针。
示例（单向链表）：
特点：
  • 查询：必须从头遍历，平均时间复杂度 O(n)。
  • 插入/删除：只需调整指针，不涉及大量数据移动，时间复杂度 O(1)。
  • 动态大小，可以随时扩展。

0.3 什么是红黑树？

红黑树（Red-Black Tree）是一种 自平衡二叉搜索树（BST），其中每个节点有一个额外的 " 颜色 " 属性（红或黑）。 红黑树遵循以下规则：
  1. 每个节点要么是红色，要么是黑色。
  1. 根节点必须是黑色。
  1. 每个红色节点的子节点必须是黑色（不能有连续两个红色节点）。
  1. 从任何一个节点到其所有叶子节点的路径上，黑色节点数量必须相同。
  1. 插入或删除节点后，可能需要 旋转（左旋/右旋） 和 变色 来保持平衡。
示例：
特点：
  • 查询：时间复杂度 O(log n)。
  • 插入/删除：由于可能涉及旋转和变色，时间复杂度 O(log n)。
  • 自平衡：保证树的高度接近最小，使得查找高效。

1.1 HashMap 结合这些数据结构

在 HashMap 里：
  1. 数组 作为哈希桶（buckets），存储链表或红黑树的 头指针。
  1. 链表 处理哈希冲突（当多个键映射到相同索引时）。
  1. 红黑树 只有在某个桶中的链表长度超过阈值（如 8）时，该桶的链表才会转换为红黑树，提高查询效率。
示例（HashMap 结构）：
这样，HashMap 在大多数情况下查询时间接近 O(1)（数组 + 链表），而在极端情况下仍能保持 O(log n)（红黑树），至少不会是 O(n)。

1.2 HashMap 的扩容机制——负载因子（Load Factor）

  • 负载因子是 元素个数 / 哈希桶的数量，通常默认 0.75。
  • 当负载因子超过阈值时，HashMap 会扩容，使桶的数量翻倍，重新分布键值对。
    • 如果扩容后某个桶的元素减少到阈值以下（默认 6），该桶的红黑树会退化回链表，以节省内存。 （为什么不是 7？转为红黑树的阈值是 8，离得太近，可能会导致链表与红黑树的频繁转换，产生不必要的消耗。）
  • 目的：避免桶内链表过长，保证查询接近 O(1)。
示例：
假设 HashMap 初始大小是 16，负载因子 0.75，当元素数量达到 16 × 0.75 = 12 时，哈希表会扩容到 32 个桶，并重新分配已有键值对。这样做可以 减少哈希冲突，使链表长度保持较短。

1.3 哈希函数的均匀性

一个 优秀的哈希函数 会尽可能均匀地分布键值对，使每个桶的负载均衡，从而降低哈希冲突的概率。 理想情况下，哈希函数的分布类似于 泊松分布（Poisson Distribution） ：
  • 大多数桶的链表长度接近 0 或 1。
  • 少数桶的链表长度可能是 2 或 3。
  • 很少有桶的链表长度会超过 8（极端情况下才会发生）。
示例（假设有 16 个桶，插入 12 个元素，且哈希函数均匀）：
观察：大多数桶只包含 1 个元素，很少（产生哈希冲突）有桶内有 2 个或以上的元素。

1.4 计算桶内链表长度的期望

假设：
  • n 为存储的键值对个数
  • m 为桶的数量
  • λ = n / m 为 平均每个桶的键值对数量
如果 HashMap 选择合适的扩容策略（默认负载因子 0.75），可以保证 λ ≈ 0.75，那么按照泊松分布：
  • 约 36% 的桶是空的（链表长度 0）。
  • 约 39% 的桶只有 1 个元素（链表长度 1）。
  • 约 18% 的桶有 2 个元素（链表长度 2）。
  • 约 5% 的桶有 3 个元素（链表长度 3）。
  • 超过 8 个元素的概率极低（小于 0.0001），这也是 HashMap 选择在 8 这个阈值转换为红黑树的原因。
结论：大多数桶的链表长度通常为 1~2 个元素，超过 8 的情况极少。

Q：为什么链表通常不会长到 8？

我们要知道，绝大多数的 HashMap 中的一个桶通常只有两个数据左右，超过两个的都很少，如下：
  1. 其一：这是因为大多数 HashMap 实现（如 Java 的 HashMap）使用 哈希函数 + 取模运算 将键分布到不同的桶（bucket）中。理想情况下，哈希函数能够 均匀分布键值对，从而保持桶内元素数量尽可能少。这是由 哈希分布的概率特性 决定的。
  1. 其二：由于 HashMap 扩容的触发点 远远早于 链表转换为红黑树的阈值（8），所以在 大多数情况下，桶内的链表还没来得及增长到 8，HashMap 就已经扩容了，进而导致原本冲突的键可能会被分配到不同的桶中。
只有极端情况下（如哈希函数不均匀，或者数据特征导致大量键映射到相同桶）才会让某个桶的链表长度增长到 8，触发转换为红黑树。

2.1 哈希冲突的原因

哈希冲突发生在以下情况下：
  • 哈希函数 将不同的键映射到了同一个桶的索引位置。
  • 桶的容量有限，如果有多个键值对计算出的哈希值相同，或者有相同的哈希值映射到相同的桶，就会导致哈希冲突。

2.2 哈希冲突的处理

HashMap 通常通过以下几种方法来处理哈希冲突：

1. 链式法（Separate Chaining）

这是最常见的哈希冲突处理方法。当哈希冲突发生时，将发生冲突的所有元素存储在同一个桶中，桶内的元素通过链表相连，并按顺序存储在该桶内，链表的长度会随冲突元素的增加而增长。

2. 开放寻址法（Open Addressing）

另一种哈希冲突解决方法。不同于链式法，开放寻址法通过探测方法在其他桶中寻找空位来存储冲突的元素。若是发生哈希冲突，就以当前地址为基准，根据再寻址的方法（探查序列），去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止。常见的探测方法有 线性探测、二次探测 和 双重哈希。
在这种方法下，不会出现链表，而是通过探测空位来避免链表长度的增加。

3.1 HashMap 存放键值对的步骤

当你向 HashMap 中存入一个键值对 ("name", "tom")，HashMap 需要决定 "name" 这个键应该存在哪个桶（bucket）中。整个存储过程可以分为以下几个步骤：

1. 计算键的哈希值

HashMap 需要先计算 key 的哈希值（hashCode）。
在 Java 中，String 类的 hashCode() 计算方式如下：
假设 "name" 计算出的哈希值为：

2. 计算桶的索引

HashMap 通过 哈希值取模桶的数量 来确定 "name" 存在哪个桶。
在 Java 8 HashMap 里，取模操作使用 位运算：
假设 HashMap 现在容量为 16（默认初始值），即 table.length = 16：
所以，("name", "tom") 会被存放在索引 3 的桶。

3. 存入桶

如果索引 3 的桶为空，则 ("name", "tom") 直接存入。
如果索引 3 的桶已有元素（哈希冲突），则：
  • 使用链表法存入下一个节点。
  • 若链表长度达到 8，转换为红黑树。
HashMap 的 key 可以为 null，但只能有一个，且索引只能为 0。不会计算哈希值，避免 null 触发 hashCode() 方法（因为 null.hashCode() 会抛 NullPointerException）。

4. 读取 name 对应的 tom

当 map.get("name") 时：
  1. 计算 "name" 的 hashCode() 并计算索引为 3。
  1. 在索引 3 处找到匹配的 key，返回 value "tom"。

4.1 线程安全

HashMap 是线程不安全的，与之对应的是加了 synchronized 锁的 HashTable ，但 synchronized 打开销有点太大了。因此 HashTable 通常是不建议使用的。
如果你想要一种既线程安全又不至于让锁拖慢性能的解决方案，可以考虑以下几种选择：
  1. ConcurrentHashMapJava 提供了 ConcurrentHashMap，这是一个设计良好的线程安全的 Map 实现。它的优势在于：
      • Java 8 之前的版本：采用了 分段锁（segment locking） 技术，意味着对不同段的数据加锁，而不是对整个 Map 加锁。因此它的并发性能要比 Hashtable 好很多。
      • Java 8 之后的版本：去除了原来的分段结构，转而使用 桶（bucket）级别的锁 和 CAS（Compare-And-Swap） 操作。新的实现方法通过细化锁的粒度，进一步提高了性能，并且简化了设计。因此，在当前的实现中，我们通常不再提到段的概念，而是通过更细粒度的锁和无锁的 CAS 操作来实现高效的并发控制。
      • 它在大多数情况下提供比 Hashtable 更好的性能，尤其是在多线程读写的场景下。
  1. ImmutableMap如果数据一旦创建之后就不会修改，可以考虑使用不可变的 Map，比如 Guava 提供的 ImmutableMap。由于它是不可变的，因此在多线程环境下无需加锁，线程安全且性能很好。
  1. 使用 Collections.synchronizedMapCollections.synchronizedMap 是一个简单的解决方案，它用于将任何普通的 Map 转换为线程安全的版本。它通过在所有的 Map 方法上加锁来确保线程安全，避免多个线程同时修改 Map 数据导致的并发问题，虽然它解决了线程不安全的问题，但是它在多线程高并发的环境下，会导致较大的性能开销。
  1. CopyOnWriteMap (基于写时复制的策略)如果对读操作的并发要求很高，而对写操作的频率相对较低，可以考虑实现一种类似 CopyOnWriteMap 的数据结构（类似于 CopyOnWriteArrayList），它通过在写操作时 复制整个数据结构 来确保线程安全。虽然这种方式在写操作较少的情况下表现良好，但在频繁写操作的场景下性能较差。
如果你的应用场景是高并发读低并发写，ConcurrentHashMap 会是一个非常合适的选择。它的设计充分考虑了高效的并发操作，并且减少了锁竞争。
相关文章
栈和堆
Lazy loaded image
SpringBoot自动装配到底有什么用？
Lazy loaded image
栈和堆ThreadLocal
Loading...
林明菁
林明菁
一个思念的人
公告

🎉欢迎你来到我的博客🎉

去右下角歌单里点首歌听吧
因为博客里没什么好看的
🔰版本号：NotionNext 4.8.3🔰
目录
0%