哈希查找，也称为散列查找(本文以哈希称呼)。提起哈希，我的第一印象就是C#中的Hashtable类，它是由一组key/value的键值对组成的集合，它就是应用了散列技术。
 
 那么，什么是哈希查找呢？在弄清楚什么是哈希查找之前，我们要弄清楚哈希技术，哈希技术是在记录的存储位置和记录的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。查找时，根据这个确定的对应关系找到给定值的映射f(key),若查找集合中存在这个记录，则必定在f(key)的位置上。哈希技术既是一种存储方法，也是一种查找方法。
 
 六种哈希函数的构造方法：
 
 1，直接定址法：
 
 函数公式：f(key)=a*key+b (a,b为常数)
 
 这种方法的优点是：简单，均匀，不会产生冲突。但是需要事先知道关键字的分布情况，适合查找表较小并且连续的情况。
 
 2，数字分析法：
 
 比如我们的11位手机号码“136XXXX7887”，其中前三位是接入号，一般对应不同运营公司的子品牌，如130是联通如意通，136是移动神州行，153是电信等。中间四们是HLR识别号，表示用户归属地。最后四们才是真正的用户号。
 
 若我们现在要存储某家公司员工登记表，如果用手机号码作为关键字，那么极有可能前7位都是相同的，所以我们选择后面的四们作为哈希地址就是不错的选择。
 
 3，平方取中法：
 
 故名思义，比如关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为哈希地址。
 
 4，折叠法：
 
 折叠法是将关键字从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些)，然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。
 
 比如我们的关键字是9876543210，哈希表表长三位，我们将它分为四组，987|654|321|0 ，然后将它们叠加求和987+654+321+0=1962，再求后3位即得到哈希地址为962，哈哈，是不是很有意思。
 
 5，除留余数法：
 
 函数公式：f(key)=key mod p (p<=m)m为哈希表表长。
 
 这种方法是最常用的哈希函数构造方法。
 
 6，随机数法：
 
 函数公式：f(key)= random(key)。
 
 这里random是随机函数，当关键字的长度不等是，采用这种方法比较合适。
 
 两种哈希函数冲突解决方法：
 
 我们设计得最好的哈希函数也不可能完全避免冲突，当我们在使用哈希函数后发现两个关键字key1!=key2，但是却有f(key1)=f(key2)，即发生冲突。
 
 方法一：开放定址法：
 
 开放定址法就是一旦发生了冲突，就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总是能找到，然后将记录插入。这种方法是最常用的解决冲突的方法。
 
 方法二：链地址法：
 
 下面是实现代码：
 
 C#版本：
 
 
 

  
 
 
 
namespace HashSearch.CSharp
{
    class Program
    {
        //初始化哈希表
        static int hashLength = 7;
        static int[] hashTable= new int[hashLength];

        //原始数据
        static List<int> list = new List<int>() { 13,29,27,28,26,30,38 };

        static void Main(string[] args)
        {
            Console.WriteLine("********************哈希查找(C#版)********************\n");
            
            //创建哈希表
            for (int i = 0; i < list.Count; i++)
            {
                Insert(hashTable,list[i]);
            }
            Console.WriteLine("展示哈希表中的数据：{0}",String.Join(",",hashTable));

            while (true)
            {
                //哈希表查找
                Console.Write("请输入要查找的数据:");
                int data = int.Parse(Console.ReadLine());
                var result = Search(hashTable, data);
                if (result == -1) Console.WriteLine("对不起，没有找到!");
                else Console.WriteLine("数据的位置是：{0}", result);
            }
        }

        /// <summary>
        /// 哈希表插入
        /// </summary>
        /// <param name="hashTable">哈希表</param>
        /// <param name="data">待插入值</param>
        public static void Insert(int[] hashTable, int data)
        { 
            //哈希函数,除留余数法
            int hashAddress = Hash(hashTable,data);

            //如果不为0，则说明发生冲突
            while (hashTable[hashAddress] != 0)
            {
                //利用开放定址的线性探测法解决冲突
                hashAddress = (++hashAddress) % hashTable.Length;
            }

            //将待插入值存入字典中
            hashTable[hashAddress] = data;
        }

        /// <summary>
        /// 哈希表查找
        /// </summary>
        /// <param name="hashTable">哈希表</param>
        /// <param name="data">待查找的值</param>
        /// <returns></returns>
        public static int Search(int[] hashTable, int data)
        {
            //哈希函数,除留余数法
            int hashAddress = Hash(hashTable,data);

            //冲突发生
            while (hashTable[hashAddress] != data)
            {
                //利用开放定址的线性探测法解决冲突
                hashAddress = (++hashAddress) % hashTable.Length;

                //查找到了开放单元或者循环回到原点，表示查找失败
                if (hashTable[hashAddress] == 0 || hashAddress==Hash(hashTable,data)) return -1;
            }
            //查找成功,返回值的下标
            return hashAddress;
        }

        /// <summary>
        /// 哈希函数(除留余数法)
        /// </summary>
        /// <param name="hashTable">待操作哈希表</param>
        /// <param name="data"></param>
        /// <returns>返回数据的位置</returns>
        public static int Hash(int[] hashTable, int data)
        {
            return data % hashTable.Length;
        }
    }
}
 
 

  
 
 
 
 程序输出结果如图：
 
 
 
  
 
 C语言版：
 
 
 

  
 
 
 
#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define SUCCESS 1
#define UNSUCCESS 0

#define HASHSIZE 7 /* 定义散列表长为数组的长度 */
#define NULLKEY -32768 

typedef int Status;    
typedef struct
{
    int *elem; /* 数据元素存储地址，动态分配数组 */
    int count; /*  当前数据元素个数 */
}HashTable;

int m=0; /* 散列表表长，全局变量 */

/*初始化*/
Status Init(HashTable *hashTable)
{
    int i;

    m=HASHSIZE;
    hashTable->elem= (int *)malloc(m*sizeof(int)); //申请内存
    hashTable->count=m;
    for (i=0;i<m;i++)
    {
        hashTable->elem[i]=NULLKEY;
    }
    return OK;
}

/*哈希函数(除留余数法)*/
int Hash(int data)
{
    return data%m;
}

/*插入*/
void Insert(HashTable *hashTable,int data)
{
    int hashAddress=Hash(data); //求哈希地址

    //发生冲突
    while(hashTable->elem[hashAddress]!=NULLKEY)
    {
        //利用开放定址的线性探测法解决冲突
        hashAddress=(++hashAddress)%m;
    }

    //插入值
    hashTable->elem[hashAddress]=data;
}

