考研笔记

板子：散列表线性探测

★ 级：手算 ASL 是重点，代码认得就行。插入时从 开始往后找第一个空位置；查找时沿同样的路走，碰到空位置就说明不存在。

代码

#define HM 16                                // 表长 m
#define HP 13                                // 散列函数 H(key) = key % p，p 取不大于 m 的质数
#define EMPTY -1                             // 空位置（关键字都是非负数）
int HT[HM];                                  // 散列表
 
void InitHash() {
    for (int i = 0; i < HM; i++) HT[i] = EMPTY;
}
 
bool HashInsert(int key) {                   // 线性探测插入；key 已经存在或表满时返回 false
    int d = key % HP;                        // 散列地址
    for (int i = 0; i < HM; i++) {           // 最多看 m 个位置
        int pos = (d + i) % HM;              // 线性探测：d, d+1, d+2, …，到表尾绕回表头（模的是表长 m）
        if (HT[pos] == EMPTY) {              // 找到空位置：放进去
            HT[pos] = key;
            return true;
        }
        if (HT[pos] == key) return false;    // 已经有了
    }
    return false;                            // 表满
}
 
int HashSearch(int key, int &cnt) {          // 返回 key 所在位置，找不到返回 -1；cnt 带回比较次数
    int d = key % HP;
    cnt = 0;
    for (int i = 0; i < HM; i++) {
        int pos = (d + i) % HM;
        cnt++;                               // 查看一次这个位置，就算一次比较（空位置也算）
        if (HT[pos] == EMPTY) return -1;     // 碰到空位置：key 一定不在表里
        if (HT[pos] == key) return pos;
    }
    return -1;                               // 探遍全表都没找到
}

复杂度：插入、查找的平均比较次数取决于装填因子 ，与 不直接相关；最坏 。

教材例子（上面代码的参数就是按它设的）

关键字 {19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79}，，表长 16，得到：

地址0123456789101112131415
关键字140168275519208479231110
  • 查 84：比较 3 次，在地址 8 找到。查 38：地址 12 不是，地址 13 是空的，比较 2 次，失败。
  • 成功，失败。

关键边界

位置为什么
散列地址模 ，探测模 只会得到 ；探测时往后走，要能走到表尾的 ，所以模表长
碰到空位置就返回失败如果 key 在表里，插入时它会占住这条路上的第一个空位置。所以碰到空位置就说明它不在
空位置也算一次比较按教材口径，「查看这个位置有没有记录」本身算一次比较，所以 cnt++ 放在判断空之前
失败 的分母是 查找只可能从 这 个地址出发，不是除以表长 ，也不是除以

易错点

  • 开放定址法不能直接删除元素：删掉以后会凭空多出一个空位置，截断同义词的查找路径。只能做删除标记（逻辑删除）。
  • 手算 失败：对 每个起点，数到第一个空位置（包含空位置那一次）为止的比较次数，再求平均。见 7.5.4 散列查找及性能分析。

链接

反向链接