【数据结构与算法】哈希表设计（C\C++）

实践要求

1. 问题描述

针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查找程序。

2. 基本要求

假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造。用伪随机探测再散列法处理冲突。

3. 测试数据

取读者周围较熟悉的30个人的姓名拼音。

4. 实现提示

如果随机函数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过度20个字符。字符的取码方法可直接利用PASCAL语言中的ord函数。可先对过长的人名作折叠处理。

5. 选作内容

1. 从教科书上介绍的几种哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较它们的地址冲突率(可以用更大的名字集合作试验)。
2. 研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。
3. 在哈希函数确定的前题下尝试各种不同处理冲突的方法，考查平均查找长度的变化和造好的哈希表中关键字的聚簇性。

实践报告

1. 题目分析

说明程序设计的任务，强调的是程序要做什么，此外列出各成员分工

程序设计任务：
针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查找程序。假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造。用伪随机探测再散列法处理冲突。

2. 数据结构设计

说明程序用到的数据结构的定义，主程序的流程及各模块之间的层次关系

该程序主要用到的数据结构是自定义的哈希表，该数据结构包含以下成员：

1. Person: 人名节点结构体，包含一个 name 字符数组用于存储人名。

2. HashTable: 哈希表结构体，包含以下成员：

   成员名称	解释
   data	一个 Person 类型的指针，用于存储哈希表中的数据。
   flags	一个整数数组，用于标记哈希表中的位置是否为空。当一个位置有 人名时，对应位置的标记为1；否则，标记为0。
   size	哈希表的大小，表示哈希表可以容纳的最大元素数量。

主程序流程图

3. 程序设计

实现概要设计中的数据类型，对主程序、模块及主要操作写出伪代码，画出函数的调用关系

各模块伪代码

初始化哈希表

// 初始化哈希表void initHashTable(HashTable *table, int size){// 为哈希表分配空间// 为标记数组分配空间// 设置哈希表的大小for (int i = 0; i < size; i++){// 初始化人名为空// 初始化标记数组为0}}

除留余数法

// 哈希函数：除留余数法int hashFunction(char *name, int size){int sum = 0;for (int i = 0; i < strlen(name); i++){// 将人名中每个字符的ASCII码相加}return sum % size;}

插入人名到哈希表中

// 插入人名到哈希表中void insertName(HashTable *table, char *name){// 计算人名在哈希表中的位置int i = 0;// 记录发生冲突的次数while // 人名发生冲突{// 发生冲突时，使用伪随机探测再散列法处理}// 将人名填入哈希表中// 标记数组中的位置为1，表示该位置已经有人名}

查找人名在哈希表中

// 查找人名在哈希表中的位置int findName(HashTable *table, char *name){// 计算人名在哈希表中的位置int i = 0;while // 人名发生冲突{if// 比较人名是否相同{return index; // 找到了人名，返回索引位置}// 发生冲突时，使用伪随机探测再散列法处理}return NOT_FOUND; // 未找到人名}

各函数层次关系图

4. 调试分析

程序复杂度分析

1. 空间复杂度
时间复杂度：

1. 初始化哈希表时间复杂度为$$O(size)$$
   注：其中 size 是哈希表的大小。
2. 插入人名到哈希表中的时间复杂度
   $$平均情况下O(1)，最坏情况下为O(size)$$
   这是因为哈希函数的散列操作通常具有 O(1) 的复杂度，但在发生冲突时可能需要执行一系列探测再散列操作，导致最坏情况下的复杂度为 O(size)。
3. 查找人名在哈希表中的位置的时间复杂度
   $$平均情况下为O(1)，最坏情况下为O(size)$$
   与插入操作类似，平均情况下的复杂度是常数级别，但最坏情况下需要遍历整个哈希表才能找到人名或确定其不存在。

2. 时间复杂度
$$O(size)$$
哈希表数据和标记数组：O(size)，其中 size 是哈希表的大小。哈希表数据占用的空间是 O(size)，标记数组占用的空间也是 O(size)。

心得体会

使用链表要注意不能使用空指针，不能使用指向未知内存的指针，以及用完指针后要及时释放。否则就会碰到一些莫名其妙的错误。

5. 测试结果

列出测试结果，包括输入和输出

测试结果

测试结果说明：
输入姓名集里面的姓名，
将会输出该姓名在哈希表中的位置。

input

chenxinxin

output

Found at index 47

6. 用户使用说明

给出主界面及主要功能界面