/*查找*/
int Search(HashTable *hashTable,int data)
{
    int hashAddress=Hash(data); //求哈希地址

    //发生冲突
    while(hashTable->elem[hashAddress]!=data)
    {
        //利用开放定址的线性探测法解决冲突
        hashAddress=(++hashAddress)%m;

        if (hashTable->elem[hashAddress]==NULLKEY||hashAddress==Hash(data)) return -1;
    }

    //查找成功
    return hashAddress;
}

/*打印结果*/
void Display(HashTable *hashTable)
{
    int i;
    printf("\n**********展示结果**********\n");

    for (i=0;i<hashTable->count;i++)
    {
        printf("%d ",hashTable->elem[i]);
    }

    printf("\n**********展示完毕**********\n");
}

void main()
{
    int i,j,result;
    HashTable hashTable;
    int arr[HASHSIZE]={13,29,27,28,26,30,38};

    printf("***************哈希查找(C语言版)***************\n");

    //初始化哈希表
    Init(&hashTable);

    //插入数据
    for (i=0;i<HASHSIZE;i++)
    {
        Insert(&hashTable,arr[i]);
    }
    Display(&hashTable);

    //查找数据
    result= Search(&hashTable,29);
    if (result==-1) printf("对不起，没有找到！");
    else printf("29在哈希表中的位置是:%d",result);

    getchar();
}
 
 

  
 
 
 
 程序输出结果如图：
 
 
 
 -------------------------------------------------
 
 
 
 Hash算法
 
 
 
　　Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
 
 
 
 
　　HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系
 
 
 基本概念
 
 
　　　* 若结构中存在和关键字K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。
 
 
 
 
　　* 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。
 
 
 
 
　　* 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
 
 
 常用的构造散列函数的方法
 
 
　　散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位ǐ
 
 
 
 
　　1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）
 
 
 
 
　　2. 数字分析法
 
 
 
 
　　3. 平方取中法
 
 
 
 
　　4. 折叠法
 
 
 
 
　　5. 随机数法
 
 
 
 
　　6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
 
 
 处理冲突的方法
 
 
　　1. 开放寻址法；Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：
 
 
 
 
　　1. di=1,2,3,…, m-1，称线性探测再散列；
 
 
 
 
　　2. di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列;
 
 
 
 
　　3. di=伪随机数序列，称伪随机探测再散列。 ==
 
 
 
 
　　2. 再散列法：Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
 
 
 
 
　　3. 链地址法(拉链法)
 
 
 
 
　　4. 建立一个公共溢出区
 
 
 查找的性能分析
 
 
　　
 
 
 
 
　　散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。
 
 
 
 
　　查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：
 
 
 
 
　　1. 散列函数是否均匀；
 
 
 
 
　　2. 处理冲突的方法；
 
 
 
 
　　3. 散列表的装填因子。
 
 
 
 
　　散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度
 
 
 
 
　　α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。
 
 
 
 
　　实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。
 
 
 
 
　　了解了hash基本定义，就不能不提到一些著名的hash算法，MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。那么他们都是什么意思呢?
 
 
 
 
　　这里简单说一下：
 
 
 
 
　　（1) MD4
 
 
 
 
　　MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。
 
 
 
 
　　（2) MD5
 
 
 
 
　　MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好
 
 
 
 
　　（3) SHA-1及其他
 
 
 
 
　　SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。
 
 
 
 
　　那么这些Hash算法到底有什么用呢?
 
 
 
 
　　Hash算法在信息安全方面的应用主要体现在以下的3个方面：
 
 
 
 
　　（1) 文件校验
 
 
 
 
　　我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。
 
 
 
 
　　MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。
 
 
 
 
　　（2) 数字签名
 
 
 
 
　　Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。 对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。
 
 
 
 
　　（3) 鉴权协议
 
 
 
 
　　如下的鉴权协议又被称作挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。以上就是一些关于hash以及其相关的一些基本预备知识。那么在emule里面他具体起到什么作用呢?
 
 
 
 
　　MD5、SHA1的破解
 
 
 
 
　　2004年8月17日，在美国加州圣芭芭拉召开的国际密码大会上，山东大学王小云教授在国际会议上首次宣布了她及她的研究小组近年来的研究成果——对MD5、HAVAL－128、MD4和RIPEMD等四个著名密码算法的破译结果。 次年二月宣布破解SHA-1密码。
 
 
 
 
 
 
 编辑本段散列函数的性质
 
 
　　所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面，散列函数的输入和输出不是一一对应的，如果两个散列值相同，两个输入值很可能是相同的，但并不能绝对肯定二者一定相等。输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。
 
 
 
 
　　典型的散列函数都有无限定义域，比如任意长度的字节字符串，和有限的值域,比如固定长度的比特串。在某些情况下，散列函数可以设计成具有相同大小的定义域和值域间的一一对应。一一对应的散列函数也称为排列。可逆性可以通过使用一系列的对于输入值的可逆“混合”运算而得到。求。到2007年为止，第三版还未完备。
 
 
 
 
 
 
 编辑本段散列函数的应用
 
 
　　由于散列函数的应用的多样性，它们经常是专为某一应用而设计的。例如，加密散列函数假设存在一个要找到具有相同散列值的原始输入的敌人。一个设计优秀的加密散列函数是一个“单向”操作：对于给定的散列值，没有实用的方法可以计算出一个原始输入，也就是说很难伪造。为加密散列为目的设计的函数，如MD5，被广泛的用作检验散列函数。这样软件下载的时候，就会对照验证代码之后才下载正确的文件部分。此代码有可能因为环境因素的变化，如机器配置或者IP地址的改变而有变动。以保证源文件的安全性。
 
 
 
 
　　错误监测和修复函数主要用于辨别数据被随机的过程所扰乱的事例。当散列函数被用于校验和的时候，可以用相对较短的散列值来验证任意长度的数据是否被更改过。
 
 
 
 
 
 
 编辑本段散列表
 
 
