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

显地提高查找效率。为了继续提高查找的效率，还可以继续分组，比如，分成250组，每组的大小为40：

显然，采用这种定义方式太繁琐了，由于每个数组的大小是相同的，因此可以直接将存储40个学生记录的数组定义为一个类型：

此时，每个分组的大小为40，从而使得查找记录时，最多只需要比较40次。接下来，需要定义分组规则，以通过学号找到该记录属于哪个组。在定义规则时，应尽可能地使所有记录平均地分布在各个组中，不应该出现一些组存储的记录非常多，而一些组存储的记录非常少的情况。但这并不是一件容易的事情，需要对学号的数据分布进行精确的分析。

如果分成250组，假定学号是均匀分布的，则可以将6字节学号数求和除以250（分组数目）所得的余数（取余法）作为分组的索引，由于写入和查找时，都需要通过学号找到该记录应该属于哪个组，因此可以根据学号分组的依据，编写一个通过学号找到对应分组索引的函数，详见程序清单3.62。

程序清单3.62  通过学号分组范例程序

即将分组数为250看作一个大小为250的表格，每个表项可以存储40个学生记录的数组，通过db_id_to_idx()函数找到关键字学号ID对应在该表中的位置。其中，大小为250的表格就是"哈希表"，详见图3.24。db_id_to_idx()函数就是"哈希函数"，哈希函数的结果（分组索引）称之为"哈希值"。

图3.24  哈希表

哈希表的核心工作在于哈希函数的选择，将查找的关键字送给哈希函数产生一个哈希值，哈希函数的选择直接决定了记录的分布，必须尽可能地确保所有记录均匀地分布在各个组中。在上面的示例中，每个分组中都定义了大小相同的数组作为记录存储的空间。如果按照分组规则，能够确保恰好均匀地分布在各个分组中，这是最佳的。

而实际上学生记录是会变动的，可能增加或删除，则很难保证按照现在定义的分组规则，保证100%的完全平均。如果每个分组都使用大小相同的数组作为记录存储的空间，则可能会导致部分数组未存满，部分数组却存不下的情况，就会导致部分学生记录无处可存，造成严重的数据管理问题。

由于数组都是提前定义好大小的，动态性能差，而链表的动态性能更好，可以根据需要增加、删除结点，改变链表长度，因此可以使用链表管理学生记录，就算分布不均匀，也只存在链表长度的差异，不会出现数据存储不了的问题，其示意图详见图3.25。

图3.25  链式哈希表

当使用链表管理学生记录时，哈希表每个表项的实际内容就是该组链表的表头。链表头结点的类型slist_head_t（slist.h）的定义如下：

基于此，在哈希表的每个表项中存储一个slist_head_t类型的链表头结点即可，哈希表的定义如下：

根据对链式哈希表结构的分析，编写一个基于链式哈希表的信息管理系统，作为示例仅提供增加、删除、查找三种功能。当然，在使用这些功能前，还必须定义一个哈希表对象的类型，以便使用该类型定义具体的哈希表实例，进而使用各个功能接口对该实例进行操作。

>>> 3.5.2 哈希表的类型

哈希表类型struct _hash_db定义如下：

在结构体中，需要包含哪些哈希表的相关信息呢？链式哈希表的核心是一个slist_head_t类型的数组，其大小与分组数目相关。为了通用，分组数目应由用户根据实际情况确定。slist_head_t类型的数组信息由一个指向数组首地址的slist_head_t*类型的指针和一个指定数组大小的size构成，哈希表结构体类型的定义如下：

在实际的应用中，信息可以是任意数据类型（void *），其次还需要知道该void *指针指向的记录的长度，比如，学生记录的长度是sizeof(student_t)，因此更新哈希表结构体类型的定义如下：

在存储或查找记录时，可以通过与关键字（比如，学号ID）比较找到哈希表中的索引值，然后在对应的表项中添加或查找记录。在存储记录时，需要提供关键字和记录；而在查找记录时，仅需提供关键字。由此可见，关键字和记录是两个不同的概念，关键字具有特殊的作用，因此关键字和记录应该分别对待。对于学生信息管理系统来说，其关键字为学号，长度是6字节，记录包含姓名、性别、身高、体重等信息。因此，在学生记录结构体的定义中，将关键字ID分离出来。学生记录的定义如下：

同理，关键字的长度也是由用户决定的，在存储一条记录时，需要分配内存存储关键字，以便查询时读取该关键字与查询使用的关键字进行比较。因此在哈希表的结构体类型中，需要包含关键字长度信息，更新哈希表结构体类型的定义如下：

特别地，在前面