14.4.4 哈希散列表

哈希表试图跳过“逐个比较”的过程，用关键字通过散列函数直接计算存储地址。理想情况下，查找时间接近 $O(1)$；真正的难点在于冲突处理。

核心概念

概念	含义
散列函数	把关键字映射为存储地址的函数
散列表	按散列地址组织的数据表
冲突	不同关键字映射到同一地址
装填因子	表中已存元素数与表长的比值

装填因子越大，冲突概率通常越高。

常见散列函数

方法	思想
直接定址法	关键字本身或线性函数作为地址
除留余数法	H(key)=key mod p
数字分析法	选关键字中分布较均匀的若干位
平方取中法	平方后取中间若干位

软考中最常见的是除留余数法。

冲突处理

方法	思想	特点
开放定址法	冲突后在表内寻找下一个空位	可能产生聚集
线性探测	依次尝试下一个位置	简单但易堆积
二次探测	按平方步长探测	缓解一次聚集
链地址法	同一地址的元素挂链表	装填因子可大于 1，常用

与二分查找的取舍

方法	优势	代价
二分查找	有序表中查找稳定，支持范围相关判断	维护有序成本高，$O(\log n)$
哈希查找	等值查找很快，理想 $O(1)$	冲突、扩容、散列函数设计复杂，不擅长范围查询

哈希表不是“所有查找都最优”，它特别适合等值查找。

本节例题

单选

哈希表中的“冲突”指的是：

A不同关键字映射到同一散列地址B关键字全部有序C查找失败D表中没有空位

自查清单

1. 能否解释哈希查找为什么理想情况下接近 $O(1)$？
2. 能否说明装填因子与冲突概率的关系？
3. 能否区分开放定址法和链地址法？