概述
哈希表（Hash Table）是一种通过哈希函数将关键字映射到存储位置的数据结构，旨在实现快速查找、插入和删除操作。本文介绍哈希表的核心概念、冲突处理策略及 C++ 实现。
一、哈希函数
1. 核心特点
- 确定性：同一输入始终映射到同一个哈希值。
- 压缩性：任意长度输入映射为固定长度输出。
- 高效性：计算过程时间复杂度通常为 O(1) 或 O(k)。
2. 设计目标
- 均匀分布：减少哈希冲突，保证操作效率接近 O(1)。
- 减少冲突：降低不同键映射到同一地址的概率。
3. 常见哈希函数
直接定址法
公式：H(key) = key 或 H(key) = a × key + b
适用于关键字范围较小且连续的场景。
除法散列法
公式：H(key) = key % m
- 优点：实现简单，适用性广。
- 缺点：m 选取不当易导致冲突。建议 m 取质数，避免 2 的幂次。
乘法散列法
公式：h(key) = ⌊m × (key × A mod 1)⌋
其中 A 为 (0,1) 之间的常数（如黄金分割数）。对 m 取值限制较少，分布较均匀。
全域散列法
从哈希函数族中随机选择函数，确保最坏情况下平均性能良好。
二、负载因子
1. 定义
负载因子 λ = n / m，其中 n 为元素数量，m 为哈希表容量。
2. 影响
- λ 越小：冲突概率低，但空间浪费大。
- λ 越大：冲突概率高，性能退化至 O(n)，但空间利用率高。
3. 扩容机制
当负载因子超过阈值（如 0.7）时触发扩容，通常新建更大容量的桶数组并重新映射所有元素。
三、哈希冲突
指不同关键字映射到相同哈希地址的情况。由于输入空间远大于输出空间，冲突无法完全避免。
四、冲突处理
方法一：开放定址法
所有元素存储在数组本身中，通过探测序列寻找空闲槽位。
- 线性探测：
h_i(key) = (h(key) + i) % m。易产生聚集现象。 - 二次探测：
h_i(key) = (h(key) + c1*i + c2*i²) % m。减少聚集，但不能探测所有位置。 - 双重散列：
h_i(key) = (h1(key) + i*h2(key)) % m。探测序列更均匀，需满足 h2(key) 与 m 互质。
方法二：链地址法
使用数组 + 链表组合。每个桶对应一个链表，冲突元素链在一起。
- 优点：冲突处理简单，无聚集问题，负载因子可大于 1。
- 缺点：遍历开销大，额外指针空间开销。
