Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

1 绪论

1.1 项目开发的背景

我们每个活在世上的人，为了能够参与各种社会活动，都需要一个用于识别自己的标志。也许你觉得名字或是身份证就足以代表你这个人，但是这种代表性非常脆弱，因为重名的人很多，身份证也可以伪造。最可靠的办法是把一个人的所有基因序列记录下来用来代表这个人，但显然，这样做并不实际。而指纹看上去是一种不错的选择，虽然一些专业组织仍然可以模拟某个人的指纹，但这种代价实在太高了。

而对于在互联网世界里传送的文件来说，如何标志一个文件的身份同样重要。比如说我们下载一个文件，文件的下载过程中会经过很多网络服务器、路由器的中转，如何保证这个文件就是我们所需要的呢？我们不可能去一一检测这个文件的每个字节，也不能简单地利用文件名、文件大小这些极容易伪装的信息，这时候，我们就需要一种指纹一样的标志来检查文件的可靠性，这种指纹就是我们现在所用的Hash算法(也叫散列算法)。

1.2 项目开发的目的

散列算法（Hash Algorithm），又称哈希算法，杂凑算法，是一种从任意文件中创造小的数字「指纹」的方法。与指纹一样，散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改变，从而告诉文件使用者当前的文件已经不是你所需求的文件。

这种标志有何意义呢？之前文件下载过程就是一个很好的例子，事实上，现在大部分的网络部署和版本控制工具都在使用散列算法来保证文件可靠性。而另一方面，我们在进行文件系统同步、备份等工具时，使用散列算法来标志文件唯一性能帮助我们减少系统开销，这一点在很多云存储服务器中都有应用。

当然，作为一种指纹，散列算法最重要的用途在于给证书、文档、密码等高安全系数的内容添加加密保护。这一方面的用途主要是得益于散列算法的不可逆性，这种不可逆性体现在，你不仅不可能根据一段通过散列算法得到的指纹来获得原有的文件，也不可能简单地创造一个文件并让它的指纹与一段目标指纹相一致。散列算法的这种不可逆性维持着很多安全框架的运营，而这也将是本次课程设计讨论的重点。

2 相关技术介绍

2.1散列表介绍

使用Hash的数据结构叫做散列表，主要是为了提高查询的效率。也有直接译作哈希表，也叫Hash表，

Hash表是一种特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。这个源于Hash表设计的特殊性，它采用了函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。

2.2 Hash算法特点

一个优秀的 hash 算法，将能实现：

（1）正向快速：给定明文和 hash 算法，在有限时间和有限资源内能计算出 hash 值。

（2）逆向困难：给定（若干） hash 值，在有限时间内很难（基本不可能）逆推出明文。

（3）输入敏感：原始输入信息修改一点信息，产生的 hash 值看起来应该都有很大不同。

（4）冲突避免：很难找到两段内容不同的明文，使得它们的 hash 值一致（发生冲突）。即对于任意两个不同的数据块，其hash值相同的可能性极小；对于一个给定的数据块，找到和它hash值相同的数据块极为困难。

2.3 常见的Hash算法

（1）数字分析法

（2）直接定址法

（3）除留余数法

2.4 常见的解决冲突方法

（1）线性探测法

（2）平方取中法

（3）拉链法

3 需求分析

Hash主要应用于数据结构中和密码学中。

用于数据结构时，主要是为了提高查询的效率，这就对速度比较重视，对抗碰撞不太看中，只要保证hash均匀分布就可以。

在密码学中，hash算法的作用主要是用于消息摘要和签名，换句话说，它主要用于对整个消息的完整性进行校验。

我们这里主要研究Hash用于数据结构中的作用。

1. 问题描述

（1）首先需要随机生成中国人姓名的汉字拼音形式。

（2）随机生成3000个人名列表，并保存在文本文件中，在构建哈希表时读入。

（3）实现3种不同的哈希函数，并在建表的时候提供对应的冲突处理方案。

（4）比较不同方法的平均查找长度

2.功能要求

