直接寻址表

概述

直接寻址表（Direct-Address Table, DAT） 是一种最简单的字典实现方式：用一个大小为全域 $U$ 的数组 $T[\mathrm{0..}m-1]$，直接以关键字 $k$ 作为数组下标来存储和查找元素。它提供了 $O(1)$ 的最坏情况搜索、插入和删除操作，但当全域 $m$ 很大而实际存储的元素 $n$ 很小时，会造成严重的空间浪费。

定义

直接寻址表

设全域 $U=\{0,1,\dots ,m-1\}$，直接寻址表是一个数组 $T[\mathrm{0..}m-1]$，其中每个位置（称为槽位，slot）对应全域中的一个关键字。若关键字 $k$ 的元素存在于动态集合 $S$ 中，则 $T[k]$ 指向该元素；否则 $T[k]=\text{NIL}$。

核心思想

直接寻址的本质是：关键字本身就是地址。不需要任何计算或映射，直接用关键字作为数组索引访问。

伪代码

搜索：

DIRECT-ADDRESS-SEARCH(T, k)
    return T[k]

插入：

DIRECT-ADDRESS-INSERT(T, x)
    T[x.key] = x

删除：

DIRECT-ADDRESS-DELETE(T, x)
    T[x.key] = NIL

核心性质

时间复杂度

操作	最坏情况	说明
搜索	$O(1)$	直接按下标访问数组
插入	$O(1)$	直接按下标写入数组
删除	$O(1)$	直接按下标置 NIL

所有操作均为最坏情况 $O(1)$，这是直接寻址表最大的优势。

空间复杂度

• 空间需求为 $O(m)$，其中 $m=|U|$ 是全域大小。
• 实际存储的元素数量为 $n=|S|$。
• 空间利用率为 $n/m$，当 $n\ll m$ 时，大量槽位空闲，空间浪费严重。

关键限制

• 全域不能太大：如果全域 $U$ 很大（例如 64 位整数，$m=2^{64}$），则不可能分配这么大的数组。
• 关键字必须可枚举：关键字必须是有限全域中可直接用作数组下标的值。
• 不适合稀疏数据：当实际存储的元素远少于全域大小时，空间效率极低。

章节扩展

从直接寻址到散列

直接寻址表的空间问题催生了 散列表 的设计思路：

• 直接寻址表：用关键字 $k$ 直接作为下标 $\Rightarrow$ 需要 $O(m)$ 空间
• 散列表：用散列函数 $h(k)$ 将关键字映射到 $O(m)$ 大小的数组 $\Rightarrow$ 只需要 $O(n)$ 空间（$n$ 为实际元素数）

散列函数 $h:U\to \{0,1,\dots ,m-1\}$ 将较大的全域映射到较小的表，用少量的空间冲突换取极大的空间节省。

与其他字典实现的对比

实现方式	搜索	插入	删除	空间	适用场景
直接寻址表	$O(1)$ 最坏	$O(1)$ 最坏	$O(1)$ 最坏	$O(m)$	全域小、元素密集
散列表	$O(1)$ 期望	$O(1)$ 期望	$O(1)$ 期望	$O(n)$	全域大、元素稀疏
平衡二叉搜索树	$O(\lg n)$ 最坏	$O(\lg n)$ 最坏	$O(\lg n)$ 最坏	$O(n)$	需要有序遍历

参见

• 散列表 —— 直接寻址表的改进，用散列函数解决空间浪费问题
• 散列函数 —— 散列表的核心组件，将关键字映射到槽位
• 链地址法 —— 处理散列冲突的方法之一
• 开放寻址法 —— 处理散列冲突的另一种方法