【VIP专享】哈希表的设计与实现,含源代码

链表查找的时间效率为O(N)，二分法为log2N，B+ Tree为log2N，但Hash链表查找的时间效率为O(1)。

设计高效算法往往需要使用Hash链表，常数级的查找速度是任何别的算法无法比拟的，Hash链表的构造和冲突的不同实现方法对效率当然有一定的影响，然而Hash函数是Hash链表最核心的部分，下面是几款经典软件中使用到的字符串Hash函数实现，通过阅读这些代码，我们可以在Hash算法的执行效率、离散性、空间利用率等方面有比较深刻的了解。

下面分别介绍几个经典软件中出现的字符串Hash函数。

●PHP中出现的字符串Hash函数static unsigned long hashpjw(char *arKey, unsigned int nKeyLength){unsigned long h = 0, g;char *arEnd=arKey+nKeyLength;while (arKey < arEnd) {h = (h << 4) + *arKey++;if ((g = (h & 0xF0000000))) {h = h ^ (g >> 24);h = h ^ g;}}return h;}●OpenSSL中出现的字符串Hash函数unsigned long lh_strhash(char *str){int i,l;unsigned long ret=0;unsigned short *s;if (str == NULL) return(0);l=(strlen(str)+1)/2;s=(unsigned short *)str;for (i=0; iret^=(s[i]<<(i&0x0f));return(ret);}/* The following hash seems to work very well on normal text strings* no collisions on /usr/dict/words and it distributes on %2^n quite* well, not as good as MD5, but still good.*/unsigned long lh_strhash(const char *c){unsigned long ret=0;long n;unsigned long v;int r;if ((c == NULL) || (*c == '\0'))return(ret);/*unsigned char b[16];MD5(c,strlen(c),b);return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));*/n=0x100;while (*c){v=n|(*c);n+=0x100;r= (int)((v>>2)^v)&0x0f;ret=(ret(32-r));ret&=0xFFFFFFFFL;ret^=v*v;c++;}return((ret>>16)^ret);}●MySql中出现的字符串Hash函数#ifndef NEW_HASH_FUNCTION/* Calc hashvalue for a key */static uint calc_hashnr(const byte *key,uint length){register uint nr=1, nr2=4;while (length--){nr^= (((nr & 63)+nr2)*((uint) (uchar) *key++))+ (nr << 8);nr2+=3;}return((uint) nr);}/* Calc hashvalue for a key, case indepenently */static uint calc_hashnr_caseup(const byte *key,uint length){register uint nr=1, nr2=4;while (length--){nr^= (((nr & 63)+nr2)*((uint) (uchar) toupper(*key++)))+ (nr << 8); nr2+=3;}return((uint) nr);}#else/** Fowler/Noll/Vo hash** The basis of the hash algorithm was taken from an idea sent by email to the* IEEE Posix P1003.2 mailing list from Phong Vo (kpv@) and* Glenn Fowler (gsf@). Landon Curt Noll (chongo@) * later improved on their algorithm.** The magic is in the interesting relationship between the special prime * 16777619 (2^24 + 403) and 2^32 and 2^8.** This hash produces the fewest collisions of any function that we've seen so* far, and works well on both numbers and strings.*/uint calc_hashnr(const byte *key, uint len){const byte *end=key+len;uint hash;for (hash = 0; key < end; key++){hash *= 16777619;hash ^= (uint) *(uchar*) key;}return (hash);}uint calc_hashnr_caseup(const byte *key, uint len){const byte *end=key+len;uint hash;for (hash = 0; key < end; key++){hash *= 16777619;hash ^= (uint) (uchar) toupper(*key);}return (hash);}#endifMysql中对字符串Hash函数还区分了大小写●另一个经典字符串Hash函数unsigned int hash(char *str){register unsigned int h;register unsigned char *p;for(h=0, p = (unsigned char *)str; *p ; p++)h = 31 * h + *p;return h; }。

(此文档为word格式，下载后您可任意编辑修改！) 数据结构课程设计（哈希表的设计）院系专业班级学生姓名学号课程设计日期：2011年6月26日至2011年7 月7 日目录一、问题描述 (3)二、需求分析1、基本要求 (3)2、测试数据 (3)三、概要设计 (3)四、详细设计 (4)五、测试分析 (11)六、课程设计总结 (13)七、附录（源代码） (14)一、问题描述针对自己班级体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。

二、需求分析基本要求：假设人名为中国姓名的汉语拼音模式。

待填入哈希表的人名共有30个，取平均查找长度的上限为2。

哈希函数用除留余数法构造，用链表法处理冲突。

测试数据：输入30个人的姓名拼音，即30个字符串，然后用除留余数法构建哈希表并用链表法处理冲突，最后将结果输出，程序自动计算查找长度的总数和平均查找长度，然后用户可以根据需求进行查找操作。

三、概要设计四、详细设计头文件#include <stdio. 30 *哈希表长度*int sum=0,k=0;typedef struct Node*哈希表结构体*{char key_code[10];*哈希表地址*struct Node *next;}Node;typedef struct mode;}void Hash_Init(HashTable str[0]+str[1]+str[2]; }int Hash_Insert(HashTable 1;}Node* Hash_Search(HashTable NULL;} else if( p;}p = p->next;sum++;}}return NULL;}int Hash_Create(HashTable ");return 1;}int ;i++){printf("%4d",i);printf("%4d",");}return count2;}void Hash_Link()*链表法构造函数*{int key;int i;Node *node;HashTable ",k); *查找总长度*printf("ASL=%d8\n",k); *平均查找长度*printf("请输入要查找的数据：");*输入查找的姓名*scanf("%s",&key);node = Hash_Search(",sum);if(node != NULL)printf("查找成功！");elseprintf("查找不成功！");}void -1;di++){address=((data%P)+di)%;if(status[address]==0){;}int 1;else{for(di=1;di<=-1;di++)*哈希表中元素与查找元素不相等，查找下一元素* {address=((key%P)+di)%;if( di+1;break;}}}if(di>=)return 0;}int main()*主函数*{printf("\t\t\t************************\n");printf("\t\t\t 哈希表设计\n");printf("\n");printf("\t\t\t************************\n");printf("\n");Hash_Link();}五、测试分析测试数据：随机输入的30个人的姓名拼音测试过程：输入30个人的姓名拼音，观察输出结果，并进行查找操作测试结果：主界面：哈希表：六、课程设计总结这次数据结构课程设计持续了两周，在这两周中付出了很多，同样也得到了很多。

数据结构哈希表设计数据结构哈希表设计====================章节一：引言---------------------在计算机科学中，哈希表（Hash Table）是一种用于实现关联数组（Associative Array）或映射（Map）的数据结构。

哈希表通过使用哈希函数将键（Key）映射到存储位置（数组索引）来实现快速的插入、删除和查找操作。

本文将详细介绍哈希表的设计原理和实现方法。

章节二：哈希函数---------------------哈希函数是哈希表的核心，它将任意大小的输入映射为固定大小的输出，通常是一个整数。

好的哈希函数应该具有以下特性：1.一致性：对于相同的输入，始终返回相同的输出。

2.均匀性：哈希函数应将输入均匀地映射到输出范围内。

3.支持快速计算：哈希函数应该能够在常数时间内计算出哈希值。

章节三：哈希冲突解决方法------------------------由于哈希函数的输出空间通常较小，不同的键可能会被映射到相同的存储位置上，这就导致了哈希冲突。

在实际应用中，哈希冲突是不可避免的。

为了解决哈希冲突，常用的方法有以下几种：1.法（Chning）：将冲突的键值对存储在同一个链表中，在插入和查找时顺序遍历链表即可。

2.开放地质法（Open Addressing）：将冲突的键值对存储在哈希表中的其他位置，通过一定的规则（如线性探测、二次探测等）查找下一个可用的位置。

3.建立更好的哈希函数：合适的哈希函数能够尽量减少冲突的概率。

章节四：哈希表的实现--------------------在实现哈希表时，我们需要考虑以下几个重要的方面：1.哈希函数的选择：选择合适的哈希函数是保证哈希表性能的关键。

不同的键类型可能需要不同的哈希函数。

2.存储结构的选择：可以使用数组、链表、红黑树等数据结构来存储哈希表中的键值对。

3.动态扩容：当哈希表中的数据量增加时，需要及时进行扩容操作，以保证哈希表的性能。

数据结构课程设计题目哈希表的设计与实现作者院系信息工程学院专业信息管理与信息系统学号1514210117指导老师张慧答辩时间2016年12月18日目录数据结构课程设计 01系统需求分析 (2)1.1用户需求分析 (3)1.2功能需求分析 (3)1.3数据需求分析 (3)1.4 小结 (4)2系统设计 (4)2.1设计内容及要求 (4)2.2总体设计思路 (5)2.3程序详细设计流程图 (5)2.31以姓名为关键字的Hash()函数流程图 (5)2.32添加结点信息流程图: (7)2.33按姓名查找流程图: (8)2.34按号码查找流程图 (9)2.35主程序流程图 (11)2.4详细设计编码 (13)2.41建立节点 (13)2.42对哈希函数的定义 (13)2.43哈希查找 (14)2.44主函数 (15)3系统测试 (16)3.1上机调试 (16)3.2调试结果与分析 (17)4总结 (21)5附录 (22)1系统需求分析在信息化时代的今天，计算机技术已经是发展到一个很可观的地步了，特别是面向窗口的操作系统的出现，使得程序设计更加的容易了。

在过去计算机内存容量小，CPU计算速度慢，关于程序设计中的数据结构也因此提出来很多的关于解决这方面的问题。

哈希表就是其中之一，哈希表是一个由关键字与值组成的特殊的一种数据结构。

它的出现主要是为了解决在结构中查找记录时需要进行一系列和关键字的比较,这一类查找方法是建立在“比较”的基础上的，在顺序等的查找中，查找的效率是依赖于查找过程中所比较的次数。

理想的情况是希望不经过任何的比较一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系，使得每个关键字和结构中一个唯一的存储位置相对应。

因而在查找时只要根据这个对应关系找到给定的值的像。

若结构中存在关键字和该值相等的记录，则所要查找的数就必定就是这个所查找到的记录。

哈希函数是建立哈希表的一个重要的成员，它的构造方法分为以下几种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。

哈希表及其常⽤算法（代码实例）<hash表的特性>Hash 表是使⽤ O(1) 时间进⾏数据的插⼊删除和查找，但是 hash 表不保证表中数据的有序性，这样在 hash 表中查找最或者最⼩数据的时间是 O(N) 。

<寻址和 hash 函数>理想状态下 hash ⾜够⼤，每⼀数据保存在⼀个 hash 存储单元内，这样对于插⼊删除和查找某⼀个数据就可以直接得到。

但是现实情况下 hash 表不可能⽆限⼤，⽽且理论上保存的数据的个数是没有限制的，这样保存的数据的数量就远远⼤于 hash 表的存储单元的数量。

为了实现在 O(1) 内对数据进⾏插⼊删除和查找，就必须将⼀个数据映射到 hash 表中的固定位置，这个映射函数就是 hash 函数。

Hash 函数通过对数据进⾏计算得到⼀个在 hash 表中的位置地址。

图 1.1 理想的 hash 表要选择较好的 hash 函数，以及 hash 表存储单元的数量，这样才能使保存在 hash 表中的数据均匀分布。

理想状态不太可能实现，由于存储的数据数量远远⼤于 hash 表存储单元的数量，所以再好的 hash 函数也可能使不同的数据得到相同的映射位置，这就造成了冲突。

但是好的 hash 函数可以将这种冲突降到最低。

<分离链接>解决这种冲突的第⼀种⽅法是借助链表来实现，就是将数据实际存放在与 hash 表存储单元相链接的链表中，⽽不是 hash 的存储单元中。

图 2.1 分离链表当产⽣冲突的时候，将两个数据都链接在同⼀ hash 存储单元保存的链表中。

当⼀个存储单元保存的链表中有多个数据的时候，对于链表后⾯的数据的查找添加和删除就是不是严格意义上的 O(1) 了。

⼀个好的 hash 函数可以使得这个链表很短。

最坏情况下，当所有的数据都保存在⼀个 hash 单元指定的链表中的时候，那么这个 hash 就和链表⼀样了。

<开放地址>使⽤开放地址⽅法解决冲突的时候，数据仍然保存在 hash 表的存储单元中，但是当冲突发⽣的时候，要再次计算新的地址。

数据结构哈希表设计1.引言哈希表（Hash Table）是一种常用的数据结构，用于快速存储和检索数据。

它通过将键（Key）映射到值（Value）来实现高效的数据存储和查找。

本文将介绍哈希表的设计原理和实现方法，以及一些常见的应用场景。

2.哈希函数的选择哈希函数是实现哈希表的关键，它将键映射到哈希值。

一个好的哈希函数应当具有以下特点：●均匀性：对于任意的输入，哈希函数应该能够将其均匀地映射到哈希表的各个位置，避免产生过多的冲突。

●高效性：哈希函数应当能够在常数时间内计算出哈希值，避免影响哈希表的性能。

●低冲突性：哈希函数应当能够尽可能少的冲突，即不同的键经过哈希函数计算得到相同的哈希值的概率应当很低。

3.冲突解决方法由于哈希函数的有限性，不同的键可能会产生相同的哈希值，这种情况称为冲突。

常见的冲突解决方法有以下几种：●链地质法（Chning）：将哈希表的每个位置引入链表，当多个键映射到相同的位置时，将它们存储在链表中。

●开放寻址法（Open Addressing）：当发生冲突时，通过一定的方法在哈希表中寻找下一个可用的位置，直到找到一个空位置或者遍历完整个哈希表。

●再哈希法（Rehashing）：当发生冲突时，通过应用另一个哈希函数来计算出一个新的哈希值，以此来解决冲突。

4.哈希表的操作哈希表支持以下几种操作：●插入（Insert）：将一个键值对插入到哈希表中。

●删除（Delete）：从哈希表中删除指定的键值对。

●查找（Search）：根据给定的键，在哈希表中查找对应的值。

●更新（Update）：根据给定的键，更新哈希表中对应的值。

5.哈希表的应用哈希表广泛应用于各种场景，例如：●缓存：哈希表可以用于实现高效的缓存系统，根据请求的键值对快速查找到对应的数据。

●字典：哈希表可以被用作实现字典，将单词与其定义相关联。

●数据库索引：哈希表可以用于构建数据库的索引，提高数据的检索性能。

6.总结哈希表是一种高效的数据结构，通过将键映射到值来实现快速的数据存储和检索。

数学与计算机学院课程设计说明书课程名称: 数据结构-课程设计课程代码: 8404181题目：哈希表的设计与实现年级/专业/班: 2009级软件工程3班学生姓名：张加发学号：312009*********开始时间：2011 年06 月20 日完成时间：2011 年06 月29 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量(45）总分（100)指导教师签名: 年月日数据结构课程设计任务书学院名称: 数学与计算机学院课程代码：8404181专业：软件工程年级：2009级一、设计题目哈希表的设计与实现二、主要内容设计哈希表实现电话号码查找系统，要求如下：1）设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表（要求设计两种以上不同的散列函数)；3)采用两种以上的方法解决冲突；4）查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。