使用说明

用户运行程序后系统会自动打印各个姓名插入到哈希表中冲突的次数，随后可以输入姓名集合里面的的一个姓名，系统会输出其在哈希表中的位置。
注：姓名集是在源文件中一直写进去的，而不是txt或者文档读入的，故若想修改姓名集合，则需要重写main函数里面的数组。

7. 选作内容

实现了(1),(2),(3)

7.1 (1)的实现

从教科书上介绍的几种哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较它们的地址冲突率(可以用更大的名字集合作试验)。

解：将书本上的平方去中法与上述的除留取余法进行地址冲突比较，发现平方去中法的冲突率非常高，达到了31.22%。

除留余数法

除留余数法
总冲突次数:12
平均冲突次数:0.4
冲突率:0.013333

平方取中法

7.2 (2)的实现

研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。

解：根据以下名字集合，总结了三个特点，针对这三个特点实现了一个自定义哈希函数。

//名字集合"chencaiyi", "chenxinxin", "fangsongjie", "huangjiawei", "huangjunlin", "leiyang","luwei", "wangzhanqi", "wuweidong", "longjiajing", "huangweiqin", "chenshangming", "huangtao","maixupeng", "chenying", "liujunhui", "chenqingdong", "guoziming", "chenyilong", "libaiyang", "liangdeguang","zhangyuxing", "huangyibin", "liuwenlong", "zengzihao", "wangshulian", "zhuzixian", "lidingkun", "caofu", "yuemingju"

1. 大多数名字遵循“姓+名”或“姓+中间名+名字”的模式。
2. 有些名字有重复的字符，如chencaiyi,chenxinxni,huangjunlin。
3. 名称的长度各不相同，从 5 到 12 个字符不等。

因此设计了一个自定义哈希函数，函数如下

// 哈希函数：自定义哈希函数int hashFunction(char *name, int size){int hash = 0;int nameLength = strlen(name);for (int i = 0; i < nameLength; i++){hash = (hash * 31 + name[i]) % size;}return hash;}

7.3 (3)的实现

在哈希函数确定的前题下尝试各种不同处理冲突的方法，考查平均查找长度的变化和造好的哈希表中关键字的聚簇性。

解：在确定使用（2）所说的自定义哈希函数后，将采用单独链接法来处理冲突的情况。

单独链接法：在此方法中，哈希表中的每个插槽都包含一个链表或其他数据结构，用于存储散列到同一索引的多个元素。发生冲突时，新元素将添加到该索引处的链接列表中。要搜索元素，请在相应的索引处遍历链表，直到找到匹配项。

下面是改动最大的函数findName。

// 查找人名在哈希表中的位置int findName(HashTable *table, char *name){int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置// 遍历链表查找人名PersonNode *currentNode = table->data[index];while (currentNode != NULL){if (strcmp(currentNode->name, name) == 0){return index; // 找到了人名，返回索引位置}currentNode = currentNode->next;}return NOT_FOUND; // 未找到人名}

8. 附录

附录说明：
一共有四个.cpp文件，分别为HashMap.cpp、HashMap(1).cpp、HashMap(2).cpp、HashMap(3).cpp 。

源程序文件清单:
HashMap.cpp ：使用求留取余法的哈希表。
HashMap(1).cpp ：使用平方取中法的哈希表。
HashMap(2).cpp ：使用自定义哈希方法来改善求留取余法的哈希表。
HashMap(3).cpp ：使用单链接法来处理冲突情况来改善HashMap(2).cpp中的程序。

9. 全部代码

HashMap.cpp

