知识卡片
直接寻址用键作下标
键域 U={0,…,m−1} 较小时,直接寻址表为每个可能键保留槽位 T[k],空槽记 NIL。
查找、插入、删除都能 O(1),因为键就是下标;代价是空间随整个键域 m 增长,即使实际只存很少元素也要留位。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第11章 散列表 · 查看原书依据
Slot k points to an element in the set with key k.
参考来源
- 位置:《算法导论(第4版)》第 11 章 11.1 节(`OEBPS/chapter011.xhtml`,文本字符 [0, 4500);图 11.1/Art_P378)。
- 结论依据:原文直接定义直接寻址表及三种操作,并在 11.2 节说明稀疏键域的空间缺点。
- 原始内容:Slot k points to an element in the set with key k .