概述
哈希表(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。
- 缺点:遍历开销大,额外指针空间开销。