/* * @Author: hiddenSharp429 z404878860@163.com * @Date: 2023-06-13 16:38:25 * @LastEditors: hiddenSharp429 z404878860@163.com * @LastEditTime: 2023-06-14 17:28:58 * @FilePath: \appe:\C OR C++\code\HashMap.cpp * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE */#include #include #include #define HashTABLE_SIZE 61// 哈希表的大小，选择一个较大的素数#define MAX_NAME_LENGTH 20 // 人名的最大长度#define NOT_FOUND -1 // 未找到的标志typedef struct{char name[MAX_NAME_LENGTH]; // 人名} Person;typedef struct{Person *data; // 哈希表的数据int *flags; // 标记哈希表中的位置是否为空int size; // 哈希表的大小} HashTable;// 哈希函数：除留余数法int hashFunction(char *name, int size){int sum = 0;for (int i = 0; i < strlen(name); i++){sum += name[i]; // 将人名中每个字符的ASCII码相加}return sum % size;}// 初始化哈希表void initHashTable(HashTable *table, int size){table->data = (Person *)malloc(sizeof(Person) * size); // 为哈希表分配空间table->flags = (int *)malloc(sizeof(int) * size);// 为标记数组分配空间table->size = size;// 设置哈希表的大小for (int i = 0; i < size; i++){strcpy(table->data[i].name, ""); // 初始化人名为空table->flags[i] = 0; // 初始化标记数组为0}}// 插入人名到哈希表中void insertName(HashTable *table, char *name){int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置int i = 0;int conflicts = 0; // 记录发生冲突的次数while (table->flags[index] == 1) // 人名发生冲突{// 发生冲突时，使用伪随机探测再散列法处理i++;index = (index + i * i) % table->size;conflicts++;}strcpy(table->data[index].name, name); // 将人名填入哈希表中table->flags[index] = 1; // 标记数组中的位置为1，表示该位置已经有人名printf("Inserted %s with %d conflicts.\n", name, conflicts);}// 查找人名在哈希表中的位置int findName(HashTable *table, char *name){int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置int i = 0;while (table->flags[index] != 0) // 人名发生冲突{if (strcmp(table->data[index].name, name) == 0) // 比较人名是否相同{return index; // 找到了人名，返回索引位置}i++;index = (index + i * i) % table->size; // 发生冲突时，使用伪随机探测再散列法处理}return NOT_FOUND; // 未找到人名}int main(){HashTable table;initHashTable(&table, HashTABLE_SIZE); // 初始化哈希表// 待填入哈希表的人名char names[30][MAX_NAME_LENGTH] = {"chencaiyi", "chenxinxin", "fangsongjie", "huangjiawei", "huangjunlin", "leiyang","luwei", "wangzhanqi", "wuweidong", "longjiajing", "huangweiqin", "chenshangming", "huangtao","maixupeng", "chenying", "liujunhui", "chenqingdong", "guoziming", "chenyilong", "libaiyang", "liangdeguang","zhangyuxing", "huangyibin", "liuwenlong", "zengzihao", "wangshulian", "zhuzixian", "lidingkun", "caofu", "yuemingju"};// 建立哈希表for (int i = 0; i < 30; i++){insertName(&table, names[i]);}// 查找程序char searchName[MAX_NAME_LENGTH];printf("Enter a name to search: "); // 输入要查找的人名scanf("%s", searchName);// 读取人名int index = findName(&table, searchName); // 查找人名在哈希表中的位置if (index != NOT_FOUND) // 找到了人名{printf("Found at index %d\n", index);}else // 未找到人名{printf("Not found\n");}return 0;}

HashMap(1).cpp