（1）随机姓名生成。

名字的长度不少于3个字符，不多于10个字符，为了符合要求，我们随机选用单姓的拼音加上一个随机的文字拼音组成随机姓名的拼音形式，并保存在文本文件中。

（2）建立Hash表功能。

分别通过直接取址法，平方取中法和除留余数法对姓名拼音的第一个字母，倒数第二个字母，倒数第一个字母的组合公式进行哈希，建立哈希表。

（3）实现Hash查找函数。

实现Hash查找函数并返回查找需要的次数，如果查找失败，返回0。

3.1可行性研究

开发环境

IDE：DevC++

编译器：GNU GCC Compiler

操作系统：Windows 10 64位

3.2需求概述

该程序可以分为以下几个模块：

1.生成随机名字拼音模块：随机生成名字拼音并保存在文本文件中。

2.建立Hash表模块：通过3种不同的算法建立不同的Hash表。

3.查找Hash表模块：通过3种不同的算法对应的查找函数查找Hash表中是否存在我们的名字，并返回查找次数，如果不存在该名字，则返回0。

4.平均查找长度比较模块：通过返回的查找次数求和并求平均数，比较不同的Hash表的查找效率。

4 详细设计

本章是根据软件工程知识，对概要设计的具体实现。通过对每个模块的功能进行描述，绘出功能流程图，编写代码，最终展示出相应的页面。使得整个设计变成一个可运行物理实体，从而达到本次设计的最终目的。

4.1 生成随机姓名拼音

首先，我建立了两个字符串数组name0和name1，分别保存我们所需要用到的姓氏和名字的拼音，一共存储了444个姓氏的拼音和305个名字的拼音。

然后实现了makeName()这个函数，函数通过调用头文件time.h中的随机函数rand()生成随机数，并对随机数分别mod 444和mod 305，获得我们要的数组范围内索引，从两个数组中分别取得姓和名，拼接成我们所要的随机姓名。

同时，我们通过C语言的文件操作，以只写模式打开同目录下的name.txt，并将我们生成的随机姓名存入该文本文件中，一个姓名占据一行，最后关闭文件操作。

流程图如下：

模块函数实现如下：

 

void makeName()
{
    srand((int)time(0));//让我们的随机数根据系统时间变化
    FILE *fp;//建立一个文件操作指针
    if ( (fp=fopen("name.txt","w+"))==NULL)     // 以追加只写模式打开文件操作
    {
        printf("File open error!\n");
    }
    for(int i = 0; i<3000; i++)
    {
        int a = rand()%444;//用来作为姓氏的数组索引
        int b = rand()%305;//用来作为名字的数组索引
        char tempName[12];
        strcpy(tempName,name0[a]);//将随机的姓复制到tempName中
        strcat(tempName,name1[b]);//将随机的名复制到tempName中
        fprintf( fp, "%s\n", tempName  );//将tempName写入文件
    }
    fclose(fp);//关闭文件操作
}

 

 

4.2 建立Hash表模块

我们分别通过不同的方法建立了3个不同的Hash表，分别名为hashmap1，hashmap2，hashmap3，hashmap4，其中hashmap4是hashmap3的补充，即当hashmap3发生冲突时我们的数据会存入hashmap4。

建立三个不同的Hash表我们使用了3个不同的函数，分别名为myHash1(),myHash2(),myHash3(),分别采用了直接取址法、平方取中法、除留余数法进行建表，并在函数中提供了相应的冲突解决方案。

由于我们的名字是由字符串组成，我们希望生成相应的数字用来当哈希表的索引，所以我们在myHash1()中使用公式int k = (a[0]-‘a’)*26*26 + (a[strlen(a)-2]-‘a’)*26 + (a[strlen(a)-1]-‘a’)生成索引。如果发生冲突我们就一直往后找直到找到空位置为止，把数据存到该空位置中。

