2.14、hashtable的实现原理

1. Hashtable 的核心思想

Hashtable 是一种基于数组的数据结构，通过哈希函数将任意大小的关键字映射成固定范围内的整数索引，直接定位到存储桶（bucket）或槽（slot）中。这样避免了传统线性查找或树形查找中需要多次比较关键字的过程，实现了平均 O(1) 时间复杂度的访问速度。

• • 哈希函数（Hash Function）：将关键字映射为数组索引的函数。好的哈希函数应满足均匀分布、计算快速、减少冲突（collision）。
• • 冲突处理（Collision Resolution）：由于哈希函数可能将不同关键字映射到相同索引，需要采用冲突解决策略，常见的有：
  • • 链地址法（Separate Chaining）：每个槽维护一个链表或其他结构，冲突元素挂载在链表中。
  • • 开放地址法（Open Addressing）：发生冲突时，按一定探查序列寻找下一个空槽，如线性探测、二次探测、双重哈希等。

2. Hashtable 的基本操作实现

• • 插入（Insert）：
  1. 1. 通过哈希函数计算关键字的索引。
  2. 2. 若槽为空，直接存储元素。
  3. 3. 若发生冲突，采用冲突处理策略插入。
• • 查找（Search）：
  1. 1. 计算关键字的索引。
  2. 2. 在对应槽中查找目标关键字，若链地址法则遍历链表，开放地址法则按探查序列查找。
• • 删除（Delete）：
  1. 1. 查找到目标元素。
  2. 2. 删除元素，链地址法中直接移除链表节点，开放地址法中需标记槽为已删除状态以保证探查序列完整。

3. C++ 实现细节与性能考量

• • 存储结构：
  • • 通常使用固定大小的数组（或动态扩容数组）作为底层存储。
  • • 数组元素为指针或链表头指针，存储实际的键值对。
• • 哈希函数设计：
  • • 对于整数键，常用模运算（key % capacity）。
  • • 对于字符串，常用累加、乘法散列等方法，结合取模保证索引范围。
• • 容量与负载因子：
  • • Hashtable 容量决定哈希表大小，负载因子（元素数量/容量）影响性能。
  • • 负载因子过高时，冲突频率增加，性能下降，通常需要扩容和 rehash 操作。
• • STL 中的实现：
  C++ 标准库的 std::unordered_map 即为高效的哈希表实现，内部采用链地址法，支持动态扩容和高质量哈希函数。

4. Hashtable 与其他数据结构对比

• • Hashtable 提供平均 O(1) 的查找、插入和删除性能，但不保证元素有序。
• • 与平衡二叉搜索树（如红黑树）相比，后者提供 O(logn) 的性能，但支持有序遍历。
• • 选择依据：若需求快速访问且无序，优先选择 hashtable；若需要有序数据或范围查询，选择树结构。
  本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
  （加入我的知识星球，免费获取账号，解锁所有文章。）