一、什么是工业级 HashMap？

哈希表（Hash Map），平均时间复杂度为 O(1) 的键值对存储结构，是最常用和强大的工具之一。“工业级 HashMap”不仅指实现了基本插入、查找和删除功能的哈希表。还是一个在严苛生产环境中能够稳定运行、性能卓越、资源高效、具备良好可维护性的数据结构。

一个工业级的 HashMap ：

1. 不仅要保证平均 O(1) 的时间复杂度，还要关注最坏情况下的性能表现，以及在不同负载、不同数据分布下的稳定性和效率。
2. 在各种异常情况下保持数据完整性，不崩溃，不产生未定义行为。
3. 最小化内存开销，避免内存碎片。
4. 在多线程或多进程环境下，安全、高效进行读写操作，避免数据竞争和死锁，提高并行度。
5. 可以自定义哈希函数、相等比较器、内存分配器等。

C++ STL 的std::unordered_map 提供有哈希表的基本功能，经过了高度优化，能满足大多数应用的需求。但在对性能、内存或并发有极致要求的特定场景下，std::unordered_map 的通用性就无法完全满足。

构建一个工业级的 HashMap 是要求在数据结构、算法、系统编程和并发控制等多个领域都有深刻的理解。

1. 选择合适的冲突解决策略不容易。每种策略都有优缺点，设计一个既快速又均匀分布的哈希函数，很难。
2. 频繁的内存分配和释放会导致性能下降和内存碎片。
3. 多线程环境下，确保 HashMap 的线程安全又不牺牲性能非常难。
4. HashMap 中的元素数量增长到一定程度时，要进行扩容（Rehash）。这是一个 O(N) 的操作，如果处理不当，会导致程序在某一时刻出现明显的性能卡顿。

二、 HashMap 核心原理和基础结构

哈希表把键映射到数组的某个索引位置来实现快速查找。

2.1、基本构成

一个 HashMap 主要由两个核心部分构成：

1. 桶数组： 一个底层的数据存储结构，是一个动态大小的数组。数组的每个元素称为“桶”（Bucket）或“槽”（Slot）。键值对就存储在这些桶中。桶的数量决定了哈希表的容量，也直接影响哈希冲突的概率。在链式法中，每个桶存储一个指向链表头部的指针；在开放寻址法中，每个桶直接存储键值对或其状态。
2. 哈希函数： 哈希函数把任意大小的键（Key）映射到一个固定大小的整数，这个整数就是桶数组的索引。哈希函数 H(key) 会计算出一个哈希码，然后通过 hash_code % capacity得到最终的桶索引。哈希函数的质量直接决定了 HashMap 的性能。一个好的哈希函数能够把键均匀地分布到各个桶中，减少冲突，提高查找效率。

2.2、哈希函数的设计

哈希函数是 HashMap 性能的关键决定因素，确保键的均匀分布，最小化冲突，保持接近 O(1) 的平均时间复杂度。

理想哈希函数的特性：

• 哈希值的计算过程必须尽可能快，因为每次插入、查找、删除操作都要先计算哈希值。
• 对不同的输入键，哈希函数要能够均匀映射到哈希表的整个地址空间（即桶数组的索引范围）。每个桶被选中的概率大致相等，减少冲突。
• 不同的键生成相同哈希值的概率要尽可能低。虽然完全避免碰撞是不可能的（因为键空间通常远大于哈希值空间），但一个好的哈希函数要能有效降低碰撞频率。
• 同一个键在任何时候、任何上下文中都必须生成相同的哈希值。这是哈希表的基本前提。

常见哈希算法：

• 整数键： 对整数类型的键，如果本身就比较均匀，可以直接用键本身作为哈希码，或者进行一些位操作来增加随机性。
• DJB2 算法： 一种简单、广泛使用的字符串哈希算法，通过位移和乘法操作，能产生不错的分布。
• FNV-1a 算法： 高效的非加密哈希算法。
• MurmurHash3： 非加密型哈希函数，因为高性能和良好的散列质量而闻名，适合大数据和分布式系统。
• std::hash： C++11 引入的 std::hash 模板类，为基本类型和一些标准库类型提供默认的哈希函数。