/* * @Author: hiddenSharp429 z404878860@163.com * @Date: 2023-06-14 17:27:57 * @LastEditors: hiddenSharp429 z404878860@163.com * @LastEditTime: 2023-06-14 17:28:14 * @FilePath: \appe:\C OR C++\code\HashMap(1).cpp * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE */#include #include #include #define HashTABLE_SIZE 61// 哈希表的大小，选择一个较大的素数#define MAX_NAME_LENGTH 20 // 人名的最大长度#define NOT_FOUND -1 // 未找到的标志typedef struct{char name[MAX_NAME_LENGTH]; // 人名} Person;typedef struct{Person *data; // 哈希表的数据int *flags; // 标记哈希表中的位置是否为空int size; // 哈希表的大小} HashTable;// 哈希函数：平方取中法int hashFunction(char *name, int size){int nameLength = strlen(name);int square = nameLength * nameLength;int midDigits = (square / 100) % 100; // 取中间两位数return midDigits % size;}// 初始化哈希表void initHashTable(HashTable *table, int size){table->data = (Person *)malloc(sizeof(Person) * size); // 为哈希表分配空间table->flags = (int *)malloc(sizeof(int) * size);// 为标记数组分配空间table->size = size;// 设置哈希表的大小for (int i = 0; i < size; i++){strcpy(table->data[i].name, ""); // 初始化人名为空table->flags[i] = 0; // 初始化标记数组为0}}// 插入人名到哈希表中void insertName(HashTable *table, char *name){int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置int i = 0;int conflicts = 0; // 记录发生冲突的次数while (table->flags[index] == 1) // 人名发生冲突{// 发生冲突时，使用平方探测再散列法处理i++;index = (index + i * i) % table->size;conflicts++;}strcpy(table->data[index].name, name); // 将人名填入哈希表中table->flags[index] = 1; // 标记数组中的位置为1，表示该位置已经有人名printf("Inserted %s with %d conflicts.\n", name, conflicts);}// 查找人名在哈希表中的位置int findName(HashTable *table, char *name){int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置int i = 0;while (table->flags[index] != 0) // 人名发生冲突{if (strcmp(table->data[index].name, name) == 0) // 比较人名是否相同{return index; // 找到了人名，返回索引位置}i++;index = (index + i * i) % table->size; // 发生冲突时，使用平方探测再散列法处理}return NOT_FOUND; // 未找到人名}int main(){HashTable table;initHashTable(&table, HashTABLE_SIZE);// 待填入哈希表的人名char names[30][MAX_NAME_LENGTH] = {"chencaiyi", "chenxinxin", "fangsongjie", "huangjiawei", "huangjunlin", "leiyang","luwei", "wangzhanqi", "wuweidong", "longjiajing", "huangweiqin", "chenshangming", "huangtao","maixupeng", "chenying", "liujunhui", "chenqingdong", "guoziming", "chenyilong", "libaiyang", "liangdeguang","zhangyuxing", "huangyibin", "liuwenlong", "zengzihao", "wangshulian", "zhuzixian", "lidingkun", "caofu", "yuemingju"};// 建立哈希表for (int i = 0; i < 30; i++){insertName(&table, names[i]);}// 查找程序char searchName[MAX_NAME_LENGTH];printf("Enter a name to search: ");scanf("%s", searchName);int index = findName(&table, searchName);if (index != NOT_FOUND){printf("Found at index %d\n", index);}else{printf("Not found\n");}return 0;}

HashMap(2).cpp

/* * @Author: hiddenSharp429 z404878860@163.com * @Date: 2023-06-14 17:29:44 * @LastEditors: hiddenSharp429 z404878860@163.com * @LastEditTime: 2023-06-14 17:45:38 * @FilePath: \appe:\C OR C++\code\HashMap(2).cpp * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE */#include #include #include #define HashTABLE_SIZE 61// 哈希表的大小，选择一个较大的素数#define MAX_NAME_LENGTH 20 // 人名的最大长度#define NOT_FOUND -1 // 未找到的标志typedef struct{char name[MAX_NAME_LENGTH]; // 人名} Person;typedef struct{Person *data; // 哈希表的数据int *flags; // 标记哈希表中的位置是否为空int size; // 哈希表的大小} HashTable;// 哈希函数：自定义哈希函数int hashFunction(char *name, int size){int hash = 0;int nameLength = strlen(name);for (int i = 0; i < nameLength; i++){hash = (hash * 31 + name[i]) % size;}return hash;}// 初始化哈希表void initHashTable(HashTable *table, int size){table->data = (Person *)malloc(sizeof(Person) * size); // 为哈希表分配空间table->flags = (int *)malloc(sizeof(int) * size);// 为标记数组分配空间table->size = size;// 设置哈希表的大小for (int i = 0; i < size; i++){strcpy(table->data[i].name, ""); // 初始化人名为空table->flags[i] = 0; // 初始化标记数组为0}}// 插入人名到哈希表中void insertName(HashTable *table, char *name){int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置int i = 0;int conflicts = 0; // 记录发生冲突的次数while (table->flags[index] == 1) // 人名发生冲突{// 发生冲突时，使用平方探测再散列法处理i++;index = (index + i * i) % table->size;conflicts++;}strcpy(table->data[index].name, name); // 将人名填入哈希表中table->flags[index] = 1; // 标记数组中的位置为1，表示该位置已经有人名printf("Inserted %s with %d conflicts.\n", name, conflicts);}// 查找人名在哈希表中的位置int findName(HashTable *table, char *name){int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置int i = 0;while (table->flags[index] != 0) // 人名发生冲突{if (strcmp(table->data[index].name, name) == 0) // 比较人名是否相同{return index; // 找到了人名，返回索引位置}i++;index = (index + i * i) % table->size; // 发生冲突时，使用平方探测再散列法处理}return NOT_FOUND; // 未找到人名}int main(){HashTable table;initHashTable(&table, HashTABLE_SIZE);// 待填入哈希表的人名char names[30][MAX_NAME_LENGTH] = {"chencaiyi", "chenxinxin", "fangsongjie", "huangjiawei", "huangjunlin", "leiyang","luwei", "wangzhanqi", "wuweidong", "longjiajing", "huangweiqin", "chenshangming", "huangtao","maixupeng", "chenying", "liujunhui", "chenqingdong", "guoziming", "chenyilong", "libaiyang", "liangdeguang","zhangyuxing", "huangyibin", "liuwenlong", "zengzihao", "wangshulian", "zhuzixian", "lidingkun", "caofu", "yuemingju"};// 建立哈希表for (int i = 0; i < 30; i++){insertName(&table, names[i]);}// 查找程序char searchName[MAX_NAME_LENGTH];printf("Enter a name to search: ");scanf("%s", searchName);int index = findName(&table, searchName);if (index != NOT_FOUND){printf("Found at index %d\n", index);}else{printf("Not found\n");}return 0;}

