知识卡片

结构图卡 · 5654.d.1.a.3.d.10 · 生成模型:未记录

链式哈希组合桶数组与策略

理解等级:中级

本章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 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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:链式哈希表的实现

    参考来源

    - 位置:《算法精解:C语言描述》第8章《链式哈希表的实现与分析》(spine1269;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1236.html;u124-ch08-011)。 - 结论依据:124正文六字段和02812–02813完整chtbl.h实读,与02814初始化实际List数组分配核对;API为自由函数不虚构方法或继承。 - 原始内容:这个结构包含6个成员:buckets指明表中分配的“桶”的个数;h、match和destroy用于封装传入chtbl_init函数的函数;size指明表中现有元素的数量;table是存储“桶”的数组。 示例8-2:链式哈希表抽象数据类型的头文件 - 位置:《算法精解:C语言描述》第8章《chtbl_init》(spine1269;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1236.html;u125-ch08-011)。 - 结论依据:125及02814–02815 chtbl_init:malloc(buckets*sizeof(List))失败返回-1;成功后保存buckets,逐桶list_init(...,destroy),再存h/match/destroy、size=0,返回0。初始化O(m)来自m次桶初始化。实际代码未校验buckets为正或乘积溢出,调用条件不能仅凭函数名假定已验证。 - 原始内容:首先为“桶”分配空间;然后调用list_init初始化每个“桶”;接着封装h、match和destroy函数;最后将size值设置为0。 chtbl_init的时间复杂度为O(m),其中m是表中“桶”的个数。这是由于复杂度为O(1)的操作list_init将为每个“桶”执行一次(桶的数量为m)。而剩 - 位置:《算法精解:C语言描述》第8章《chtbl_size》(spine1274;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1241.html;u130-ch08-011)。 - 结论依据:130及02813宏chtbl_size(htbl)=((htbl)->size),是字段访问而非遍历,正文“遍历结构的size成员”用语不准确。02814–02817全文件已读,只有成功插入/移除更新size。 - 原始内容:size成员来获取元素个数。 其时间复杂度为O(1),因为访问一个结构的一个成员是一个简单的任务,运行一段固定的时间即可完成。 示例8-3:链式哈希表的实现