1. 散列表核心概念复盘#

散列表（Hash Table）又称哈希表，是根据关键字(key)直接进行访问的数据结构，通过把关键字映射到表中一个位置来访问记录，以加快查找速度，这个映射函数称为散列函数，存放记录的数组称为散列表。考研核心考点：散列表的平均查找长度(ASL)与装填因子$\alpha = \frac{表中记录数n}{散列表长度m}$直接相关，$\alpha$越小，发生冲突的概率越低，平均查找长度越小。

2. 常用散列函数构造方法#

考研高频考点包括：

• 除留余数法：最常用的构造方法，公式为$H(key) = key \% p$，其中$p$应取不大于散列表长度$m$的最大质数，可最大程度减少冲突。
• 直接定址法：$H(key) = a*key + b$，适用于关键字分布连续的场景。
• 数字分析法、平方取中法等，多以选择题形式考察适用场景。

3. 冲突解决方法（考研核心大题考点）#

分为两大类：

1. 开放地址法：
   • 线性探测法：$H_i = (H(key) + i) \% m, i=1,2,...,k(k\leq m-1)$，缺点是会产生“堆积”问题，相同散列地址的关键字越多，查找效率越低。
   • 二次探测法：$H_i = (H(key) \pm i^2) \% m$，避免了线性探测的堆积问题，但不能探测到整个散列表空间。
   • 双散列法：使用第二个散列函数计算增量，进一步减少堆积。
2. 链地址法：将所有关键字为同义词的记录存储在一个单链表中，散列表数组存储每个链表的头指针，是考研最常考察的冲突解决方法，其平均查找长度与装填因子$\alpha$线性相关，且不会产生堆积问题。

4. 平均查找长度计算#

考研常考察不同冲突处理方法下的ASL计算，例如给定关键字序列和散列表长度，计算线性探测法下的成功和不成功平均查找长度，需要重点掌握计算步骤。