在myHash2()中使用公式long long int k = (a[0]-‘a’)*26*26 + (a[strlen(a)-2]-‘a’)*26 + (a[strlen(a)-1]-‘a’)生成一个大数k，如果k小于或等于4位数，则直接用k作为索引，如果k大于4位数，则使用k的中间4位作为我们的索引。如果发生冲突我们就一直往后找直到找到空位置为止，把数据存到该空位置中。

在myHash3()中使用公式int k = (a[0]-‘a’)*26*26 + (a[strlen(a)-2]-‘a’)*26 + (a[strlen(a)-1]-‘a’)来生成一个数，并对这个数取mod 2777，其中2777是一个接近我们的数组大小的素数，如果发生冲突我们把冲突的数据按顺序放到hashmap4中。

流程图如下：

模块函数实现如下：

 

void myHash1()
{
    memset(hashmap1,0,sizeof(hashmap1));//将hashmap1字符串数组中所有的字符串置为空
    FILE *fpRead;
    if ( (fpRead=fopen("name.txt","r"))==NULL)     // 打开文件
    {
        printf("File open error!\n");
    }
    char a[12];
    for(int i = 0; i<3000; i++)
    {
        fscanf(fpRead,"%s",&a);//读取name.txt文件的一行给字符串数组a
        int k = (a[0]-'a')*26*26 + (a[strlen(a)-2]-'a')*26 + (a[strlen(a)-1]-'a');
        int index = k;
        while(hashmap1[index][0]!='\0')
        {
            index++;
        }
        strcpy(hashmap1[index],a);//将读取到的a存入hashmap1的该位置
    }
}

void myHash2()
{
    memset(hashmap2,0,sizeof(hashmap2));//将hashmap2字符串数组中所有的字符串置为空
    FILE *fpRead;
    if ( (fpRead=fopen("name.txt","r"))==NULL)     // 打开文件
    {
        printf("File open error!\n");
    }
    char a[12];
    int index = 0;
    for(int i = 0; i<3000; i++)
    {
        fscanf(fpRead,"%s",&a);//读取name.txt文件的一行给字符串数组a
        long long int k = (a[0]-'a')*26*26 + (a[strlen(a)-2]-'a')*26 + (a[strlen(a)-1]-'a');
        k = k*k;//平方
        if(k<10000)
        {
            index = k;
        }
        else//取中
        {
            int dight = getDigit(k);
            for(int i = 0; i<(dight-4)/2 ; i++)
            {
                k = k/10;
            }
            index = k%10000;
        }
        while(hashmap2[index][0]!='\0')
        {
            index++;
        }
        strcpy(hashmap2[index],a);//将a存到对应的位置
    }
}

void myHash3()
{
    int count = 0;
    memset(hashmap3,0,sizeof(hashmap3));//将hashmap3字符串数组中所有的字符串置为空
    memset(hashmap4,0,sizeof(hashmap4));//将hashmap4字符串数组中所有的字符串置为空
    FILE *fpRead;
    if ( (fpRead=fopen("name.txt","r"))==NULL)     // 打开文件
    {
        printf("File open error!\n");
    }
    char a[12];
    int index = 0;
    for(int i = 0; i<3000; i++)
    {
        fscanf(fpRead,"%s",&a);//读取name.txt文件的一行给字符串数组a
        int k = (a[0]-'a')*26*26 + (a[strlen(a)-2]-'a')*26 + (a[strlen(a)-1]-'a');
        index = k%2777;
        if(strlen(hashmap3[index])==0)
        {
            strcpy(hashmap3[index],a);//如果不存在字符串，放进hashmap3对应位置
        }
        else
        {
            strcpy(hashmap4[count],a);//否则放到hashmap4字符串数组中
            count++;
        }
    }
}

 

 

4.3 查找Hash表模块

查找Hash表模块分别用myHash1Find(),myHash2Find(),myHash3Find()三个函数实现,根据建表时的方法和冲突解决方案对应的去查找我们要的数据是否存在，同时都设置了计数器，当找到了我们要的数据时，返回查找次数，否则返回0表示没有找到我们要的数据。

流程图如下：

具体实现如下：

