哈希函数的设计与评价。
一目的。利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用c/c++语言进行程序设计，并规范地完成课程设计报告。掌握哈希表的构造方法和冲突的解决问题方法，掌握哈希结构在实际问题中的应用。
在现代密码学中，哈希函数扮演着非常重要的角色。它不仅在安全通信中起着重要的作用，而且是许多密码算法和协议的基本结构模块。一个好的hash函数可以很大程度上提高程序的整体时间效率和空间效率。
二需求分析。
1、题目描述。
利用哈希表存储上述数，设计3个哈希函数以及两种不同的冲突处理方式（一共6种存储方式），将上述数据存储在一个长度为19的数组中。并列出不同存储方式的冲突值，从中选出最优的存储方式（冲突值最小的）。
2、功能描述。
使用数组data[13]来存储初始的13个数据，然后使用hash[19]线性数组来存储hash过后的数据，采用直接定址法或除留余数法或随机数法来进行hash，采用线性探测再散列法或再哈希法解决冲突。
3、输入输出形式。
输入数据：无（数据已经给出，存入data数组）
输出数据：分别给出三种哈希函数与两种冲突解决方案两两组合的hash数组每一位的值，并且给出每一种组合的冲突值。
三概要设计。
1、数组和主要变量的含义。
data:存待处理的数据。
hash:存处理后的数据。
pos:处理每一个数据时，存放该数据hash后应该在hash数组中的位置。
collision:处理每一个数据的时候，冲突的次数
2、hash函数的算法思想。
1）直接定址法：取关键字或关键字的某个线性函数值为散列地址。即h(key)=key或h(key) =a·key + b，其中a和b为常数（这种散列函数叫做自身函数）
2）除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 h(key) =key mod p,p<=m。
不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
3）随机数法：根据关键字设置随机数种子，再用随机数产生函数产生对应数据的位置。
3、冲突处理函数的算法思想。
1）hi=(h(key) +di) mod m,i=1,2,…，k(k<=m-1)，其中h(key)为散列函数，m为散列表长，di为增量序列， di=1,2,3,…，m-1，称线性探测再散列；
2）再hash法：hi=rhi(key),i=1,2,…，k rhi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
四详细设计。
1、算法流程图。
2、详细**。
1)使用数组data[13]来存储初始的13个数据，然后使用hash[19]线性数组来存储hash过后的数据，采用直接定址法或除留余数法或随机数法来进行hash，采用线性探测再散列法或再哈希法解决冲突。
int data[13]= data用于存待处理的数据。
int hash[19存放hash以后的数据。
int poshash后数据的位置
int collision存放冲突次数。
2)直接定址法：取关键字或关键字的某个线性函数值为散列地址。即h(key)=key或h(key) =a·key + b，其中a和b为常数（这种散列函数叫做自身函数）, hi=(h(key) +di) mod m,i=1,2,…，k(k<=m-1)，其中h(key)为散列函数，m为散列表长，di为增量序列， di=1,2,3,…，m-1，称线性探测再散列。
int hash(int kind, int a, int b, int c散列函数(第一个参数为散列函数类型)
switch(kind)
case 2:
case 3:
3）再hash法：hi=rhi(key),i=1,2,…，k rhi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
int nhash(int pos,int x专用于使用再哈希法处理冲突的hash函数。
return pos * x;
void getabc(int num, int &a, int &b, int &c用来提取三位数三个位的值
a = num / 100;
b = num - a * 100) /10;
c = num % 10;
int coll_handle(int pos, int coll_kind用来解决冲突的函数。
switch(coll_kind){
case 1:{
while(hash[pos线性探测再散列
collision++;
pos++;
pos = pos % 19;
return pos;
break;
case 2再hash法
4）hi=(h(key) +di) mod m,i=1,2,…，k(k<=m-1)，其中h(key)为散列函数，m为散列表长，di为增量序列， di=1,2,3,…，m-1，称线性探测再散列；pos:处理每一个数据时，存放该数据hash后应该在hash数组中的位置，collision:处理每一个数据的时候，冲突的次数。
int hash_kind = m, coll_kind = n分别表示采用的hash函数方式与冲突处理方式
int a, b ,c存放三位数每一位的值
for (int i = 0; i < 13 ; i++)
pos = 0;
getabc(data[i], a, b ,c);
pos = hash(hash_kind, a, b, c) %19;
pos = coll_handle(pos, coll_kind);
hash[pos] =data[i];
for (int t = 0; t < 19; t++)
printf("%d\t",hash[t]);
int result = hash_kind * 10 + coll_kind;
switch(result){
case 11:{
printf("直接定址法+线性探测再散列冲突次数为：%d", collision);
break;
case 12:
printf("直接定制法+在哈希法冲突次数为：%d", collision);
break;
case 21:{
printf("除留余数法+线性探测再散列法冲突次数为：%d", collision);
break;
case 22:{
printf("除留余数法+再哈希法冲突次数为：%d", collision);
break;
4)随机数法：根据关键字设置随机数种子，再用随机数产生函数产生对应数据的位置。
int result = hash_kind * 10 + coll_kind;
switch(result){
case 11:{
printf("直接定址法+线性探测再散列冲突次数为：%d", collision);
break;
case 12:{
printf("直接定制法+在哈希法冲突次数为：%d", collision);
break;
case 21:{
printf("除留余数法+线性探测再散列法冲突次数为：%d", collision);
break;
case 22:{
printf("除留余数法+再哈希法冲突次数为：%d", collision);
break;
case 31:{
printf("随机数法+线性探测再散列法冲突次数为：%d", collision);
break;
case 32:{
printf("随机数法+再哈希法冲突次数为：%d", collision);
break;
五调试分析。
1、运行结果。
如果选择了不合适的hash函数或者不合适的再hash方法，会让程序进入死循环。
六测试结果。
正确的hash函数与冲突处理方法，分别输出了6种不同组合的冲突次数。可以看出最少的是直接定址法加上再哈希法。
七用户使用说明。
根据设计的哈希函数以及两种不同的冲突处理方式，在数据存储的数组中。输入正确的hash函数与冲突方法，并列出不同存储方式的冲突值，从中选出最优的存储方式（冲突值最小的）。
八课程设计总结。
在写这个hash程序的时候，首先了解了hash表的运作原理，同时也熟悉了解了hash表的优势。除此之外，了解了几种不同的hash函数，知道了他们各自的优缺点。意识到了再程序的编写中，许多值得选择是十分重要的。
例如hash函数中除留余数法选择取模的值就很重要，如果不加考虑，很容易让hash函数进入死循环而无法完整执行。
数据结构课程设计报告
东莞理工学院城市学院。题目 二叉排序树 专业 计算机科学与技术 本 年级 2010级计算机科学与技术专业 1 班。个人姓名 何振江。指导教师 张娟老师 时间 2010至2011第二学期第18周 地点 实验楼615机房 东莞理工学院城市学院计算机与信息科学系制。2011年 6月。实习报告的内容。一 问...
数据结构课程设计报告
设计一个校园导游程序，为来访的客人提供信息查询服务。1 设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图 无向网 以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。2 存放景点代号 名称 简介等信息供用户查询。3 为来访客人提供图中任意景点相关信息的查询。4 为来访客人提供...
数据结构课程设计报告
河北科技大学。课程设计报告。学生姓名学号。专业班级。课程名称数据结构。学年学期 2 012 2 013学年第 2 学期指导教师 黄春茹。2 0 13年 6 月。课程设计成绩评定表。一 数据结构课程设计目标。二 问题描述。三 需求分析。四 概要设计。五 详细设计。六 软件说明书 给出软件如何使用，使用...