　　散列表是散列函数的一个主要应用，使用散列表能够快速的按照关键字查找数据记录。（注意：关键字不是像在加密中所使用的那样是秘密的，但它们都是用来“解锁”或者访问数据的。）例如，在英语字典中的关键字是英文单词，和它们相关的记录包含这些单词的定义。在这种情况下，散列函数必须把按照字母顺序排列的字符串映射到为散列表的内部数组所创建的索引上。
 
 
 
 
　　散列表散列函数的几乎不可能/不切实际的理想是把每个关键字映射到唯一的索引上（参考完美散列），因为这样能够保证直接访问表中的每一个数据。
 
 
 
 
　　一个好的散列函数（包括大多数加密散列函数）具有均匀的真正随机输出，因而平均只需要一两次探测（依赖于装填因子）就能找到目标。同样重要的是，随机散列函数几乎不可能出现非常高的冲突率。但是，少量的可以估计的冲突在实际状况下是不可避免的（参考生日悖论）。
 
 
 
 
　　在很多情况下，heuristic散列函数所产生的冲突比随机散列函数少的多。Heuristic函数利用了相似关键字的相似性。例如，可以设计一个heuristic函数使得像FILE0000.CHK, FILE0001.CHK, FILE0002.CHK, 等等这样的文件名映射到表的连续指针上，也就是说这样的序列不会发生冲突。相比之下，对于一组好的关键字性能出色的随机散列函数，对于一组坏的关键字经常性能很差，这种坏的关键字会自然产生而不仅仅在攻击中才出现。性能不佳的散列函数表意味着查找操作会退化为费时的线性搜索。
 
 
 
 
 
 
 编辑本段错误校正
 
 
　　使用一个散列函数可以很直观的检测出数据在传输时发生的错误。在数据的发送方，对将要发送的数据应用散列函数，并将计算的结果同原始数据一同发送。在数据的接收方，同样的散列函数被再一次应用到接收到的数据上，如果两次散列函数计算出来的结果不一致，那么就说明数据在传输的过程中某些地方有错误了。这就叫做冗余校验。
 
 
 
 
　　对于错误校正，假设相似扰动的分布接近最小(a distribution of likely perturbations is assumed at least approximately)。对于一个信息串的微扰可以被分为两类，大的（不可能的）错误和小的（可能的）错误。我们对于第二类错误重新定义如下，假如给定 H(x) 和 x+s，那么只要s足够小，我们就能有效的计算出x。那样的散列函数被称作错误校正编码。这些错误校正编码有两个重要的分类：循环冗余校验和里德所罗门码。
 
 
 
 
 
 
 编辑本段语音识别
 
 
　　对于像从一个已知列表中匹配一个MP3文件这样的应用，一种可能的方案是使用传统的散列函数——例如MD5，但是这种方案会对时间平移、CD读取错误、不同的音频压缩算法或者音量调整的实现机制等情况非常敏感。使用一些类似于MD5的方法有利于迅速找到那些严格相同（从音频文件的二进制数据来看）的音频文件，但是要找到全部相同（从音频文件的内容来看）的音频文件就需要使用其他更高级的算法了。
 
 
 
 
　　那些并不紧随IT工业潮流的人往往能反其道而行之，对于那些微小差异足够鲁棒的散列函数确实存在。现存的绝大多数散列算法都是不够鲁棒的，但是有少数散列算法能够达到辨别从嘈杂房间里的扬声器里播放出来的音乐的鲁棒性。有一个实际的例子是Shazam[1]服务。用户可以用电话机拨打一个特定的号码，并将电话机的话筒靠近用于播放音乐的扬声器。该项服务会分析正在播放的音乐，并将它于存储在数据库中的已知的散列值进行比较。用户就能够收到被识别的音乐的曲名（需要收取一定的费用）
 
 
 
 
　　什么是文件的hash值呢?
 
 
 
 
　　大家都知道emule是基于P2P （Peer-to-peer的缩写，指的是点对点的意思的软件）， 它采用了"多源文件传输协议”(MFTP，the Multisource FileTransfer Protocol)。在协议中，定义了一系列传输、压缩和打包还有积分的标准，emule 对于每个文件都有md5-hash的算法设置，这使得该文件独一无二，并且在整个网络上都可以追踪得到。
 
 
 
 
　　MD5-Hash-文件的数字文摘通过Hash函数计算得到。不管文件长度如何，它的Hash函数计算结果是一个固定长度的数字。与加密算法不同，这一个Hash算法是一个不可逆的单向函数。采用安全性高的Hash算法，如MD5、SHA时，两个不同的文件几乎不可能得到相同的Hash结果。因此，一旦文件被修改，就可检测出来。
 
 
 
 
　　当我们的文件放到emule里面进行共享发布的时候，emule会根据hash算法自动生成这个文件的hash值，他就是这个文件唯一的身份标志，它包含了这个文件的基本信息,然后把它提交到所连接的服务器。当有他人想对这个文件提出下载请求的时候， 这个hash值可以让他人知道他正在下载的文件是不是就是他所想要的。尤其是在文件的其他属性被更改之后（如名称等）这个值就更显得重要。而且服务器还提供了,这个文件当前所在的用户的地址,端口等信息,这样emule就知道到哪里去下载了。
 
 
 
 
　　一般来讲我们要搜索一个文件，emule在得到了这个信息后，会向被添加的服务器发出请求，要求得到有相同hash值的文件。而服务器则返回持有这个文件的用户信息。这样我们的客户端就可以直接的和拥有那个文件的用户沟通，看看是不是可以从他那里下载所需的文件。
 
 
 
 
　　对于emule中文件的hash值是固定的，也是唯一的，它就相当于这个文件的信息摘要，无论这个文件在谁的机器上，他的hash值都是不变的，无论过了多长时间，这个值始终如一，当我们在进行文件的下载上传过程中，emule都是通过这个值来确定文件。
 
 
 
 
　　那么什么是userhash呢?
 
 
 
 
　　道理同上，当我们在第一次使用emule的时候，emule会自动生成一个值，这个值也是唯一的，它是我们在emule世界里面的标志，只要你不卸载，不删除config，你的userhash值也就永远不变，积分制度就是通过这个值在起作用，emule里面的积分保存，身份识别，都是使用这个值，而和你的id和你的用户名无关，你随便怎么改这些东西，你的userhash值都是不变的，这也充分保证了公平性。其实他也是一个信息摘要，只不过保存的不是文件信息，而是我们每个人的信息。
 
 
 
 
　　那么什么是hash文件呢?
 
 
 
 
　　我们经常在emule日至里面看到，emule正在hash文件，这里就是利用了hash算法的文件校验性这个功能了，文章前面已经说了一些这些功能，其实这部分是一个非常复杂的过程，目前在ftp,bt等软件里面都是用的这个基本原理，emule里面是采用文件分块传输，这样传输的每一块都要进行对比校验，如果错误则要进行重新下载，这期间这些相关信息写入met文件，直到整个任务完成，这个时候part文件进行重新命名，然后使用move命令，把它传送到incoming文件里面，然后met文件自动删除，所以我们有的时候会遇到hash文件失败，就是指的是met里面的信息出了错误不能够和part文件匹配，另外有的时候开机也要疯狂hash，有两种情况一种是你在第一次使用，这个时候要hash提取所有文件信息，还有一种情况就是上一次你非法关机，那么这个时候就是要进行排错校验了。
 
 
 
 
　　关于hash的算法研究，一直是信息科学里面的一个前沿，尤其在网络技术普及的今天，他的重要性越来越突出，其实我们每天在网上进行的信息交流安全验证，我们在使用的操作系统密钥原理，里面都有它的身影，特别对于那些研究信息安全有兴趣的朋友，这更是一个打开信息世界的钥匙，他在hack世界里面也是一个研究的焦点。
 
 
 
 
　　常用HASH函数
 
 
 
 
　　·直接取余法： f(x):= x mod maxM ; maxM一般是不太接近 2^t 的一个质数。
 
 
 
 
　　·乘法取整法： f(x):=trunc((x/maxX)*maxlongit) mod maxM，主要用于实数。
 
 
 
 
　　·平方取中法： f(x):=(x*x div 1000 ) mod 1000000); 平方后取中间的，每位包含信息比较多。
 
 

 