HashMap(3).cpp

/* * @Author: hiddenSharp429 z404878860@163.com * @Date: 2023-06-14 17:28:46 * @LastEditors: hiddenSharp429 z404878860@163.com * @LastEditTime: 2023-06-14 17:46:28 * @FilePath: \appe:\C OR C++\code\HashMap(3).cpp * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE */#include #include #include #define HashTABLE_SIZE 61// 哈希表的大小，选择一个较大的素数#define MAX_NAME_LENGTH 20 // 人名的最大长度#define NOT_FOUND -1 // 未找到的标志typedef struct PersonNode{char name[MAX_NAME_LENGTH]; // 人名struct PersonNode *next;// 指向下一个节点的指针} PersonNode;typedef struct{PersonNode **data; // 哈希表的数据int size;// 哈希表的大小} HashTable;// 哈希函数：自定义哈希函数int hashFunction(char *name, int size){int hash = 0;int nameLength = strlen(name);for (int i = 0; i < nameLength; i++){hash = (hash * 31 + name[i]) % size;}return hash;}// 初始化哈希表void initHashTable(HashTable *table, int size){table->data = (PersonNode **)malloc(sizeof(PersonNode *) * size); // 为哈希表分配空间table->size = size; // 设置哈希表的大小for (int i = 0; i < size; i++){table->data[i] = NULL; // 初始化每个槽位为空}}// 插入人名到哈希表中void insertName(HashTable *table, char *name){int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置// 创建新节点PersonNode *newNode = (PersonNode *)malloc(sizeof(PersonNode));strcpy(newNode->name, name);newNode->next = NULL;if (table->data[index] == NULL){// 槽位为空，直接插入新节点table->data[index] = newNode;}else{// 槽位非空，遍历链表找到尾节点并插入新节点PersonNode *currentNode = table->data[index];while (currentNode->next != NULL){currentNode = currentNode->next;}currentNode->next = newNode;}printf("Inserted %s\n", name);}// 查找人名在哈希表中的位置int findName(HashTable *table, char *name){int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置// 遍历链表查找人名PersonNode *currentNode = table->data[index];while (currentNode != NULL){if (strcmp(currentNode->name, name) == 0){return index; // 找到了人名，返回索引位置}currentNode = currentNode->next;}return NOT_FOUND; // 未找到人名}int main(){HashTable table;initHashTable(&table, HashTABLE_SIZE);// 待填入哈希表的人名char names[30][MAX_NAME_LENGTH] = {"chencaiyi", "chenxinxin", "fangsongjie", "huangjiawei", "huangjunlin", "leiyang","luwei", "wangzhanqi", "wuweidong", "longjiajing", "huangweiqin", "chenshangming", "huangtao","maixupeng", "chenying", "liujunhui", "chenqingdong", "guoziming", "chenyilong", "libaiyang", "liangdeguang","zhangyuxing", "huangyibin", "liuwenlong", "zengzihao", "wangshulian", "zhuzixian", "lidingkun", "caofu", "yuemingju"};// 建立哈希表for (int i = 0; i < 30; i++){insertName(&table, names[i]);}// 查找程序char searchName[MAX_NAME_LENGTH];printf("Enter a name to search: ");scanf("%s", searchName);int index = findName(&table, searchName);if (index != NOT_FOUND){printf("Found at index %d\n", index);}else{printf("Not found\n");}return 0;}

结束语

  因为是算法小菜，所以提供的方法和思路可能不是很好，请多多包涵~如果有疑问欢迎大家留言讨论，你如果觉得这篇文章对你有帮助可以给我一个免费的赞吗？我们之间的交流是我最大的动力！