哈希表查找

定义与基本思想

哈希表查找（Hash Table Search）是一种通过哈希函数将关键字映射到表中某个位置进行查找的方法。其核心思想是“以空间换时间”，查找效率极高。

适用场景

• 适用于查找频繁、数据量较大的场合
• 适用于对查找效率要求极高的应用

算法描述

1. 设计合适的哈希函数 $H(x)$，将关键字 $x$ 映射到哈希表的某个位置
2. 若该位置为空，则查找失败
3. 若该位置存有元素，比较关键字是否相等
4. 若冲突，采用冲突处理方法（如开放定址法、链地址法）

伪代码如下：

pos = H(x)
if table[pos] == null:
    return -1
elif table[pos].key == x:
    return pos
else:
    // 冲突处理（如线性探测、链表查找等）
    ...

哈希函数的构造方法

• 除留余数法：$H(key) = key \bmod p$，p 取不大于表长 m 的最大素数，分布最均匀，最常用
• 直接定址法：$H(key) = a \times key + b$，适合关键字分布连续
• 数字分析法：取关键字中分布较均匀的若干位
• 平方取中法：取关键字平方的中间几位
• 折叠法：将关键字分割成若干段再相加

冲突处理方法

开放定址法

发生冲突时，在哈希表内寻找下一个空位。

• 线性探测：$H_i = (H(key) + i) \bmod m$，容易产生”堆积”
• 平方探测：$H_i = (H(key) + i^2) \bmod m$，可避免堆积

链地址法

把哈希到同一位置的所有元素挂在同一条链表上。查找时先定位链表，再在链表中顺序查找。

#define M 13  // 哈希表长（取素数）

typedef struct Node {
    int key;
    struct Node *next;
} Node;

// 哈希函数：除留余数法
int H(int key) {
    return key % M;
}

// 链地址法查找
Node *HashSearch(Node *hashtable[], int key) {
    int pos = H(key);
    Node *p = hashtable[pos];
    while (p != NULL && p->key != key)
        p = p->next;          // 在链表中顺序查找
    return p;                 // 返回找到的结点或 NULL
}

// 链地址法插入
void HashInsert(Node *hashtable[], int key) {
    int pos = H(key);
    Node *s = (Node *)malloc(sizeof(Node));
    s->key = key;
    s->next = hashtable[pos];  // 头插法
    hashtable[pos] = s;
}

装填因子与性能分析

装填因子 $\alpha = \frac{\text{表中元素个数}}{\text{表长}}$，它直接影响查找性能。

• $\alpha$ 越大，冲突越多，查找效率越低
• 链地址法的平均查找长度：$ASL_{成功} \approx 1 + \frac{\alpha}{2}$
• 线性探测的平均查找长度：$ASL_{成功} \approx \frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right)$
• 工程实践中通常控制 $\alpha$ 在 0.7~0.8 以下

时间复杂度分析

• 理想情况下：$O(1)$
• 最坏情况下（大量冲突）：$O(n)$
• 实际应用中，查找效率接近 $O(1)$

习题

习题 1

哈希表查找的基本思想是什么？常见的冲突处理方法有哪些？

习题 2

哈希表查找的平均时间复杂度是多少？在什么情况下会退化为 $O(n)$？

习题 3

哈希表查找的查找过程包括哪两步？常见的冲突处理方法有哪些？