一、散列查找的基本思想：
 
散列技术：
 
在记录的存储位置和它的关键码key之间建立一个确定的对应关系H，使得每个关键字key和唯一的存储位置H(key)相对应。存储记录时，根据这个对应关系找到关键码的映射地址，并按此地址存储该记录；查找记录时，根据这个对应关系找到待查关键码的映射地址，并按此地址访问该记录，这种查找技术就称为散列技术。采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表；将关键码映射为散列表中适当位置的函数称为散列函数，所得的存储位置称为散列地址。
 
散列技术需要考虑的两个问题：
 
1.散列函数的设计。力求简单、均匀、存储利用率高的散列函数。
 
2.冲突的处理。
 
二、散列函数的设计。
 
散列函数遵循的基本原则：
 
1.计算简单。散列函数应该不是很大的计算量，否则会降低查找效率。
 
2.函数值（即散列地址）分布均匀，希望散列函数能够把记录以相同的概率散列到散列表的所有地址空间中，这样才能保证存储空间的有效利用，并减少冲突。
 
三种常见的散列函数：
 
直接定址法：
 
直接定址法的散列函数是关键码的线性函数，即H(key) = a x key + b , 其中a, b为常数。
 
例如：关键码集合为{10,30,50,70,80}，选取的散列函数为H（key） = key / 10,则散列表如下图所示：
 
 
评价：
 
直接定址法的特点是不会产生冲突，但实际应用中能使用这种散列函数的情况很少，它适用于事先知道关键码的分布，关键码结合不是很大且连续性较好的情况。
 
除留余数法：
 
除留余数法的基本思想是选择某个适当的正整数p,以关键码除以p的余数作为散列地址。
 
H(key) = key mod p.
 
一般情况下，如果散列表的长度为m， 通常选p为小于或等于表长(最好接近m)的最小素数或不包含小于20质因子的合数。
 
评价：
 
除留余数法是一种最简单、也是最常用的构造散列函数的方法，并且这种方法不要求事先知道关键码的分布。
 
 
 
平方取中法：
 
平方取中法是对关键码平方后，按散列表大小，取中间的若干位作为散列地址（简称平方后截取）。
 
之所以这样，是因为一个数平方后，中间的几位分布较均匀，从而冲突发生的概率较小。
 
例如：关键码1234，假设散列地址是2位，1234^2 = 1522756，选取中间的2位作为散列地址，可以选22，也可以选27.
 
三、处理冲突的方法
 
1.开放定址法：
 
用开发定址法处理冲突得到的散列表叫做闭散列表。
 
开放地址法处理冲突的方法是，如果关键码得到的散列地址产生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，他的散列地址总能找到，并将记录存入。找下一个空散列地址的方法通常有线性探测法和二次探测法。
 
1.1线性探测法：
 
当冲突发生时，线性探测法从冲突位置的下一个位置起，依次寻找空的散列地址，对于键值key，闭散列表的长度为m, 发生冲突时，寻找下一个散列地址的公式为：
 
(H(key) + di) % m               (di = 1,2,3 ,4,...m-1)
 
1.2二次探测法
 
2.拉链法（链地址法）
 
用拉链法处理冲突构造的散列表叫做开散列表。
 
四、散列查找的性能分析
 
影响冲突概率的主要三个因素：
 
1.散列函数是否均匀。
 
2.处理冲突的方法。
 
3.散列表的装填因子。
 
开散列表和闭散列表的比较：
 
 
 
未完待续...

 
 

  
　　
 
  
Hash表的“查找成功的ASL”和“查找不成功的ASL”
 
  
ASL指的是 平均查找时间
 
  
关键字序列：（7、8、30、11、18、9、14）
 
  
散列函数： 
H(Key) = (key x 3) MOD 7
 
  
装载因子： 
0.7
 
  
处理冲突：线性探测再散列法
 
  

  
查找成功的ASL计算方法：
 
  

