🎲哈希表
系统提供一个全局的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，以及又是全局唯一的，所以不建议使用它。
网友评论