哈希表核心概念
什么是哈希?
哈希(Hash),也称为散列,是一种将任意长度的输入数据(通常称为'键'或'关键字')通过特定的数学算法映射为固定长度输出的技术。这个输出值被称为'哈希值'、'散列值'或'哈希码'。哈希的核心目的是快速实现数据的查找、存储和比较,广泛应用于哈希表、密码学、数据校验等领域。
核心术语
一、哈希函数
哈希函数是哈希表的核心组成部分,它的作用是将任意长度的输入数据映射到一个固定长度的输出值。这个输出值通常用于确定该键在哈希表中的存储位置。
1. 哈希函数的核心特点
- 确定性:同一输入必须始终映射到同一个哈希值。
- 压缩性:无论输入数据的长度如何,输出的哈希值长度是固定的。
- 高效性:计算哈希值的过程应快速且易于实现,时间复杂度通常为 O(1) 或 O(k)。
2. 哈希函数的设计目标
- 均匀分布:理想情况下,哈希函数应将不同的键均匀地映射到哈希表的各个位置,避免大量键集中在少数位置(即哈希冲突)。
- 减少冲突:由于输入空间远大于输出空间,哈希冲突无法完全避免,但好的哈希函数能最大限度降低冲突概率。
3. 常见的哈希函数有哪些?
-
直接定址法
- 公式:
H(key) = key或H(key) = a × key + b - 适用场景:关键字的范围较小且连续,可直接作为地址。
- 缺点:若关键字范围很大,会导致空间浪费严重。
- 公式:
-
除法散列法
- 公式:
H(key) = key % m - 本质:利用取余运算的截断特性,把任意整数映射到
[0, m-1]区间。 - 优化策略:优先选质数作为
m,避免m=2^k或10^X导致低位相同的关键字扎堆。
- 公式:
-
乘法散列法
- 公式:
h(key) = ⌊m × (key × A mod 1)⌋ - 特点:对哈希表大小
m的取值相对自由,哈希值分布较均匀。 - 注意:常数
A的选择很关键,通常取黄金分割数相关值。
- 公式:
-
全域散列法
- 思想:从精心设计的哈希函数族中随机选择哈希函数,确保即使对于最坏情况下的输入也能获得良好的平均性能。
- 原理:对于任意两个不同的关键字,哈希值相同的概率不超过
1/m。
二、负载因子
1. 什么是负载因子?
负载因子是衡量哈希表填充程度的指标,直接影响哈希冲突概率和内存利用率。
公式:λ = n / m(n 为元素数量,m 为总容量)。
2. 负载因子的影响
- 越小:哈希冲突概率越低,操作接近 O(1),但内存浪费严重。
- 越大:内存利用率高,但操作时间复杂度可能退化到 O(n)。
3. 超过阈值时的处理 当负载因子超过阈值时,会触发扩容(Resize)。流程包括新建更大的桶数组、重新映射所有元素、释放旧内存。