以下求解过程是按照“计算机统考的计算方法”，不同的老师、教材在“处理冲突”上可能会有不同的方法，所以最主要的是掌握原理即可，对于考研的朋友最好掌握统考真题的解题方法。 
 
  
题目 
例子：（2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题第一题）
 
  
将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为： H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。 
(1) 请画出所构造的散列表； 
(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 
1.散列表： 
α = 表中填入的记录数/哈希表长度 ==> 哈希表长度 = 7/0.7 = 10 
H(7) = (7x3) MOD 7 = 0 H(8) = (8x3) MOD 7 = 3 H(30) = (30x3) MOD 7 = 6 
H(11) = (11x3) MOD 7 = 5 H(18) = (18x3) MOD 7 = 5 H(9) = (9x3) MOD 7 = 6 
H(14) = (14x3) MOD 7 = 0 
按关键字序列顺序依次向哈希表中填入，发生冲突后按照“线性探测”探测到第一个空位置填入。 
 
  
因为现在的数据是7个，填充因子是0.7。所以数组大小=7/0.7=10，即写出来的散列表大小为10，下标从0~9。 
第一个元素7，带入散列函数，计算得0。 
第二个元素8，带入散列函数，计算得3。 
第三个元素30，带入散列函数，计算得6。 
第四个元素11，带入散列函数，计算得5。 
第五个元素18，带入散列函数，计算得5；此时和11冲突，使用线性探测法，得7。 
第六个元素9，带入散列函数，计算得6；此时和30冲突，使用线性探测法，得8。 
第七个元素14，带入散列函数，计算得0；此时和7冲突，使用线性探测法，得1。 
所以散列表：
 
  
 
 
  
地址
0
1
2
3
4
5
6
7
8
9
key
7
14
 
8
 
11
30
18
9
 


  

2.查找长度： 
2.1 查找成功的平均查找长度 
（待查找的数字肯定在散列表中才会查找成功） 
查找数字A的长度 = 需要和散列表中的数比较的次数； 
步骤： 
比如 查找数字：8 
则 H(8) = (8x3) MOD 7 = 3 
哈希表中地址3处的数字为8，进行了第一次比较：8 = 8，则查找成功，查找长度为1； 
比如查找数字：14 
则 H(14) = (14x3) MOD 7 = 0 
哈希表中地址0处的数字为7，进行第一次比较：7≠14 
哈希表中地址1处的数字为14，进行第二次比较：14=14 ，则查找成功，查找长度为2。 
由此可得到如下数据：【2016年12月26日修改，多谢@一楼的朋友指正】 
0 1 2 3 4 5 6 7 8 9 
7 14 8 11 30 18 9 
1 2 1 1 1 3 3 
所以总的查找成功的平均查找长度= （1+1+1+1+3+3+2）/7 = 12/7 
2.2查找不成功的平均查找长度 
（待查找的数字肯定不在散列表中） 
【解题的关键之处】根据哈希函数地址为MOD7，因此任何一个数经散列函数计算以后的初始地址只可能在0~6的位置 
查找0~6位置查找失败的查找次数为： 
地址0，到第一个关键字为空的地址2需要比较3次，因此查找不成功的次数为3. 
地址1，到第一个关键字为空的地址2需要比较2次，因此查找不成功的次数为2. 
地址2，到第一个关键字为空的地址2需要比较1次，因此查找不成功的次数为1. 
地址3，到第一个关键字为空的地址4需要比较2次，因此查找不成功的次数为2. 
地址4，到第一个关键字为空的地址4需要比较1次，因此查找不成功的次数为1. 
地址5，到第一个关键字为空的地址2(比较到地址6，再循环回去)需要比较5次，因此查找不成功的次数为5. 
地址6，到第一个关键字为空的地址2(比较到地址6，再循环回去)需要比较4次，因此查找不成功的次数为4. 
于是得到如下数据： 
0 1 2 3 4 5 6 7 8 9 
7 14 8 11 30 18 9 
3 2 1 2 1 5 4 
则查找不成功的平均查找长度 = （3+2+1+2+1+5+4）/7 = 18/7
 
  
二.hash算法原理详解
 
  
一.概念
 
  
 
 
  
哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。
 
  
哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
 
  
使用哈希查找有两个步骤:
 
  
1. 使用哈希函数将被查找的键转换为数组的索引。在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突
 
  
2. 处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法，本文后面会介绍拉链法和线性探测法。
 
  
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
 
  
 
 
  
 
 
  
在Hash表中，记录在表中的位置和其关键字之间存在着一种确定的关系。这样我们就能预先知道所查关键字在表中的位置，从而直接通过下标找到记录。使ASL趋近与0.
 
  
 
 
  
              1)   哈希(Hash)函数是一个映象，即： 将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地       址集合的大小不超出允许范围即可；
 
  
             2)  由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1！=key2，而  f  (key1) = f(key2)。
 
  
              3).  只能尽量减少冲突而不能完全避免冲突，这是因为通常关键字集合比较大，其元素包括所有可能的关键字， 而地址集合的元素仅为哈希表中的地址值
 
  
 
 
  
       在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一 种“处理冲突” 的方法。
 
  
 
 
  
二.Hash构造函数的方法
 
  
 
 
  
   1.直接定址法：
 
  
                         
 
  
 直接定址法是以数据元素关键字k本身或它的线性函数作为它的哈希地址，即：H（k）=k  或 H（k）=a×k+b ； (其中a,b为常数)
 
  
  例1，有一个人口统计表，记录了从1岁到100岁的人口数目，其中年龄作为关键字，哈希函数取关键字本身，如图(1)：
 
  
 
地址
 
 
A1
 
 
A2
 
 
……
 
 
A99
 
 
A100
 
 
年龄
 
 
1
 
 
2
 
 
……
 
 
99
 
 
100
 
 
人数
 
 
980
 
 
800
 
 
……
 
 
495
 
 
107
 
  
可以看到，当需要查找某一年龄的人数时，直接查找相应的项即可。如查找99岁的老人数，则直接读出第99项即可。
 
  
 
 
  
 
地址
 
 
A0
 
 
A1
 
 
……
 
 
A99
 
 
A100
 
 
年龄
 
 
1980
 
 
1981
 
 
……
 
 
1999
 
 
2000
 
 
人数
 
 
980
 
 
800
 
 
……
 
 
495
 
 
107
 
  
 
 
  
如果我们要统计的是80后出生的人口数，如上表所示，那么我们队出生年份这个关键字可以用年份减去1980来作为地址，此时f(key)=key-1980
 
  
这种哈希函数简单，并且对于不同的关键字不会产生冲突，但可以看出这是一种较为特殊的哈希函数，实际生活中，关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费，因此这种方法适应性并不强。[2]↑
 
  
  此法仅适合于：地址集合的大小 = = 关键字集合的大小，其中a和b为常数。
 
  
 
 
  
 
 
  
2.数字分析法：
 
  
             假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。
 
  
数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时，可以通过对关键字的各位进行分析，丢掉分布不均匀的位，作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。
 
  
   例2，要构造一个数据元素个数n=80,哈希长度m=100的哈希表。不失一般性，我们这里只给出其中8个关键字进行分析，8个关键字如下所示：
 
  
K1=61317602      K2=61326875      K3=62739628      K4=61343634
 
  
K5=62706815      K6=62774638      K7=61381262      K8=61394220
 
  
分析上述8个关键字可知，关键字从左到右的第1、2、3、6位取值比较集中，不宜作为哈希地址，剩余的第4、5、7、8位取值较均匀，可选取其中的两位作为哈希地址。设选取最后两位作为哈希地址，则这8个关键字的哈希地址分别为：2，75，28，34，15，38，62，20。           
 
  
 
 
  
 此法适于:能预先估计出全体关键字的每一位上各种数字出现的频度。
 
  
             
 
  
3.折叠法：
 
  
            将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：移位叠加:将分 割后的几部分低位对齐相加；边界叠加:从一端沿分割界来回折叠，然后对齐相加。
 
  
