散列表

一、定义

散列表（Hash Table）是根据关键字直接访问的数据结构。通过散列函数将关键字映射到存储位置：

$$H(key) = 地址$$

二、散列函数

1. 除留余数法

$$H(key) = key \mod p$$

• p 通常取不大于表长的最大素数
• 简单常用

2. 直接定址法

$$H(key) = a \times key + b$$

• 适合关键字连续分布

3. 平方取中法

取关键字平方的中间几位。

4. 折叠法

将关键字分成几部分，相加。

三、冲突处理

1. 开放定址法

线性探测法：

$$H_i = (H(key) + i) \mod m, \quad i = 0, 1, 2, ...$$

冲突时，依次探测下一个位置。

平方探测法：

$$H_i = (H(key) \pm i^2) \mod m, \quad i = 0, 1, 2, ...$$

探测位置：$H, H+1, H-1, H+4, H-4, ...$

要求：m 必须是 $4k+3$ 的素数。

双散列法：

$$H_i = (H_1(key) + i \times H_2(key)) \mod m$$

用第二个散列函数确定探测步长。

2. 链地址法（拉链法）

将散列到同一位置的关键字用链表连接。

[0] → NULL
[1] → [12] → [25] → people...
[2] → [7] → NULL
[3] → NULL
[4] → [18] → [31] → NULL

四、装填因子

$$\alpha = \frac{表中记录数}{表长}$$

• $\alpha$ 越大，冲突越多
• ASL 是 $\alpha$ 的函数

五、查找效率分析

成功 ASL：

$$ASL_{成功} = \frac{\sum 各元素比较次数}{元素个数}$$

失败 ASL：

$$ASL_{失败} = \frac{\sum 各位置探测到空的次数}{表长}$$

期望 ASL：

• 线性探测（成功）：$\approx \frac{1}{2}(1 + \frac{1}{1-\alpha})$
• 线性探测（失败）：$ASL_{失败} = \frac{1}{2}(1 + \frac{1}{(1-\alpha)^2})$
• 链地址法（成功）：$\approx 1 + \frac{\alpha}{2}$

例 1：线性探测法

关键字序列：19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79

散列函数：$H(key) = key \% 13$，表长 $m = 16$

散列表（位置 0~15）：

位置: 0  1   2  3   4   5   6   7   8   9  10  11  12  13  14  15
数据: -  14   1 68  27  55  19  20  84  79  23  11  10   -   -   -

$ASL_{成功}$ = (1+1+1+2+1+1+3+4+3+1+3+9)/12 = $\frac{30}{12} = 2.5$

例 2：链地址法

关键字序列：19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79；散列函数 $H(key) = key \% 13$

[0] → NULL
[1] → [14] → [1] → [27] → [79] → NULL
[2] → NULL
[3] → [68] → [55] → NULL
[4] → NULL
[5] → NULL
[6] → [19] → [84] → NULL
[7] → [20] → NULL
[8] → NULL
[9] → NULL
[10] → [23] → [10] → NULL
[11] → [11] → NULL
[12] → NULL

$ASL_{成功} = (10+3+3+1+3+1)/12 = \frac{21}{12} = 1.75$

例 3：失败 ASL 计算

线性探测法，表长 16，散列函数 $H(key) = key \% 13$。失败 ASL 与装填因子 $\alpha$ 有关，需计算每个位置探测到空的次数。