三、具体要求及应提交的材料1．每个同学以自己的学号和姓名建一个文件夹,如：“312009*********张三”。

里面应包括：学生按照课程设计的具体要求所开发的所有源程序(应该放到一个文件夹中）、任务书和课程设计说明书的电子文档。

2．打印的课程设计说明书(注意：在封面后夹入打印的“任务书”以后再装订）。

四、主要技术路线提示法、除留余数法等，解决冲突的方法也较多,常用：开放定址法、链地址法等。

五、进度安排共计两周时间，建议进度安排如下:选题，应该在上机实验之前完成需求分析、概要设计可分配4学时完成详细设计可分配4学时调试和分析可分配10学时.2学时的机动，可用于答辩及按教师要求修改课程设计说明书。

注：只用课内上机时间一般不能完成设计任务,所以需要学生自行安排时间做补充.六、推荐参考资料［1］苏仕华等编著,数据结构课程设计，机械工业出版社，2007［2］严蔚敏等编著，数据结构（C语言版），清华大学出版社，2003［3］严蔚敏等编著,数据结构题集（C语言版）,清华大学出版社，2003指导教师签名日期年月日系主任审核日期年月日摘要分析了对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的应用，对现实复杂问题的分析建模和解决方法！分析了针对系统的需求所要执行的解决方法的可行性，正确性.完成系统前需要进行问题描述、系统分析、设计建模、代码实现、调试修改，结果分析。

数据结构哈希表设计在计算机科学中，数据结构是组织和存储数据的方式，以便能够高效地访问、操作和管理数据。

哈希表（Hash Table）作为一种重要的数据结构，在许多应用中都发挥着关键作用。

它以其高效的查找、插入和删除操作，成为了处理大量数据时的得力工具。

那么，什么是哈希表呢？简单来说，哈希表是一种根据关键码值（Key）而直接进行访问的数据结构。

通过一个哈希函数（Hash Function），将关键码映射到表中的一个位置来访问记录，以加快查找的速度。

要设计一个有效的哈希表，首先需要考虑的是哈希函数的选择。

一个好的哈希函数应该尽可能地将不同的关键码值均匀地分布在哈希表的存储空间中，以减少冲突的发生。

常见的哈希函数设计方法包括直接定址法、数字分析法、平方取中法、折叠法、除留余数法等。

以除留余数法为例，假设我们要存储的关键码值是整数，哈希表的长度为 m，那么哈希函数可以设计为 h(key) ＝ key ％ m 。

也就是说，用关键码值除以 m 取余数，得到的结果就是在哈希表中的存储位置。

然而，即使选择了一个较好的哈希函数，冲突仍然可能会发生。

这是因为哈希函数将一个无限的关键码值集合映射到一个有限的存储空间中，必然会存在多个关键码值被映射到相同位置的情况。

当发生冲突时，就需要采用合适的冲突解决方法。

常见的冲突解决方法有开放定址法和链地址法。

开放定址法是指当发生冲突时，按照某种探查方式在哈希表中寻找下一个空闲的位置来存储冲突的元素。

常见的探查方法有线性探查、二次探查和双重探查等。

链地址法则是将所有哈希地址相同的元素构成一个单链表，并将单链表的头指针存储在哈希表的对应位置。

当查找元素时，首先通过哈希函数计算出哈希地址，然后在对应的单链表中进行查找。

在实际设计哈希表时，还需要考虑哈希表的装填因子（Load Factor）。

装填因子是指哈希表中已存储的元素个数与哈希表的长度之比。

装填因子越大，冲突发生的可能性就越高；装填因子越小，虽然冲突减少，但会浪费更多的存储空间。

哈希表的构造⽅法、冲突处理⽅法及哈希拉链法的简单代码实现 由于哈希表的查找⾼效性，在平时的算法中⽤的也是⽐较多。

例如：字符串、单词个数的统计，只出现⼀次字符或者数字的统计，两个集合相同元素的查找等等，还有插⼊删除的⾼效（链地址法）都可以⽤哈希表来解决。

所以这⾥对其做⼀个⼩⼩的总结。

缺点可能是需要占⽤额外的内存空间。

⼀、哈希函数的构造⽅法下⾯介绍五种常⽤的哈希构造⽅法：构造哈希函数的原则是：（1）函数本⾝便于计算；（2）计算出来的地址分布均匀，即对任⼀关键字k，f(k) 对应不同地址的概率相等，⽬的是尽可能减少冲突。

1、除留余数法；取关键字被某个不⼤于哈希表长m的数p除后所得的余数为哈希地址。

即：H(key)=key MODE p,p<=m.(p的取值最好为素数)。

若冲突较多，可取较⼤的m和p值。

2、随机法；采⽤⼀个伪随机函数做哈希函数，即：H(key)=random(key)。

其中random为随机函数。

通常，当关键字长度不等时采⽤此法构造哈希函数较为恰当。

3、平⽅取中法；当⽆法确定关键字中哪⼏位分布较均匀时，可以先求出关键字的平⽅值，然后按需要取平⽅值的中间⼏位作为哈希地址。

这是因为：平⽅后中间⼏位和关键字中每⼀位都相关，故不同关键字会以较⾼的概率产⽣不同的哈希地址。

例如对于关键key：123。

1234^2=1522756，H(k)关键字的哈希地址为：227.4、折叠法；这种⽅法是按哈希表地址位数将关键字分成位数相等的⼏部分（最后⼀部分可以较短），然后将这⼏部分相加，舍弃最⾼进位后的结果就是该关键字的哈希地址。

具体⽅法有折叠法与移位法。

移位法是将分割后的每部分低位对齐相加，折叠法是从⼀端向另⼀端沿分割界来回折叠（奇数段为正序，偶数段为倒序），然后将各段相加。

例如：key=12360324711202065,哈希表长度为1000，则应把关键字分成3位⼀段，在此舍去最低的两位65，分别进⾏移位叠加和折叠叠加，求得哈希地址为105和907。

课程名称：数据结构XXXXXXXX本科学生课程设计（论文）题目哈希表的设计与实现姓名 XXX学号 XXXXXXXXXXXX学部计算机科学与技术专业、年级计算机科学与技术大二指导教师 XX2010 年 11月 28日摘要随着信息技术的发展，关于各种程序中的数据结构也是层出不穷，对于项目某一方面的计算或者是某一方面的研究，出现了专门的数据结构，哈希表就是其中之一，哈希表作为另类的一种数据结构，其作用也是区别于其它同类的数据结构的，它是由两部分组成的：键(key)和值，通过键可以迅速的查找到你需要的值。

常见的构造哈希函数的方法有直接定址法除留余数法平方取中法数字分析法等。

一般创建哈希表时可能会出现很多的冲突，常用的处理冲突的方法为开放定址法再哈希法链地址法建立一个公共溢出区。

关键词: 数据结构；哈希表；键(key)；目录第1章前言与系统实现 ____________________________________________ 4 1.1前言__________________________________________________________ 4 1.2系统实现______________________________________________________ 51.2.1 开发环境_________________________________________________ 51.2.2 Visual C++环境的安装_____________________________________ 5 第2章系统功能分析_______________________________________________ 6 2.1 系统功能需求分析 ____________________________________________ 6 2.2 任务定义 ____________________________________________________ 6 第3章总体设计___________________________________________________ 7 3.1系统数据结构__________________________________________________ 7 3.2主要算法流程图________________________________________________ 83.2.1 以姓名为关键字的CreateHashList()函数流程图________________ 83.2.2 哈希表查找算法流程图______________________________________ 93.2.3主程序流程图_____________________________________________ 10 第4章详细设计和编码____________________________________________ 114.1节点的建立___________________________________________________ 11 4.2 对哈希函数的定义 ___________________________________________ 11 4.3 创建哈希表算法、代码如下所示: ________________________________ 124.3.1 算法_____________________________________________________ 124.3.2代码_____________________________________________________ 12 4.4哈希查找_____________________________________________________ 13 4.5显示哈希表___________________________________________________ 16 4.6主菜单设计___________________________________________________ 18 4.7 主函数设计 __________________________________________________ 18 第5章程序运行测试_______________________________________________ 215.1程序主界面___________________________________________________ 21 5.2哈希表初始化_________________________________________________ 21 5.3按姓名查找记录_______________________________________________ 23 5.4显示哈希表全部记录___________________________________________ 24 总结______________________________________________________________ 25 参考文献__________________________________________________________ 26第1章前言与系统实现1.1前言在信息化时代的今天，计算机技术已经是发展到一个很可观的地步了，特别是面向窗口的操作系统的出现，使得程序设计更加的容易了。

哈希表算法hash表问题描述：针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。

基本要求：假设人名为中国人姓名的汉语拼音形式。

待填入哈希表的人名共有30个，取平均查找长度的上限为2。

哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。

#include <stdio.h>#include<malloc.h>#include<string.h> //#include#define HASH_LEN 50 //哈希表的长度#define M 47#define NAME_NO 30 //人名的个数typedef struct NAME{char *py; //名字的拼音int k; //拼音所对应的整数}NAME;NAME NameList[HASH_LEN];typedef struct hterm //哈希表{char *py; //名字的拼音int k; //拼音所对应的整数int si; //查找长度}HASH;HASH HashList[HASH_LEN];/*-----------------------姓名（结构体数组）初始化---------------------------------*/void InitNameList(){NameList[0].py="zhanghongshuai";NameList[1].py="xurensong";NameList[2].py="huangxiangyu";NameList[3].py="luoqi";NameList[4].py="zhangsan";NameList[5].py="lisi";NameList[6].py="wangwu";NameList[7].py="renwei";NameList[8].py="zhangchu";NameList[9].py="wangmengyuan";NameList[10].py="libaohua";NameList[11].py="zhaoyanlong";NameList[12].py="jwangyuxin";NameList[13].py="duyanmo";NameList[14].py="wangmingyang";NameList[15].py="lijiawei";NameList[16].py="hesiyu";NameList[17].py="zhanghailong";NameList[18].py="lixinyu";NameList[19].py="songdiyao";NameList[20].py="zhaomingzhi";NameList[21].py="zhangchenglong";NameList[22].py="sunjie";NameList[23].py="zhangdongmei";NameList[24].py="antianyu";NameList[25].py="zhulaiao";NameList[26].py="wangyuting";NameList[27].py="wangxiliang";NameList[28].py="zhangdeshuai";NameList[29].py="xumingming";char *f;int r,s0;for (int i=0;i<NAME_NO;i++)// 求出各个姓名的拼音所对应的整数{s0=0;f=NameList[i].py;for (r=0;*(f+r) != '\0';r++) //方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字s0=*(f+r)+s0;NameList[i].k=s0;}}/*-----------------------建立哈希表---------------------------------*/void CreateHashList(){for (int i=0; i<HASH_LEN;i++)//哈希表的初始化{HashList[i].py="";HashList[i].k=0;HashList[i].si=0;}for (int i=0; i<=NAME_NO;){int sum=0;int adr=(NameList[i].k) % M; //哈希函数int d=adr;if(HashList[adr].si==0) //如果不冲突{HashList[adr].k=NameList[i].k;HashList[adr].py=NameList[i].py;HashList[adr].si=1;}else //冲突{do{d=(d+((NameList[i].k))%10+1)%M; //伪散列sum=sum+1; //查找次数加1}while (HashList[d].k!=0);HashList[d].k=NameList[i].k;HashList[d].py=NameList[i].py;HashList[d].si=sum+1;}i++;}}/*-------------------------------------查找------------------------------------*/ void FindList(){printf("\n\n请输入姓名的拼音: "); //输入姓名char name[20]={0};scanf("%s",name);int s0=0;for (int r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)s0+=name[r];int sum=1;int adr=s0 % M; //使用哈希函数int d=adr;if(HashList[adr].k==s0) //分3种情况进行判断printf("\n姓名:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);else if (HashList[adr].k==0)printf("无该记录!");else{int g=0;do{d=(d+s0%10+1)%M; //伪散列sum=sum+1;if (HashList[d].k==0){printf("无记录! ");g=1;}if (HashList[d].k==s0){printf("\n姓名:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);g=1;}}while(g==0);}}/*--------------------------------显示哈希表----------------------------*/ void Display(){printf("\n\n地址\t关键字\t\t搜索长度\tH(key)\t\t拼音 \n"); //显示的格式 for(int i=0; i<15; i++){printf("%d ",i);printf("\t%d ",HashList[i].k);printf("\t\t%d ",HashList[i].si);printf("\t\t%d ",(HashList[i].k)%M);printf("\t %s ",HashList[i].py);printf("\n");}// printf("按任意键继续显示...\n");//由于数据比较多，所以分屏显示（以便在Win9x／DOS下能看到所有的数据）// getch();for( int i=15; i<30; i++){printf("%d ",i);printf("\t%d ",HashList[i].k);printf("\t\t%d ",HashList[i].si);printf("\t\t%d ",(HashList[i].k)%M);printf("\t %s ",HashList[i].py);printf("\n");}// printf("按任意键继续显示...\n");// getch();for( int i=30; i<40; i++){printf("%d ",i);printf("\t%d ",HashList[i].k);printf("\t\t%d ",HashList[i].si);printf("\t\t%d ",(HashList[i].k)%M);printf("\t %s ",HashList[i].py);printf("\n");}//printf("按任意键继续显示...\n");//getch();for( int i=40; i<50; i++){printf("%d ",i);printf("\t%d ",HashList[i].k);printf("\t\t%d ",HashList[i].si);printf("\t\t%d ",(HashList[i].k)%M);printf("\t %s ",HashList[i].py);printf("\n");}float average=0;for (int i=0;i<HASH_LEN;i++)average+=HashList[i].si;average/=NAME_NO;printf("\n\n平均查找长度：ASL(%d)=%f \n\n",NAME_NO,average);}/*--------------------------------主函数----------------------------*/ main() {/* ::SetConsoleTitle("哈希表操作"); //Windows API函数,设置控制台窗口的标题HANDLE hCon = ::GetStdHandle(STD_OUTPUT_HANDLE); //获得标准输出设备的句柄 ::SetConsoleTextAttribute(hCon, 10|0); //设置文本颜色*/printf("\n------------------------哈希表的建立和查找----------------------"); InitNameList();CreateHashList ();while(1){printf("\n\n");printf(" 1. 显示哈希表\n");printf(" 2. 查找\n");printf(" 3. 退出\n");err:char ch1;scanf("%c",&ch1);if (ch1=='1')Display();else if (ch1=='2')FindList();else if (ch1=='3')return 0;else{printf("\n请输入正确的选择!"); goto err;}}显示哈希表：查找退出。