自定义哈希函数和 std::hash 的扩展：

• 自定义类型（struct 或 class），std::hash 默认是无法工作的，除非为其提供特化版本。
• 方法一： 为自定义类型 MyClass 提供 std::hash<MyClass> 的特化。
• 方法二：作为模板参数传入自定义哈希器。

设计自定义哈希函数一个常见的技巧是结合各个成员的哈希值，用异或操作或 boost::hash_combine 类似的算法来生成最终哈希值。

2.3、键值类型和模板化

实现一个通用的、能够存储任意类型键值对的 HashMap，C++ 的模板机制不可或缺。一个工业级的 HashMap 应该像 std::unordered_map 一样，通过模板参数来定义其行为和存储类型。

template <typename Key, typename Value,
          typename Hasher = DefaultHasher<Key>, // 默认哈希函数
          typename KeyEqual = std::equal_to<Key>, // 默认键相等比较器
          typename Allocator = std::allocator<std::pair<const Key, Value>>> // 默认内存分配器
class IndustrialHashMap {
    // ... 内部实现 ...
};

• typename Key： 键的类型。可以是基本类型、标准库类型或自定义类型。
• typename Value： 值的类型。同样，可以是任意类型。
• typename Hasher = DefaultHasher<Key>： 模板参数，指定哈希函数。默认情况下，提供一个 DefaultHasher，尝试用 std::hash<Key>。如果 Key 是自定义类型且没有特化 std::hash，就要提供自己的 Hasher 类。
• typename KeyEqual = std::equal_to<Key>： 模板参数，指定键的相等比较器。哈希函数计算出相同的桶索引时（发生碰撞），或者在链表中遍历查找时，要用这个比较器来判断两个键是否真正相等。默认情况下，std::equal_to<Key> 用 operator== 进行比较。对于定义类型， operator== 要重载。
• typename Allocator = std::allocator<std::pair<const Key, Value>>>： 模板参数，指定内存分配器。

三、冲突解决策略

哈希冲突是哈希表不可避免的问题。两个不同的键通过哈希函数计算出相同的桶索引就会发生冲突。

3.1、链式法

链式法是解决哈希冲突最常用、相对简单的策略之一。

原理： 每个桶不直接存储键值对，而是存储一个指向一个链表的指针。所有哈希到同一个桶的键值对都会添加到这个数据结构。查找、插入或删除一个键值对，首先计算哈希值得到桶索引，然后在这个桶对应的链表中进行遍历操作。

数据结构：

• 单向链表/双向链表： 最常见的选择，实现简单。
• 红黑树： 链表过长时，为了保证最坏情况下的性能，把链表转换为红黑树。查找时间复杂度从 O(N) 降低到 O(logN)。
• 跳表： 也是一种可以替代链表，提供 O(logN) 平均性能的数据结构。

优点：

• 容易理解，实现相对简单。
• 负载因子可以超过 1： 即使元素数量远超桶的数量，HashMap 也能正常工作，只是性能会下降。
• 删除操作相对容易： 只要在链表找到并移除节点，然后调整指针即可。
• 哈希函数分布不够均匀，也能通过链表来容纳冲突，只是性能会受影响。

缺点：

• 要额外的指针存储空间： 每个节点都要一个 next 指针，增加内存开销。
• 链表节点在内存中不连续，CPU 缓存命中率低，影响性能。
• 在最坏情况下（所有键都哈希到同一个桶），查找、插入和删除操作的时间复杂度会退化到 O(N)，类似于遍历一个普通链表。

工业级改进：

• 链表长度阈值转换红黑树： std::unordered_map 常用的一种优化策略。桶中的链表长度超过一个预设阈值就转换为红黑树。这样，在哈希冲突严重的情况下，也能把最坏情况下的查找时间复杂度从 O(N) 降低到 O(logN)。
• 频繁的 new 和 delete 操作会导致内存碎片和系统调用开销。用内存池可以预先分配一大块内存，然后从池中快速分配和回收节点，减少内存管理开销，提高性能。

// 链式法桶结构
template <typename Key, typename Value>
struct Node {
    Key key;
    Value value;
    Node* next; // 指向链表中下一个节点