int myHash1Find(char* a) //存在返回查找次数，不存在返回0
{
    int k = (a[0]-'a')*26*26 + (a[strlen(a)-2]-'a')*26 + (a[strlen(a)-1]-'a');
    int temp = k;
    while(1)
    {
        if(strcmp(hashmap1[temp],a)==0)
        {
            return temp-k+1;
        }
        else if(strlen(hashmap1[temp])!=0)
        {
            temp++;
        }
        else
        {
            return 0;
        }
    }
    return temp-k+1;
}

int myHash2Find(char* a) //存在返回查找此时，不存在返回0
{
    long long int k = (a[0]-'a')*26*26 + (a[strlen(a)-2]-'a')*26 + (a[strlen(a)-1]-'a');
    int temp ;
    k = k*k;//平方
    if(k<10000)
    {
        temp = k;
    }
    else//取中
    {
        int dight = getDigit(k);//计算大数k的位数，根据位数来取中间4位数
        for(int i = 0; i<(dight-4)/2 ; i++)
        {
            k = k/10;
        }
        temp = k%10000;
    }
    int num = temp;
    while(1)
    {
        if(strcmp(hashmap2[temp],a)==0)
        {
            return temp-num+1;
        }
        else if(strlen(hashmap2[temp])!=0)
        {
            temp++;
        }
        else
        {
            return 0;
        }
        k++;
    }
}

int myHash3Find(char* a) //存在返回查找此时，不存在返回0
{
    int k = (a[0]-'a')*26*26 + (a[strlen(a)-2]-'a')*26 + (a[strlen(a)-1]-'a');
    int temp = k%2777;
    if(strcmp(hashmap3[temp],a)==0)
    {
        return 1;
    }
    else
    {
        int count = 0;
        while(strlen(hashmap4[count])!=0)
        {
            if(strcmp(hashmap4[count],a)==0)
            {
                return count+1;
            }
            count++;
        }
        return 0;
    }
}

 

 

4.4 平均查找长度模块

平均查找长度模块由函数compareHash实现，分别通过文件操作读入name.txt中的3000个姓名并查找该姓名，将查找次数求和，最后输入查找总次数除以3000即可。

流程图如下：

实现函数如下：

void compareHash() //比较平均查找长度
{
    double hash1Count = 0;//用来存储使用hash1查找函数时用的次数和
    double hash2Count = 0;//用来存储使用hash2查找函数时用的次数和
    double hash3Count = 0;//用来存储使用hash3查找函数时用的次数和
    FILE *fpRead;
    if ( (fpRead=fopen("name.txt","r"))==NULL)     // 打开文件
    {
        printf("File open error!\n");
    }
    char a[12];
    for(int i = 0; i<3000; i++)
    {
        fscanf(fpRead,"%s",&a);//读取name.txt文件的一行给字符串数组a
        hash1Count = hash1Count + myHash1Find(a);
        hash2Count = hash2Count + myHash2Find(a);
        hash3Count = hash3Count + myHash3Find(a);
    }
    printf("hash1算法查找3000个名字的总查找次数为:%.2f\n",hash1Count/3000.00);
    printf("hash2算法查找3000个名字的总查找次数为:%.2f\n",hash2Count/3000.00);
    printf("hash3算法查找3000个名字的总查找次数为:%.2f\n",hash3Count/3000.00);
}

 

5 软件测试与分析

软件测试是软件开发中必不可少的阶段。本章中，通过各种测试方法和多个测试用例，对应用进行测试，以期找出系统中可能导致系统出现问题的地方，使得该应用成为一个稳定的，高效的，能够达到用户标准的应用。

经过多次测试调试，我们的程序可以正常生成随机姓名拼音，hash函数也正常运行。

生成的3000个姓名拼音如下：

效率比较如下：

最终我们发现我们的hash1算法查找效率最高，但使用的空间最多，hash3算法查找效率极低，但使用的空间较少，而hash2算法使用空间较少，效率也比较高。

源代码：maplefan/hashHomeWork