所谓折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位），这方法称为折叠法。这种方法适用于关键字位数较多，而且关键字中每一位上数字分布大致均匀的情况。
 
  
  折叠法中数位折叠又分为移位叠加和边界叠加两种方法，移位叠加是将分割后是每一部分的最低位对齐，然后相加；边界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。
 
  
例4，当哈希表长为1000时，关键字key=110108331119891，允许的地址空间为三位十进制数，则这两种叠加情况如图：
 
  
       移位叠加                                 边界叠加
 
  
       8 9 1                                     8 9 1
 
  
       1 1 9                                     9 1 1
 
  
       3 3 1                                     3 3 1
 
  
       1 0 8                                     8 0 1
 
  
    +  1 1 0                                   + 1 1 0              
 
  
   (1) 5 5 9                                  (3)0 4 4
 
  
                 图（2）由折叠法求哈希地址
 
  
     用移位叠加得到的哈希地址是559，而用边界叠加所得到的哈希地址是44。如果关键字不是数值而是字符串，则可先转化为数。转化的办法可以用ASCⅡ字符或字符的次序值。
 
  
            此法适于：关键字的数字位数特别多。
 
  
 
 
  
4.平方取中法
 
  
  这是一种常用的哈希函数构造方法。这个方法是先取关键字的平方，然后根据可使用空间的大小，选取平方数是中间几位为哈希地址。
 
  
哈希函数 H(key)=“key2的中间几位”因为这种方法的原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。
 
  
例5，若设哈希表长为1000则可取关键字平方值的中间三位，如图所示：
 
  
 
关键字
 
 
关键字的平方
 
 
哈希函数值
 
 
1234
 
 
1522756
 
 
227
 
 
2143
 
 
4592449
 
 
924
 
 
4132
 
 
17073424
 
 
734
 
 
3214
 
 
10329796
 
 
297 
 
  
  
 
  
下面给出平方取中法的哈希函数
 
  
     //平方取中法哈希函数，结设关键字值32位的整数
 
  
     //哈希函数将返回key * key的中间10位
 
  
       Int  Hash (int key)
 
  
         {
 
  
     //计算key的平方
 
  
      Key * = key ;
 
  
     //去掉低11位
 
  
     Key>>=11;
 
  
     // 返回低10位（即key * key的中间10位）
 
  
       Return key %1024;
 
  
          }
 
  
   此法适于:关键字中的每一位都有某些数字重复出现频度很高的现象
 
  
 
 
  
 
 
  
5.减去法
 
  
 
 
  
 
 
  
减去法是数据的键值减去一个特定的数值以求得数据存储的位置。
 
  
例7，公司有一百个员工，而员工的编号介于1001到1100，减去法就是员工编号减去1000后即为数据的位置。编号1001员工的数据在数据中的第一笔。编号1002员工的数据在数据中的第二笔…依次类推。从而获得有关员工的所有信息，因为编号1000以前并没有数据，所有员工编号都从1001开始编号。
 
  
 
 
  
 
 
  
6.基数转换法
 
  
  将十进制数X看作其他进制，比如十三进制，再按照十三进制数转换成十进制数，提取其中若干为作为X的哈希值。一般取大于原来基数的数作为转换的基数，并且两个基数应该是互素的。
 
  
 
 
  
例Hash(80127429)=(80127429)13=8*137+0*136+1*135+2*134+7*133+4*132+2*131+9=(502432641)10如果取中间三位作为哈希值，得Hash（80127429）=432
 
  
 为了获得良好的哈希函数，可以将几种方法联合起来使用，比如先变基，再折叠或平方取中等等，只要散列均匀，就可以随意拼凑。
 
  
 
 
  
 
 
  
 
 
  
  7.除留余数法：
 
  
            
 
  
假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为
 
  
h（k）=k  %  p ，其中%为模p取余运算。
 
  
例如，已知待散列元素为（18，75，60，43，54，90，46），表长m=10，p=7，则有
 
  
    h(18)=18 % 7=4    h(75)=75 % 7=5    h(60)=60 % 7=4   
 
  
    h(43)=43 % 7=1    h(54)=54 % 7=5    h(90)=90 % 7=6   
 
  
    h(46)=46 % 7=4
 
  
此时冲突较多。为减少冲突，可取较大的m值和p值，如m=p=13，结果如下：
 
  
    h(18)=18 % 13=5    h(75)=75 % 13=10    h(60)=60 % 13=8    
 
  
    h(43)=43 % 13=4    h(54)=54 % 13=2    h(90)=90 % 13=12   
 
  
    h(46)=46 % 13=7
 
  
此时没有冲突，如图8.25所示。
 
  
 
 
  
0      1      2     3     4     5      6     7     8     9     10     11    12
 
  
 
 
  
 
   
 
 
 
 
 
 
 
54
 
 
 
 
 
43
 
 
18
 
 
 
 
 
46
 
 
60
 
 
 
 
 
75
 
 
 
 
 
90
 
  
 
  
                      
 
  
 
 
  
除留余数法求哈希地址
 
  
 
 
  
 
 
  
理论研究表明，除留余数法的模p取不大于表长且最接近表长m素数时效果最好，且p最好取1.1n～1.7n之间的一个素数（n为存在的数据元素个数）
 
  
 
 
  
 
 
  
8.随机数法：
 
  
           设定哈希函数为:H(key) = Random(key)其中，Random 为伪随机函数
 
  
           此法适于：对长度不等的关键字构造哈希函数。
 
  
 
 
  
         实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，以及哈希表    长度（哈希地址范围），总的原则是使产生冲突的可能性降到尽可能地小。
 
  
 
 
  
9．随机乘数法
 
  
  亦称为“乘余取整法”。随机乘数法使用一个随机实数f,0≤f<1,乘积f*k的分数部分在0～1之间，用这个分数部分的值与n（哈希表的长度）相乘，乘积的整数部分就是对应的哈希值，显然这个哈希值落在0～n-1之间。其表达公式为：Hash(k)=「n*(f*k%1)」其中“f*k%1”表示f*k 的小数部分，即f*k%1=f*k-「f*k」
 
  
  例10，对下列关键字值集合采用随机乘数法计算哈希值，随机数f=0.103149002 哈希表长度n=100得图：
 
  
 
 
  
 
