知识卡片
开地址结构保存槽数组与哨兵
OHTbl有固定槽数positions、有效成员数size、数据地址数组table、删除标记vacated及四个回调h1/h2/match/destroy。探查用两个哈希回调决定位置,判等仅对有效数据调用,销毁只对有效数据按回调清理。
结构图:
classDiagram
class OHTbl {
int positions
void* vacated
int (*h1)(const void* key)
int (*h2)(const void* key)
int (*match)(const void* a, const void* b)
void (*destroy)(void* data)
int size
void** table
}
class OpenAPI["开地址公开函数组(非类型)"] {
ohtbl_init(OHTbl* htbl, int positions, h1, h2, match, destroy) int
ohtbl_destroy(OHTbl* htbl) void
ohtbl_insert(OHTbl* htbl, const void* data) int
ohtbl_remove(OHTbl* htbl, void** data) int
ohtbl_lookup(const OHTbl* htbl, void** data) int
}
OpenAPI ..> OHTbl : 操作槽与计数
init回调参数为字段所示同型指针简写,size入口是宏。table指向独立分配的void*数组;NULL和vacated为保留状态值,因此不能随意把它们当普通数据加入表。
136与02832 ohtbl_init分配positionssizeof(void),失败-1;逐槽赋NULL后令vacated=&静态char对象,保存h1/h2/match/destroy及size=0,成功0。O(m)来自逐槽初始化。代码没有校验positions正值、步长覆盖性或整数溢出,调用条件需保证合法。
141及02831:ohtbl_size(htbl)展开为((htbl)->size),不是遍历数组或结构成员。02832–02835完整实现均已读,size不包含删除标记数;不能用它单独证明实际探查路径很短。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 3 处
- · 查看原书依据
这个结构包含8个成员:positions指明哈希表中分配的槽位数目;指针vacated将被初始化来指向一个特殊的地址空间,来指明这个特殊地址上曾经删除一个元素;h1、h2、match、destroy是打包传入ohtbl_init的函数指针;size指明表中现有元素的数量;table是存储元素的数组。
- · 查看原书依据
初始化vacated,将它指向标志位地址;最后将size值置0。 ohtbl_init的时间复杂度为O(m),其中m是表中槽的个数。这是由于m个指向槽中数据的指针都必须初始化为NULL。而剩下的初始化操作都能在固定时间内完成。
- · 查看原书依据
元素数量的宏定义(见示例8-7)。它通过遍历结构OHTbl的成员来获取元素个数。 其时间复杂度为O(1)。因为遍历过程是一个常量级别运算过程。 示例8-7:开地址哈希表抽象数据类型的实现