    Node(const Key& k, const Value& v) : key(k), value(v), next(nullptr) {}
    // 考虑使用emplace_back等方式原地构造Value
    template<typename... Args>
    Node(const Key& k, Args&&... args)
        : key(k), value(std::forward<Args>(args)...), next(nullptr) {}
};

3.2、开放寻址法

开放寻址法跟链式法不同，不用额外的数据结构来存储冲突的键值对，而是直接在桶数组中寻找下一个空闲位置。

原理： 键的哈希值指向的桶已经被占用时，开放寻址法按照探测序列在桶数组中寻找下一个可用的空槽位来存储该键值对。查找时也遵循相同的探测序列，直到找到目标键或遇到空槽位。

探测方式：

（1）线性探测： H(key) 所在的桶被占用时，依次检查 (H(key) + 1) % capacity，(H(key) + 2) % capacity，以此类推，直到找到一个空槽位。

• 优点： 实现简单，缓存局部性好（因为探测的地址是连续的）。
• 缺点： 容易产生“一次聚集”。即连续的已占用槽位会形成一个大的块，导致后续的插入和查找操作要遍历更长的序列，性能急剧下降。

（2）二次探测： H(key) 所在的桶被占用时，依次检查 (H(key) + 1^2) % capacity，(H(key) + 2^2) % capacity，(H(key) + 3^2) % capacity，以此类推。

• 优点： 缓解了线性探测的“一次聚集”问题。
• 缺点： 产生“二次聚集”。即具有相同初始哈希值的键，探测序列是相同的，仍然会出现聚集。此外，如果表的大小不是素数，二次探测无法探测到所有空槽位。

（3）双重哈希： 用两个哈希函数 H1(key) 和 H2(key)。当 H1(key) 所在的桶被占用时，探测序列为 (H1(key) + i * H2(key)) % capacity，其中 i 从 1 开始递增。H2(key) 必须是一个永不返回 0 的哈希函数，且跟 capacity 互质，确保能探测到所有槽位。

• 优点： 探测序列更加随机，能有效减少各种聚集问题，是开放寻址法中性能最好的探测方法。
• 缺点： 要设计两个高质量的哈希函数。

开放寻址法的优点：

• 每个桶直接存储键值对，内存利用率更高。
• 数据存储在连续的内存区域中，探测序列也是连续或跳跃性较小的，有利于 CPU 缓存。
• 一次性分配大块内存，减少小对象频繁分配带来的碎片问题。

开放寻址法的缺点：

• 负载因子不能超过 1： HashMap 接近满载时，性能会急剧下降，负载因子最好不超过 0.7-0.8。
• 删除操作复杂： 简单把一个槽位标记为空会导致后续依赖该槽位的查找链断裂。要引入一个“已删除”状态，查找时跳过已删除的槽位，插入时可以覆盖已删除的槽位。有点复杂。
• 实现比链式法更复杂。

工业级改进：

• 槽位状态标记： 用枚举或特殊值来标记每个槽位的状态（EMPTY、OCCUPIED、DELETED）。DELETED 状态处理删除操作，保证查找路径的完整性。
• 对双重哈希，选择一个能够产生良好分布且第二个哈希函数 H2(key) 始终为非零值的哈希函数。
• 为了避免二次探测和双重哈希的循环问题，桶数组的大小设置为素数，或 2 的幂次。
• DELETED 状态的槽位会随着时间积累，影响性能。可以在扩容时清理这些已删除的槽位，或者在达到一定数量的 DELETED 槽位后触发一次局部清理。

// 开放寻址法桶结构
enum SlotStatus {
    EMPTY,      // 空槽位
    OCCUPIED,   // 已占用
    DELETED     // 已删除 (用于处理删除操作)
};

template <typename Key, typename Value>
struct Slot {
    Key key;
    Value value;
    SlotStatus status;

    Slot() : status(EMPTY) {}
    // 构造函数，用于OCCUPIED状态
    Slot(const Key& k, const Value& v) : key(k), value(v), status(OCCUPIED) {}
    template<typename... Args>
    Slot(const Key& k, Args&&... args)
        : key(k), value(std::forward<Args>(args)...), status(OCCUPIED) {}
};

