除留余数法#

408 考研中最常考的哈希函数是除留余数法：

1
H(key) = key % p

其中 p 取不大于表长的最大素数（或质数），这样可以使关键字的分布更均匀，减少冲突。例如表长 m = 15，则取 p = 13。

装填因子#

装填因子（Load Factor）α = n / m，其中 n 为表中元素个数，m 为表长。

• α 越大，表越满，冲突概率越高，查找效率越低
• 拉链法 α 可以大于 1；开放定址法 α 必须小于 1
• 一般建议 α ≤ 0.75

冲突与同义词#

• 冲突：key₁ ≠ key₂，但 H(key₁) = H(key₂)
• 同义词：发生冲突的多个关键字互称同义词

冲突不可避免（鸽巢原理），关键是如何有效处理冲突。

原理#

每个哈希槽位维护一个链表，所有哈希值相同的元素挂在同一链表上：

1
下标:  0       1       2       ...     p-1
2
槽位: [头指针] [头指针] [头指针] ...    [头指针]
3
       ↓       ↓       ↓              ↓
4
      链表    链表    链表            链表

查找与插入#

1
// 拉链法查找
2
Node* search(HashTable ht, int key) {
3
    int idx = key % MAX_SIZE;
4
    Node *p = ht[idx].head;
5
    while (p != NULL) {
6
        if (p->key == key) return p;
7
        p = p->next;
8
    }
9
    return NULL;
10
}

插入采用头插法，删除可直接在链表中摘除结点——这是拉链法相比开放定址法的一大优势（开放定址法只能逻辑删除）。

ASL 分析#

计算示例：哈希函数 H(key) = key % 13，依次插入关键字 {16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77}，表长 m = 13。

H(16) = H(29) = 3，H(90) = H(77) = 12，分别产生冲突挂在同一链表上。

• ASL 成功 = 各元素比较次数之和 / 11（按实际链表位置计算）
• ASL 失败 = 各槽位链表长度之和 / 13

易错：拉链法失败 ASL 的分母是表长 m（所有可能的哈希地址数），不是元素个数 n。如果哈希函数模 p 且 p < m，分母应取 p（只有 0~p-1 是合法地址）。

通用公式#

1
H_i = (H(key) + d_i) % m,  i = 1, 2, 3, ...

其中 d_i 是第 i 次探测的增量，不同的取法对应不同的探测方法。

三种探测方法#

线性探测法详解#

1
// 线性探测法查找
2
int linearSearch(HashTable *ht, int key) {
3
    int pos = key % ht->size;
4
    int i = 0;
5
    while (i < ht->size) {
6
        int cur = (pos + i) % ht->size;
7
        if (ht->data[cur] == EMPTY)  return -1;  // 遇到空位，失败
8
        if (ht->data[cur] == key)    return cur;  // 成功
9
        i++;
10
    }
11
    return -1;
12
}

堆积（Clustering）：线性探测法的最大缺陷。同义词和非同义词都可能争夺同一段连续区域，导致大量元素聚集，探测次数急剧增加。

易错：线性探测的堆积是非同义词也会聚集（一次聚集），二次探测的聚集是仅同义词聚集（二次聚集）。

删除问题#

开放定址法不能直接删除元素。如果直接将位置置空，会导致后续探测到此位置时误认为查找失败，中断探测链。

解决方案：使用墓碑标记（Tombstone / 懒删除）——将被删除位置标记为 DELETED 状态，查找时跳过，插入时可复用。

ASL 计算示例#

m = 11，H(key) = key % 11，依次插入 19, 1, 23, 14, 55：

1
下标:  0   1   2   3   4   5   6   7   8   9   10
2
元素:  55  1   23  14  -   -   -   -   19  -   -

查找成功 ASL = (1 + 1 + 2 + 1 + 1) / 5 = 6/5 = 1.2

查找失败 ASL：对每个哈希地址（0~10），探测到空位所需的比较次数求平均。

ASL 失败 = (5+4+3+2+1+1+1+1+2+1+1) / 11 = 22/11 = 2.0

易错：查找失败 ASL 的分母是表长 m（所有可能的哈希地址数），不是元素个数 n。如果 H(key) = key % p 且 m != p，分母应取 p。408 真题中 m 和 p 经常不同，这是最常见的丢分点。