知识卡片
链式哈希组合桶数组与策略
本章CHTbl把桶数组与操作策略分开保存:buckets是桶数,size是当前成员总数,table指向List桶数组,h负责散列,match负责判等,destroy负责数据清理。它是拥有自己字段的结构体,不是List的另一个名字。
结构图:
classDiagram
class CHTbl {
int buckets
int (*h)(const void* key)
int (*match)(const void* a, const void* b)
void (*destroy)(void* data)
int size
List* table
}
class List
class HashAPI["链式哈希公开函数组(非类型)"] {
chtbl_init(CHTbl* htbl, int buckets, h, match, destroy) int
chtbl_destroy(CHTbl* htbl) void
chtbl_insert(CHTbl* htbl, const void* data) int
chtbl_remove(CHTbl* htbl, void** data) int
chtbl_lookup(const CHTbl* htbl, void** data) int
}
CHTbl *-- List : table分配为buckets个桶
HashAPI ..> CHTbl : 公开操作
init中的h/match/destroy为图内同型函数指针简写;chtbl_size是字段查询宏,不是结构成员方法。数组拥有各桶结构,桶节点仍只保存应用数据地址,数据清理由回调约定。
125及02814–02815 chtbl_init:malloc(buckets*sizeof(List))失败返回-1;成功后保存buckets,逐桶list_init(…,destroy),再存h/match/destroy、size=0,返回0。初始化O(m)来自m次桶初始化。实际代码未校验buckets为正或乘积溢出,调用条件不能仅凭函数名假定已验证。
130及02813宏chtbl_size(htbl)=((htbl)->size),是字段访问而非遍历,正文“遍历结构的size成员”用语不准确。02814–02817全文件已读,只有成功插入/移除更新size。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 链式哈希组合桶数组与策略
- · chtbl_init
- · chtbl_size
原书出处 · 3 处
- · 查看原书依据
这个结构包含6个成员:buckets指明表中分配的“桶”的个数;h、match和destroy用于封装传入chtbl_init函数的函数;size指明表中现有元素的数量;table是存储“桶”的数组。 示例8-2:链式哈希表抽象数据类型的头文件
- · 查看原书依据
首先为“桶”分配空间;然后调用list_init初始化每个“桶”;接着封装h、match和destroy函数;最后将size值设置为0。 chtbl_init的时间复杂度为O(m),其中m是表中“桶”的个数。这是由于复杂度为O(1)的操作list_init将为每个“桶”执行一次(桶的数量为m)。而剩
- · 查看原书依据
size成员来获取元素个数。 其时间复杂度为O(1),因为访问一个结构的一个成员是一个简单的任务,运行一段固定的时间即可完成。 示例8-3:链式哈希表的实现