k
 
 
f*k
 
 
n*((f*k)的小数部分)
 
 
Hash(k)
 
 
319426
 
 
32948.47311
 
 
47.78411
 
 
47
 
 
718309
 
 
74092.85648
 
 
86.50448
 
 
86
 
 
629443
 
 
64926.41727
 
 
42.14427
 
 
42
 
 
919697
 
 
84865.82769
 
 
83.59669
 
 
83
 
  
  此方法的优点是对n的选择不很关键。通常若地址空间为p位就是选n=2p.Knuth对常数f的取法做了仔细的研究，他认为f取任何值都可以，但某些值效果更好。如f=（-1）/2=0.6180329...比较理想。
 
  
 
 
  
10．字符串数值哈希法
 
  
在很都情况下关键字是字符串，因此这样对字符串设计Hash函数是一个需要讨论的问题。下列函数是取字符串前10个字符来设计的哈希函数
 
  
Int Hash _ char (char *X)
 
  
{
 
  
  int I ,sum
 
  
  i=0;
 
  
  while (i 10 && X[i])
 
  
  Sum +=X[i++];
 
  
  sum%=N;      //N是记录的条数
 
  
  }
 
  
这种函数把字符串的前10个字符的ASCⅡ值之和对N取摸作为Hash地址，只要N较小，Hash地址将较均匀分布[0，N]区间内，因此这个函数还是可用的。对于N很大的情形，可使用下列函数
 
  
int ELFhash (char *key )
 
  
{
 
  
 Unsigned long h=0,g;
 
  
whie (*key)
 
  
{
 
  
h=(h<<4)+ *key;
 
  
key++;
 
  
g=h & 0 xF0000000L;
 
  
if (g) h^=g>>24;
 
  
h & =～g;
 
  
}
 
  
h=h % N
 
  
return （h）;
 
  
}
 
  
  这个函数称为ELFHash(Exextable and Linking Format ,ELF,可执行链接格式)函数。它把一个字符串的绝对长度作为输入，并通过一种方式把字符的十进制值结合起来，对长字符串和短字符串都有效，这种方式产生的位置不可能不均匀分布。
 
  
 
 
  
11.旋转法
 
  
  旋转法是将数据的键值中进行旋转。旋转法通常并不直接使用在哈希函数上，而是搭配其他哈希函数使用。
 
  
  例11，某学校同一个系的新生（小于100人）的学号前5位数是相同的，只有最后2位数不同，我们将最后一位数，旋转放置到第一位，其余的往右移。
 
  
 
新生学号
 
 
旋转过程
 
 
旋转后的新键值
 
 
5062101
 
 
5062101
 
 
1506210
 
 
5062102
 
 
5062102
 
 
2506210
 
 
5062103
 
 
5062103
 
 
3506210
 
 
5062104
 
 
5062104
 
 
4506210
 
 
5062105
 
 
5062105
 
 
5506210
 
  
                    如图
 
  
 运用这种方法可以只输入一个数值从而快速地查到有关学生的信息。
 
  
 
 
  
 
 
  
在实际应用中，应根据具体情况，灵活采用不同的方法，并用实际数据测试它的性能，以便做出正确判定。通常应考虑以下五个因素 ：
 
  
l 计算哈希函数所需时间 （简单）。
 
  
l 关键字的长度。
 
  
l 哈希表大小。
 
  
l 关键字分布情况。
 
  
l 记录查找频率
 
  
 
 
  
 
 
  
 
 
  
三.Hash处理冲突方法
 
  
 
 
  
   通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：
 
  
 
 
  
 通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：
 
  
1.         开放定址法
 
  
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
 
  
          Hi=（H（key）+di）% m   i=1，2，…，n
 
  
    其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：
 
  
l         线性探测再散列
 
  
    dii=1，2，3，…，m-1
 
  
这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
 
  
l         二次探测再散列
 
  
    di=12，-12，22，-22，…，k2，-k2    ( k<=m/2 )
 
  
    这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
 
  
l         伪随机探测再散列
 
  
    di=伪随机数序列。
 
  
具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。
 
  
例如，已知哈希表长度m=11，哈希函数为：H（key）= key  %  11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元，参图8.26 (a)。如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元，参图8.26 (b)。如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元，参图8.26 (c)。
 
  
 
 
  
 
 
  
0        1       2      3      4      5       6      7      8       9      10    
 
  
 
 
  
 
   
 
 
 
 
 
 
 
 
 
 
47
 
 
26
 
 
60
 
 
69
 
 
 
 
 
 
 
 
 
 
 
 
 
  
 
  
         （a） 用线性探测再散列处理冲突
 
  
 
 
  
 
 
  
0        1       2      3      4      5       6      7      8       9      10    
 
  
 
 
  
 
   
 
 
 
 
 
 
 
69
 
 
47
 
 
26
 
 
60
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  
 
  
         （b） 用二次探测再散列处理冲突
 
  
 
 
  
 
 
  
0        1       2      3      4      5       6      7      8       9      10    
 
  
 
 
  
 
   
 
 
 
 
 
 
 
 
 
 
47
 
 
26
 
 
60
 
 
 
 
 
 
 
 
69
 
 
 
 
 
 
 
  
 
  
         （c） 用伪随机探测再散列处理冲突
 
  
 
 
  
                      图8.26开放地址法处理冲突
 
  
从上述例子可以看出，线性探测再散列容易产生“二次聚集”，即在处理同义词的冲突时又导致非同义词的冲突。例如，当表中i, i+1 ,i+2三个单元已满时，下一个哈希地址为i, 或i+1 ,或i+2，或i+3的元素，都将填入i+3这同一个单元，而这四个元素并非同义词。线性探测再散列的优点是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次探测再散列和伪随机探测再散列则不一定。
 
  
 
 
  
2. 再哈希法
 
  
    这种方法是同时构造多个不同的哈希函数：
 
  
    Hi=RH1（key）  i=1，2，…，k
 
  
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
 
  
3. 链地址法
 
  
    这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
 
  
例如，已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为13，哈希函数为：H（key）= key % 13，则用链地址法处理冲突的结果如图
 
  
 
 
  


 
  
  
  
  
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
图链地址法处理冲突时的哈希表
 
  
本例的平均查找长度 ASL=(1*7+2*4+3*1)=1.5
 
  
4.建立公共溢出区
 
  
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表
 
  
 
 
  
 
 
  
 
 
  
参考资料
 
  
大话数据结
 
  
算法导论
 
 
 
 
 
 
 
  
 
  
 
  
 
  
 
  
 
  
 
 
 

 
Hash（哈希）相关知识
 
前言
一. 哈希函数
1. 函数特性
1.1 基本的哈希函数
1.2 加密的哈希函数
   
