hash地址_Hash算法基础

​1.Hash介绍

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

所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。

碰撞

两个不同的输入值，根据同一散列函数计算出的散列值相同的现象叫做碰撞。

压缩映射

设(X, ρ)为距离空间，T是X到X中的映射，如果存在数a(0<a<1)，使得对所有的x,y∈X都有ρ(Tx, Ty)≤a*ρ(x, y)，则称T是压缩映射，压缩映射也称为利普希茨映射。

例子

举个简单的例子，新华字典，我们查字典的时候，如果按照拼音去查找（当然按照偏旁部首去查找也是一样），比如查找“位”，按照拼音表，W开头的拼音

按照步骤来，应该首先去查W开头的拼音，然后去查找wei的位置，然后在找到“位”，这个过程就是键码映射，在wei键值下有很多字，这些字存储的时候产生了“碰撞”， 在公式里面，就是通过key去查找f(key)。其中，wei就是关键字（key），f（）就是字典索引，也就是哈希函数，查到的页码就是哈希值。

2.Hash冲突

刚刚查字的时候，发现wei下有很多字，问题就来了，我们要查的是“位”，而不是“未“，但是他们的拼音是一样的。也就是通过关键字”位“和关键字”未“可以映射到一样的字典页码的位置，这就是哈希冲突（也叫哈希碰撞），在公式上表达就是key1≠key2，但f(key1)=f(key2)。冲突会给查找带来麻烦，你想想，你本来查找的是“位”，但是却找到“未”字，你又得向后翻一两页，在计算机里面也是一样道理的。

但哈希冲突是无可避免的，为什么这么说呢，因为你如果要完全避开这种情况，你只能每个字典去新开一个页，然后每个字在索引里面都有对应的页码，这就可以避免冲突。但是会导致空间增大（每个字都有一页）。

既然无法避免，就只能尽量减少冲突带来的损失，而一个好的哈希函数需要有以下特点：

1. 尽量使关键字对应的记录均匀分配在哈希表里面（比如说某厂商卖30栋房子，均匀划分ABC3个区域，如果你划分A区域1个房子，B区域1个房子，C区域28个房子，有人来查找C区域的某个房子最坏的情况就是要找28次）。
2. 关键字极小的变化可以引起哈希值极大的变化。

Hash函数

此条来自于百度，Hash函数的建立有很多学问，这里只是帮大家了解一下，这些均来自数据结构中的知识！

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。常用Hash函数有：

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选的不好，容易产生碰撞。

Time33算法

这是一个对字符串进行哈希的函数，现在几乎所有流行的HashMap都采用了DJB Hash Function，俗称“Times33”算法。Times33的算法很简单，就是对字符串进行逐个字符遍历，不断的乘33，然后把数值相加即可。

核心的算法就是如下：

unsigned long hash(const char* key){
    unsigned long hash=0;
    for(int i=0;i<strlen(key);i++){
        hash = hash*33+str[i];
    }  
    return hash;
}
           

3.Hash冲突解决

处理冲突方法

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=12,-12,22,-22,32,…，±k2,(k<=m/2)称二次探测再散列；
   3. di=伪随机数序列，称伪随机探测再散列。
2. 再散列法：Hi=RHi(key),i=1,2,…，k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
3. 链地址法(拉链法)
4. 建立一个公共溢出区

最常用的就是开发定址法和链地址法。

开放定址法

为了使用开放定址法插入一个元素，需要连续的检查散列表，直到找到一个新的空槽来放置带插入的元素为止。检查的顺序不一定是0,1,2,…,m-1的这种顺序，而是要依赖待插入的关键字key,为了确定探查哪些槽，我们将散列函数加以扩充，使之包含探查号作为第二个输入参数，

下图演示的是线性探测解决冲突的方法：

二次探测和伪随机数法和线性探测的模式相同，只是在冲突后，选取平方数和随机数进行探测

链地址法

上面所说的开发定址法的原理是遇到冲突的时候查找顺着原来哈希地址查找下一个空闲地址然后插入，但是也有一个问题就是如果空间不足，那他无法处理冲突也无法插入数据，因此需要装填因子(插入数据/空间)<=1。

那有没有一种方法可以解决这种问题呢？链地址法可以，链地址法的原理时如果遇到冲突，他就会在原地址新建一个空间，然后以链表结点的形式插入到该空间。我感觉业界上用的最多的就是链地址法。下面从百度上截取来一张图片，可以很清晰明了反应下面的结构。比如说我有一堆数据{1,12,26,337,353…}，而我的哈希算法是H(key)=key mod 16，第一个数据1的哈希值f(1)=1，插入到1结点的后面，第二个数据12的哈希值f(12)=12，插入到12结点，第三个数据26的哈希值f(26)=10，插入到10结点后面，第4个数据337，计算得到哈希值是1，遇到冲突，但是依然只需要找到该1结点的最后链结点插入即可，同理353。

开放定址法的所有元素都存在于散列表之内，每一个表项要么存在元素，要么就为空，当发生映射值冲突的时候我们可以探查新的位置。最好的探查方法是双重散列，因为双重散列产生的探查序列足够随机，不像线性探查和二次探查哪样存在较为严重的群集现象。

开放定址法相对于链接法来说，可以将存储链表指针的内存空出来存储更多的数据，直接跳过了指针的操作，而是用数组的直接访问来访问元素，但是如果探查散列函数设计差劲的话，将会严重拖慢散列表的速度！

4.Hash查找性能

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

1. 散列函数是否均匀；
2. 处理冲突的方法；

3. 散列表的装填因子。

   散列表的装填因子定义为：α= 填入表中的元素个数/散列表的长度

   α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。

   实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。

由于哈希表高效的特性，查找或者插入的情况在大多数情况下可以达到O(1)，时间主要花在计算hash上，当然也有最坏的情况就是hash值全都映射到同一个地址上，这样哈希表就会退化成链表，查找的时间复杂度变成O(n)，但是这种情况比较少，只要不要把hash计算的公式外漏出去并且有人故意攻击（用兴趣的人可以搜一下基于哈希冲突的拒绝服务攻击），一般也不会出现这种情况。

如图所示，哈希冲突攻击导致退化成链表