四、动态扩容

HashMap 的性能高度依赖其负载因子和桶的数量。随着键值对数量的增加，哈希冲突的概率会上升，链表变长（链式法）或探测序列变长（开放寻址法），使查找、插入和删除操作的性能从 O(1) 逐渐退化。为了维持高效的性能，元素数量达到一定阈值就要进行扩容。

扩容触发条件：

• 负载因子 衡量 HashMap 满载程度的指标，负载因子 (λ) = 当前元素数量 (size) / 桶数组容量 (capacity)。负载因子超过预设的**阈值 ** 就触发扩容操作。
• 链式法，负载因子可以大于 1，但最好在 0.7 到 1.0 之间。std::unordered_map 的默认最大负载因子是 1.0。
• 开放寻址法，负载因子必须小于 1，最好在 0.5 到 0.8 之间，避免过多的冲突和过长的探测序列。

扩容过程：重新构建哈希表。

1. 桶数组的容量翻倍，或者选择一个更大的素数作为新容量。
2. 分配一块新的内存空间，存储新的、更大的桶数组。
3. 遍历旧桶数组中的所有键值对。对于每一个键值对，重新计算新容量下的哈希值，插入到新桶数组中对应的位置。一定要注意，只复制数据是不够的，因为桶索引是基于容量计算的 (hash_code % capacity)。容量改变后，相同的哈希值会映射到不同的桶索引，所以必须重新计算并插入。
4. 旧的桶数组释放，用新的桶数组替换。

扩容操作要遍历所有 N 个元素并重新插入，时间复杂度为 O(N)。存储大量数据时，这个操作会非常耗时，在扩容期间容易出现明显的性能卡顿。

为了缓解扩容带来的性能尖峰，工业级 HashMap 会采用一些策略：

（1）渐进式扩容： 渐进式扩容的核心思想是把 O(N) 的扩容工作分解成多个小步骤，分摊到后续的插入、查找或删除操作中。这样，每次操作的平均成本仍然保持在 O(1)，但单次操作的最坏情况成本不再是 O(N)。

原理：

1. 触发扩容条件不立即完成整个扩容过程。
2. 创建一个新的、更大的桶数组 (new_buckets)，保留旧的桶数组 (old_buckets)。
3. 每次进行 insert、find、erase 等操作时，除了处理当前操作外，还从 old_buckets 中迁移少量键值对到 new_buckets。
4. 在迁移过程中，查找操作要同时检查 new_buckets 和 old_buckets。插入操作则只插入到 new_buckets。
5. old_buckets 中的所有元素都迁移完毕后，就可以释放 old_buckets，完成扩容。

优点： 避免单次操作的性能尖峰，扩容成本平摊到多次操作中，每次操作的感知延迟更小。
缺点： 实现复杂。扩容期间要同时维护两个哈希表，增加内存使用。查找操作要检查两个表，略微增加查找的常数时间。

（2）预分配： 提前预估要存储的元素数量，在初始化时就分配足够的容量，或者在知道元素数量即将大幅增加时，主动调用 reserve() 方法进行扩容。

原理： 通过 reserve(expected_size) 方法，一次性分配足够的内存，避免后续因为元素增加而频繁触发的小规模扩容。

• 优点： 避免多次扩容的开销，减少数据迁移的次数。
• 缺点： 如果预估不准确，会浪费内存（预估过大）或仍然要扩容（预估过小）。
• 适用场景： 元素数量相对固定，或者可以准确预估最大元素数量的场景。

五、结语

能手写工业级 HashMap 的程序员水平不予评论，因为HashMap 有简单的，也有复杂的，不是说冠以 工业级 的头衔就能判定 HashMap 的复杂程度；要看应用的场景而定！！！

但是，不管怎么说，能手写一个 HashMap，就说明一定懂：

• 哈希表核心原理：哈希函数、哈希冲突、负载因子、扩容机制。。
• 数组、链表、红黑树、跳表等数据结构。
• hash算法。
• 内存管理原理：内存布局、内存碎片、CPU缓存局部性。
• 并发安全。