算法与数据结构——哈希表

的分析中，哈希表最重要的一个概念就是"哈希函数"，哈希函数的作用是通过关键字（如学号ID）得到其对应记录在哈希表中的索引值，哈希函数要尽可能确保记录均分地分布在哈希表的各个表项中。对于不同的数据，用户可能选择不同的哈希函数，因此哈希函数应该由用户指定。基于此，在哈希表结构体中新增一个函数指针，用于指向用户自定义的哈希函数。完整的哈希表结构体类型定义如下（hash_db.h）：

在使用哈希表的各个接口函数前，首先需要使用该类型定义一个哈希表实例：

如果系统中需要使用多张哈希表，则只需要使用该类型定义多个哈希表实例即可：

>>>  3.5.3 哈希表的实现

1、初始化

hash_db_init()接口用于哈希表实例的初始化，在定义哈希表结构体类型时，哈希表数组大小、记录长度、关键字长度和哈希函数都需要由用户根据实际情况确定，其函数原型定义如下（hash_db.h）：

在这里，以学生记录为例，创建一个大小为250组的哈希表：

在初始化函数的实现中，需要按照size指定的大小分配内存，用于存储哈希表的各个表项（链表头），接着需要完成各个链表头和结构体成员的初始化，初始化函数的实现范例详见程序清单3.63。

程序清单3.63  初始化函数范例程序

2、添加记录

hash_db_add()接口用于向已经初始化的哈希表中添加一条记录，添加一条记录时，需要指定关键字信息和记录值信息，其函数原型定义（hash_db.h）：

其中，p_hash为指向哈希表实例的指针，key为指向关键字的指针，value为指向记录值的指针。特别地，由于在添加记录时，程序不会修改key和value指针所指向的值，因此，指针都加了const修饰符。以添加一条学生记录为例，使用范例如下：

在添加记录函数的实现中，首先需要使用哈希函数找到关键字对应的记录在哈希表中的索引，以确定该条记录所在链表的表头，然后分配一个存储记录的结点空间，将关键字、记录等信息存储在该空间中，然后将结点添加到对应链表的头部（由于记录在链表中的具体位置不重要，因此直接添加在链表头部，效率更高）。函数实现的范例详见程序清单3.64。

程序清单3.64  添加记录函数范例程序

程序分配了一个结点的空间，该结点的空间需要存储一个slist_node_t类型链表结点，便于添加结点到链表中，存储长度为p_hash->key_len的关键字，存储长度为p_hash->value_len的记录值，详见图3.26，其内存的大小为：

图3.26  结点存储空间分布

由于结点空间的首部用于存储结点slist_node_t的值以组织链表。因此需要将结点添加到链表中时，直接将p_mem转换为slist_node_t*类型使用即可，通用链式哈希表的结构示意图详见图3.27。

图3.27  通用的链式哈希表结构示意图

与图3.25中管理学生记录的链式哈希表结构示意图对比发现，它们表达的含义是完全一致的，仅仅是具体类型变为了更加通用的void *类型。

3、查找记录

hash_db_search()接口通过关键字查找与之对应的记录，查找记录时，需要指定关键字信息，同时还需要使用一个指向记录的指针获取查找到的记录值，其函数原型（hash_db.h）如下：

虽然参数与添加记录是完全一样的，但value表示的含义却不一样，此处的value是输出参数，用于得到查找到的记录值。而添加记录函数中的value是输入参数，提供需要存储的记录值。由于此处的value指向指向的值是需要被改变的（改变为查找到的记录值），因此，其不能增加const修饰符。以查找ID为201444700239的学生记录为例，使用范例如下：

在该函数的实现中，首先需要使用哈希函数找到关键字对应的记录在哈希表中的索引，以确定该条记录所在链表的表头，然后遍历链表的各个结点，将提供的关键字与结点中存储的关键字比对，直到找到关键字完全一致的记录（查找成功）或链表遍历结束（查找失败）。找到该记录对应的结点后，将结点中存储的value值拷贝到参数value指针指向的空间中即可。函数实现的范例详见程序清单3.65。

程序清单3.65  查找记录函数范例程序

程序中，由于查找结点时需要遍历链表，关键字比对的操作需要在遍历函数的回调函数中完成，因此，需要将用户查找记录使用的关键字信息（关键字及其长度）提供给回调函数，同时，当查找到记录时，需要将查找到的结点反馈给调用遍历函数的主程序。为此，定义了一个内部使用的用于寻找一个结点的上下文结构体：

调用遍历函数时，需要提供一个设置好关键字信息的结构体作为回调函数