2. 常见的哈希函数构造法
2.1 直接寻址法
2.2 数字分析法
2.3 平方取中法
2.4 折叠法
2.5 随机数法
2.6 除留余数法
2.7 加密哈希函数
   
3. 哈希函数总结
  
二. 哈希查找
1. 操作步骤
2.哈希表的查找
2.1 哈希冲突
2.1.1 开放寻址法
2.1.2 链地址法
2.1.3 再散列法
2.1.4 建立公共溢出区
    
2.2 装填因子
  
  
三. 总结

 
前言
 
因为本人是小白(小菜鸡)，所以有些地方说的可能不是很准确，大家可以参考一些很厉害的博主，在评论区指出我写的不对的地方。
本来是想要单独写一下Hash(哈希)查找算法，但后来想到Java和区块链的入门里面都涉及到Hash，所以就说一下自己对Hash的理解。
在写的过程中，有涉及到密码学的相关概念，我尽力用举例子的方式让读者明白，如果觉得我有哪里说的不准确，可以查找相关文献进行更深层次的理解，以免我误人子弟，顺便谢谢大家啦！
 
一. 哈希函数
 
1. 函数特性
 
1.1 基本的哈希函数
 
哈希函数是一个数学函数，特性有下面三点：
其输入可为任意大小的字符串。
它产生固定大小的输出。
它能进行有效的计算，就是说对于特定的输入字符串，在合理时间内，能够计算出哈希函数的输出，对n位的字符串，哈希值计算的复杂度是O(n)。
 
1.2 加密的哈希函数
 
主要有附加的三个特性(相关文字说明源于BITCOIN AND CRYPTOCURRENCY TECHNOLOGIES 区块链技术驱动金融-数字货币与智能合约技术)：
碰撞阻力：对于两个不同的输入，能够产生相同的输出，就像y=x2，key1≠key2，但是产生了H(key1)=H(key2)。实际上世界上根本不存在具有防碰撞特性的哈希函数，现在技术上所用的加密哈希函数只不过是还没有找到碰撞的函数，就像之前人们都用的MD5，在前几年找到了碰撞后就逐渐淡出市场。
隐秘性：如果我们无法通过输出y=H(x)来找到输入x，那么就保证了隐秘性。但要满足这样条件的x必须取自一个非常大的集合，否则x将很容易就被获取。例如，我们抛硬币，只需要知道结果就很容易穷举出x的确定值。
谜题友好：这个特性听起来是人畜无害的，其实用我的话来解释就是盲目的穷举一个巨大无比的数据集，而要求是要找到一个小区域内的值。用人话来说就是，给你一个地球这么大的区域，让你通过穷举来寻找你家小区或者一个超市或者一个城市的区域，这个所要寻找的区域往往越小，难度越高(正常人都能看出来)。而这个谜题取自哪里也非常重要，谜题往往取自高阶最小熵分布，这样就保证了没有捷径能走。
 
2. 常见的哈希函数构造法
 
相信大家都接触过数据结构，在那里面讲到过很多种构建哈希函数的方法和存储方式，咱也列举一下(有的是复制粘贴的，因为在数据结构中都有讲到)。
百度词条：哈希表和相应问题处理方法
 
2.1 直接寻址法
 
取关键字或关键字的某个线性函数值为散列地址。即hash(k) = k 或 hash(k) = a · k + b，其中a、b为常数(这种散列函数叫做自身函数)。
 
2.2 数字分析法
 
这种方法是对重复性比较高的位进行查找，然后多选几位组成哈希地址，避免冲突增加。
 
2.3 平方取中法
 
取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
 
2.4 折叠法
 
将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
 
2.5 随机数法
 
选择一个随机函数，取关键字的随机函数值作为它的哈希地址，即H(key)=random(key)，其中random为随机函数。通常用于关键字长度不等时的场合。
 
2.6 除留余数法
 
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即H(key)=key MOD p(p<=m)。
不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。
 
2.7 加密哈希函数
 
这里介绍安全哈希算法(SHA - 256),主要是被比特币采用的哈希函数。
与它相关的概念叫压缩函数(compression function)。在通用术语中，将接受固定长度的哈希函数转化为可接受任意长度输入的哈希函数，这种转换过程叫MD(Merkle-Damgard)变换。一般来说这种基础型，可用于固定长度，并且具备碰撞阻力的哈希函数就是压缩函数。
SHA - 256就是利用了压缩函数将一个768位的输入压缩成256位的输出，每一个区块的大小是512位。
对于以上所说的知识，可以在百度上搜，或者看区块链的书。
 
3. 哈希函数总结
 
哈希函数并不是越复杂越好，而是根据需求进行设计和使用，因为哈希函数越复杂，时间消耗越长，对性能也有一定的影响。
 
二. 哈希查找
 
1. 操作步骤
 
用给定的哈希函数构造哈希表。
根据选择的冲突处理方法解决地址冲突。
在哈希表的基础上执行哈希查找。
 
2.哈希表的查找
 
哈希表的查找效率主要取决于哈希函数的构造方式、处理冲突的方式和装填因子。
 
2.1 哈希冲突
 
其实原理就是上面讲的碰撞，为了处理冲突，有这几种处理方法：
百度词条：哈希查找，这里面讲的还可以，有资源的可以在网上找具体操作，当然数据结构中的hash也讲过这几个方法，可以去找课件和书。
 
2.1.1 开放寻址法
 
如果产生冲突，就找个空地址塞进去，当然要保证散列地址足够大。
这种方法细分为3种，分别是线性探测再散列、二次探测再散列、伪随机探测再散列，详细的设计方法和原理在上面的链接里也有。
 
2.1.2 链地址法
 
将所有同关键字的记录存储在一个单链表中，称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。
这种方法有点像用链表构成树。
 
2.1.3 再散列法
 
提前准备多个散列函数，如果其中一个找不到合适的位置，那就换一个散列函数。
 
2.1.4 建立公共溢出区
 
粗暴方式，只要发生冲突就填进公共溢出区。
 
2.2 装填因子
 
散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度
α是散列表装满程度的标志因子。
由于表长是定值，α与填入表中的元素个数成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。
实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。
 
三. 总结
 
HashMap就是由数组+链表组合成的，也就是链地址法，在这篇里主要讲的就是哈希相关的东西，HashMap改天再说。
哈希函数的构造不是越复杂越好，合适就行了，因为不同的应用由不同的需求，根据需求选择合适的结构就行了，性能方面也要考虑，例如HashMap只要尽量的减少它的链表就能提高它执行的性能。