上一篇: iOS 标准库中常用数据结构和算法之二叉排序树
哈希表
系统提供一个全局的 key 为字符串的哈希表. 并提供哈希表的创建, 元素添加, 元素查找, 哈希表的销毁的能力. 存储在哈希表中的元素是一个如下的标准结构:
- // 哈希表元素实体结构定义
- typedef struct entry {
- char *key; // 哈希表中的 key, 必须是字符串
- void *data; // 哈希表中的值, 是一个指针类型, 其内容可以任意.
- } ENTRY;
哈希表的创建和销毁
功能: 用于全局哈希表的创建和销毁操作.
头文件:#include <search.h>
平台: BSD Unix
函数签名:
- // 创建一个哈希表
- int hcreate(size_t nel);
- // 销毁一个哈希表
- void hdestroy(void);
参数:
nel: [in] 指定哈希表的初始容量尺寸, 这个参数主要用于内存存储上的优化处理.
return:[out] 如果哈希表创建成功则返回 0, 否则返回非 0.
描述:
系统提供了一个全局的哈希表, 因此这也是一个非常重要的缺点, 因为我们无法知道其他函数是否也正在使用这个哈希表. 因此在特定时刻只有一个哈希表是有效的. 个人的感觉是这就是一个非常不合理的哈希表实现.
哈希表元素的添加和查询.
功能: 用于哈希表元素的添加和查询.
头文件:#include <search.h>
平台: BSD Unix
函数签名:
ENTRY * hsearch(ENTRY item, ACTION action);
参数:
item:[in] 要进行查询或者添加的条目, 这是一个 ENTRY 类型的数据. 如果我们只是查询则只需要设置 ENTRY 中的 key 部分的值, 而如果是添加则需要设置完整的 key 和 data 的值.
action:[in] 指定要对哈希表执行的动作, 这个类型是一个 ACTION 类型的枚举值, 其定义如下:
- typedef enum {
- FIND, ENTER
- } ACTION;
当值设置为 FIND 时则只进行查找处理.
当值设置为 ENTER 是就先进行查找, 如果不存在时就进行添加处理.
return:[out] 返回查找或者添加时在哈希表中的实体元素的指针. 如果没有查找到或者添加失败则返回 NULL. 我们不需要对返回的 ENTRY 指针进行内存释放处理, 而是由系统来完成.
描述:
对哈希表执行 ENTER 动作时, 如果找到了则直接返回以前曾经插入到哈希表中的条目, 如果没有找到则会在哈希表中创建一个新的条目, 并返回新条目的指针. 这里需要注意的是在执行插入时要求 ENTRY 结构体中的 key 部分的内存必须要用 malloc 进行分配, 因为哈希表在销毁时会对所有哈希表中的元素的 key 部分调用 free 处理. 也就是说对于哈希表的插入来说 key 的内存我们负责分配, 而由系统负责销毁. 这里也存在一个 BUG 就是当我们对一个在哈希表中已经存在的 key 再次调用 hsearch 时会返回对应的 ENTRY 指针. 但是我们无法得知这个返回值到底是新创建的还是已经存在的. 而我们的 key 又是通过 malloc 分配出来的内存数据, 因此就无法确定我们是否需要去释放这部分已经分配出来的 key 的内存.
示例代码:
- void main()
- {
- // 创建
- if (hcreate(10) != 0)
- {
- // 插入
- ENTRY ent;
- ent.key = malloc(4); // 对于插入处理必须用 malloc 进行内存分配, 而且我们不需要去释放它.
- ent.data = (int*)10; // 这里值保存着整数类型.
- strcpy(ent.key, "Bob");
- ENTRY *p1 = hsearch(ent, ENTER);
- NSAssert(strcmp(p1->key, "Bob")==0, @"oops!");
- ent.key = malloc(6);
- ent.data = (int*)20;
- strcpy(ent.key, "Alice");
- ENTRY *p2 = hsearch(ent, ENTER);
- // 查找
- ENTRY *p3 = hsearch(ent, FIND);
- NSAssert(p3 == p2);
- // 销毁
- hdestroy();
- }
- }
由于这个哈希表的实现对插入重复元素时存在着 BUG, 以及又是全局唯一的, 所以不建议使用它.
来源: http://www.jianshu.com/p/3f80d958879a