HASH 散列介绍

淩亂°似流年 2022-12-26 14:25 109阅读 0赞

# Hash #

音译：哈希  
翻译：散列

## 0. 计算机常见 ##

*  哈希函数（Hash function）：将数据编码成固定的小尺寸；用于哈希表和密码学
 *  哈希表（Hash table）：使用哈希函数的数据结构 \{key, value\}

## 1. 哈希函数 ##

### 1.1 定义 ###

**散列函数**（英语：Hash function）又称**散列算法**、**哈希函数**，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数函数将数据打乱混合，重新创建一个叫做**散列值**（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现**散列冲突**。在**散列表**和**数据处理**中，不抑制冲突来区别数据，会使得数据库记录更难找到。

如今，散列算法也被用来加密存在数据库中的**密码**（password）字符串，由于散列算法所计算出来的**散列值（Hash Value）具有不可逆**（无法逆向演算回原本的数值）的性质，因此可有效的保护密码。

### 1.2 散列函数的性质 ###

优秀的 Hash 函数性质

*  **确定性（单向散列函数）**：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有**确定性**的结果，具有这种性质的散列函数称为**单向散列函数**。
    
        输入数据的微小变化会得到完全不同的hash值，相同的数据会得到相同的值
        md5("这是一个测试文案");	==>	输出结果：2124968af757ed51e71e6abeac04f98d
        md5("这是二个测试文案");	==>	输出结果：bcc2a4bb4373076d494b2223aef9f702
        可以看到我们只改了一个文字，但是整个得到的hash值产生了非常大的变化。
 *  **较小散列碰撞（collision）**：散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同。这通常是两个不同长度的输入值，计算出相同的输出值。
    
        由于hash的原理是将输入空间的值映射成hash空间内，而hash值的空间远小于输入的空间。
        根据抽屉原理，一定会存在不同的输入被映射成相同输出的情况。
        那么作为一个好的hash算法，就需要这种冲突的概率尽可能小。
 *  **不可逆性**：从hash值不可以反向推导出原始的数据
    
        1. 这个从上面 MD5 的例子里可以明确看到，经过映射后的数据和原始数据没有对应关系
        2. 为什么有 MD5 类似解密？
        	- 数据库中对应取出
 *  **高效性**：哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值

### 1.3 散列函数的应用 ###

#### 1.3.1 散列表 ####

散列表是散列函数的一个主要应用，使用散列表能够快速的**按照关键字查找数据记录**。（注意：关键字不是像在加密中所使用的那样是秘密的，但它们都是用来“解锁”或者访问数据的。）例如，在英语字典中的关键字是英文单词，和它们相关的记录包含这些单词的定义。在这种情况下，散列函数必须把按照字母顺序排列的字符串映射到为散列表的内部数组所创建的索引上。

散列表散列函数的几乎不可能理想是把每个关键字映射到唯一的索引上，因为这样能够保证直接访问表中的每一个数据。一个好的散列函数（包括大多数加密散列函数）具有均匀的真正随机输出，因而平均只需要一两次探测（依赖于装填因子）就能找到目标。同样重要的是，随机散列函数不太会出现非常高的冲突率。但是，少量的可以估计的冲突在实际状况下是不可避免的。

#### 1.3.2 保护资料 ####

散列值可用于唯一地识别机密信息。这需要散列函数是抗碰撞(collision-resistant)的，意味着很难找到产生相同散列值的资料。散列函数分类为密码散列函数和可证明的安全散列函数。第二类中的函数最安全，但对于大多数实际目的而言也太慢。透过生成非常大的散列值来部分地实现抗碰撞。例如，SHA-2是最广泛使用的密码散列函数之一，它生成256比特值。

#### 1.3.3 确保传递真实的信息 ####

消息或数据的接受者确认消息是否被篡改的性质叫数据的真实性，也称为完整性。发信人通过将原消息和散列值一起发送，可以保证真实性。

#### 1.3.4 错误校正 ####

使用一个散列函数可以很直观的检测出数据在传输时发生的错误。在数据的发送方，对将要发送的数据应用散列函数，并将计算的结果同原始数据一同发送。在数据的接收方，同样的散列函数被再一次应用到接收到的数据上，如果两次散列函数计算出来的结果不一致，那么就说明数据在传输的过程中某些地方有错误了。这就叫做**冗余校验**。

校正错误时，至少会对可能出现的扰动大致假定一个分布模式。对于一个信息串的微扰可以被分为两类，大的（不可能的）错误和小的（可能的）错误。我们对于第二类错误重新定义如下，假如给定H（x）和x+s，那么只要 s 足够小，我们就能有效的计算出 x。那样的散列函数被称作**错误校正编码**。这些错误校正编码有两个重要的分类：**循环冗余校验**和**里德-所罗门码**。

#### 1.3.5 语音识别 ####

对于像从一个已知列表中匹配一个MP3文件这样的应用，一种可能的方案是使用传统的散列函数——例如MD5，但是这种方案会对时间平移、CD读取错误、不同的音频压缩算法或者音量调整的实现机制等情况非常敏感。使用一些类似于MD5的方法有利于迅速找到那些严格相同（从音频文件的二进制数据来看）的音频文件，但是要找到全部相同（从音频文件的内容来看）的音频文件就需要使用其他更高级的算法了。

分析正在播放的音乐，并将它于存储在数据库中的已知的散列值进行比较。用户就能够收到被识别的音乐的曲名。

### 1.4 目前常见的散列算法 ###

<table> 
 <thead> 
 <tr> 
 <th align="center">算法名称</th> 
 <th align="center">输出大小（bits）</th> 
 <th align="center">内部大小</th> 
 <th align="center">区块大小</th> 
 <th align="center">长度大小</th> 
 <th align="center">字符尺寸</th> 
 <th align="center">碰撞情形</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center">HAVAL</td> 
 <td align="center">256/224/192/160/128</td> 
 <td align="center">256</td> 
 <td align="center">1024</td> 
 <td align="center">64</td> 
 <td align="center">32</td> 
 <td align="center">是</td> 
 </tr> 
 <tr> 
 <td align="center">MD2</td> 
 <td align="center">128</td> 
 <td align="center">384</td> 
 <td align="center">128</td> 
 <td align="center">No</td> 
 <td align="center">8</td> 
 <td align="center">大多数</td> 
 </tr> 
 <tr> 
 <td align="center">MD4</td> 
 <td align="center">128</td> 
 <td align="center">128</td> 
 <td align="center">512</td> 
 <td align="center">64</td> 
 <td align="center">32</td> 
 <td align="center">是</td> 
 </tr> 
 <tr> 
 <td align="center">MD5</td> 
 <td align="center">128</td> 
 <td align="center">128</td> 
 <td align="center">512</td> 
 <td align="center">64</td> 
 <td align="center">32</td> 
 <td align="center">是</td> 
 </tr> 
 <tr> 
 <td align="center">PANAMA</td> 
 <td align="center">256</td> 
 <td align="center">8736</td> 
 <td align="center">256</td> 
 <td align="center">否</td> 
 <td align="center">32</td> 
 <td align="center">是</td> 
 </tr> 
 <tr> 
 <td align="center">RIPEMD</td> 
 <td align="center">128</td> 
 <td align="center">128</td> 
 <td align="center">512</td> 
 <td align="center">64</td> 
 <td align="center">32</td> 
 <td align="center">是</td> 
 </tr> 
 <tr> 
 <td align="center">RIPEMD-128/256</td> 
 <td align="center">128/256</td> 
 <td align="center">128/256</td> 
 <td align="center">512</td> 
 <td align="center">64</td> 
 <td align="center">32</td> 
 <td align="center">否</td> 
 </tr> 
 <tr> 
 <td align="center">RIPEMD-160/320</td> 
 <td align="center">160/320</td> 
 <td align="center">160/320</td> 
 <td align="center">512</td> 
 <td align="center">64</td> 
 <td align="center">32</td> 
 <td align="center">否</td> 
 </tr> 
 <tr> 
 <td align="center">SHA-0</td> 
 <td align="center">160</td> 
 <td align="center">160</td> 
 <td align="center">512</td> 
 <td align="center">64</td> 
 <td align="center">32</td> 
 <td align="center">是</td> 
 </tr> 
 <tr> 
 <td align="center">SHA-1</td> 
 <td align="center">160</td> 
 <td align="center">160</td> 
 <td align="center">512</td> 
 <td align="center">64</td> 
 <td align="center">32</td> 
 <td align="center">有缺陷</td> 
 </tr> 
 <tr> 
 <td align="center">SHA-256/224</td> 
 <td align="center">256/224</td> 
 <td align="center">256</td> 
 <td align="center">512</td> 
 <td align="center">64</td> 
 <td align="center">32</td> 
 <td align="center">否</td> 
 </tr> 
 <tr> 
 <td align="center">SHA-512/384</td> 
 <td align="center">512/384</td> 
 <td align="center">512</td> 
 <td align="center">1024</td> 
 <td align="center">128</td> 
 <td align="center">64</td> 
 <td align="center">否</td> 
 </tr> 
 <tr> 
 <td align="center">Tiger(2)-192/160/128</td> 
 <td align="center">192/160/128</td> 
 <td align="center">192</td> 
 <td align="center">512</td> 
 <td align="center">64</td> 
 <td align="center">64</td> 
 <td align="center">否</td> 
 </tr> 
 <tr> 
 <td align="center">WHIRLPOOL</td> 
 <td align="center">512</td> 
 <td align="center">512</td> 
 <td align="center">512</td> 
 <td align="center">256</td> 
 <td align="center">8</td> 
 <td align="center">否</td> 
 </tr> 
 </tbody> 
</table>

## 2. 哈希表 ##

### 2.1 定义 ###

**散列表**（**Hash table**，也叫**哈希表**），是根据**键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数**，**存放记录的数组称做散列表**。

### 2.2 基本概念 ###

*  若关键字为  k \{\\displaystyle k\} k，则其值存放在  f ( k ) \{\\displaystyle f(k)\} f(k) 的存储位置上，称这个对应关系  f \{\\displaystyle f\} f 为散列函数，按这个思想建立的表为散列表。不需比较便可直接取得所查记录。
 *  对不同的关键字可能得到同一散列地址，即  k 1 ≠ k 2 \{\\displaystyle k\_\{1\}\\neq k\_\{2\}\} k1=k2，而  f ( k 1 ) = f ( k 2 ) \{\\displaystyle f(k\_\{1\})=f(k\_\{2\})\} f(k1)=f(k2) ，这种现象称为**碰撞**（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。
 *  根据散列函数  f ( k ) \{\\displaystyle f(k)\} f(k) 和 **处理冲突的方法** 将一组关键字映射到一个**有限的连续的地址集（区间）上，并以关键字**在地址集中的“映像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
 *  若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

### 2.3 构造散列函数 ###

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

#### 2.3.1 直接定址法 ####

取关键字或关键字的某个线性函数值为散列地址。即  h a s h ( k ) = k \{\\displaystyle hash(k)=k\} hash(k)=k 或  h a s h ( k ) = a ⋅ k + b \{\\displaystyle hash(k)=a\\cdot k+b\} hash(k)=a⋅k\+b ，其中  a   b \{\\displaystyle a\\,b\} ab 为常数（这种散列函数叫做自身函数）

1.  **hash(k) = k**

举例1：统计1-100岁的人口，其中 年龄 作为关键字，哈希函数取关键字本身。

查找年龄25岁的人口有多少，则直接查表中第25项。

1.  **hash(k) = a \* k + b**

举例2：统计解放以后出生人口，其中 年份 作为关键字，哈希函数取关键字自身加一个常数 H(key)=key+(-1949)。

查找 2000 年出生的人数，则直接查 (2000-1949)=51 项即可。

**提示：**

*  直接定址法获取得到的散列函数有点就是简单，均匀也不会产生冲突但问题是这需要事先知道关键字的分布情况。
 *  适合查找表较小且连续的情况，地址集合的大小 = = 关键字集合的大小，其中a和b为常数。由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用。

#### 2.3.2 数字分析法 ####

假设关键字是以 r 为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。**数字分析法是取数据元素关键字中某些取值较均匀（数值不一样）的数字位作为哈希地址的方法**。即当关键字的位数很多时，可以通过对关键字的各位进行分析，丢掉分布不均匀的位，作为哈希值。

举例1：有 80 个记录，其关键字为8位十进制数，假设哈希表长，则可取两位十进制数组成哈希地址，为了尽量避免冲突，可先分析关键字。

k0  = 84595839
    k1  = 84598344
    k2  = 84593928
    k3  = 84592162
     ···
    k76 = 84211211
    k77 = 84214657
    k78 = 84219732
    k79 = 84217476

经分析，发现第一位都是8，第二位都是4，第三位只可能取5或2，第四位只可能取9或1，所以这四位不可取，那么对于第五、六、七、八位可看成是随机的，可取这四位作为哈希地址。

举例2：手机号前三位是接入号，中间四位是 HLR 识别号，只有后四位才是真正的用户号，也就是说，如果手机号作为关键字，那么极有可能前 7 位是相同的，此时我们选择后四位作为散列地址就是不错的选择。

**提示：**

*  目的就是为了提供一个能够尽量合理地将关键字分配到散列表的各个位置的散列函数
 *  能预先估计出全体关键字的每一位上各种数字出现的频度，它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间
 *  对于抽取出来的数字，还可以再进行反转，右环位移，左环位移等操作

#### 2.3.3 平方取中法 ####

取**关键字平方的中间位数**作为**散列地址**。

举例：若设哈希表长为1000则可取关键字平方值的中间四位

<table> 
 <thead> 
 <tr> 
 <th>关键字</th> 
 <th>关键字的平方</th> 
 <th>哈希函数值</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>1234</td> 
 <td>01522756</td> 
 <td>5227</td> 
 </tr> 
 <tr> 
 <td>2143</td> 
 <td>04592449</td> 
 <td>5924</td> 
 </tr> 
 <tr> 
 <td>4132</td> 
 <td>17073424</td> 
 <td>0734</td> 
 </tr> 
 <tr> 
 <td>3214</td> 
 <td>10329796</td> 
 <td>3297</td> 
 </tr> 
 </tbody> 
</table>

#include <stdio.h>
 
 // 哈希函数将返回 key * key 的中间 4 位
 int Hash(int key) {
 
 // 计算 key 的平方
 key = key * key;
 printf("%08d\n", key);
 // 去掉低 2 位
 key = key / 100;
 // 取低 4 位，即平方中间 4 位
 key = key % 10000;
 return key;
 }
 
 int main(int argc, char* argv[]) {
 
 int key = 1234;
 int ret = Hash(key);
 printf("%04d\n", ret);
 return 0;
 }

**提示：**

*  平方取中法比较**适合**于**不知道关键字的分布**，而**位数又不是很大**的情况

#### 2.3.4 折叠法 ####

将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。

两种叠加处理的方法：

*  **移位叠加**：将分 割后的几部分低位对齐相加
 *  **边界叠加**：从一端沿分割界来回折叠，然后对齐相加

举例：当哈希表长为1000时，关键字key=110108331119891，允许的地址空间为三位十进制数，则这两种叠加情况如图：

移位叠加							 边界叠加
    	891									891
    	119									911
    	331									331
    	108									801
      + 110								  + 110
    --------------                      -------------
     (1)559								 (3)044

/***************************************************************************
 * @date 2020/12/05
 * @brief 从后面开始折叠，key 为关键字，len 为返回长度
 ***************************************************************************/
 #include <malloc.h>
 #include <math.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 char* reverse(char* str) {
 
 int len = strlen(str);
 char* temp = (char*)malloc(sizeof(char) * (len + 1));
 for (int i = 0; i < len; i++) {
 
 temp[i] = str[len - 1 - i];
 }
 temp[len] = '\0';
 return temp;
 }
 
 // 移位折叠
 int fold(char* key, int len) {
 
 int n = (strlen(key) % len == 0) ? (strlen(key) / len) : (strlen(key) / len + 1);
 char** str = (char**)malloc(sizeof(char*) * n);
 for (int i = 0; i < n; i++) {
 
 *(str + i) = (char*)malloc(sizeof(char) * (len + 1));
 memset(*(str + i), '\0', sizeof(*(str + i)));
 if (i < n - 1 || strlen(key) % len == 0) {
 
 strncpy(*(str + i), key + strlen(key) - (i + 1) * len, len);
 } else {
 
 strncpy(*(str + i), key, strlen(key) % len);
 }
 printf("%d: %s\n", i, *(str + i));
 }
 int sum = 0;
 for (int i = 0; i < n; i++) {
 
 sum += atoi(*(str + i));
 }
 return (sum >= pow(10, len)) ? (sum % (int)pow(10, len)) : sum;
 }
 
 // 边界折叠
 int fold2(char* key, int len) {
 
 int n = (strlen(key) % len == 0) ? (strlen(key) / len) : (strlen(key) / len + 1);
 char** str = (char**)malloc(sizeof(char*) * n);
 for (int i = 0; i < n; i++) {
 
 *(str + i) = (char*)malloc(sizeof(char) * (len + 1));
 memset(*(str + i), '\0', sizeof(*(str + i)));
 if (i < n - 1 || strlen(key) % len == 0) {
 
 strncpy(*(str + i), key + strlen(key) - (i + 1) * len, len);
 } else {
 
 strncpy(*(str + i), key, strlen(key) % len);
 }
 }
 int sum = 0;
 for (int i = 0; i < n; i++) {
 
 if (i % 2 == 0) {
 
 sum += atoi(*(str + i));
 } else {
 
 sum += atoi(reverse(*(str + i)));
 }
 }
 return (sum >= pow(10, len)) ? (sum % (int)pow(10, len)) : sum;
 }
 
 int main(int argc, char* argv[]) {
 
 char* key = (char*)"110108331119891";
 int len = 3;
 int ret = fold(key, len);
 int ret2 = fold2(key, len);
 printf("%d\n", ret);
 printf("%d\n", ret2);
 return 0;
 }

**提示：**

*  折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况

#### 2.3.5 伪随机数法 ####

选择一个随机数，**取关键字**的**随机函数值**为它的**散列地址**： f ( k ) = r a n d o m ( k e y ) f(k) = random(key) f(k)=random(key)

#include <stdio.h>
 #include <stdlib.h>
 
 int my_random(int key) {
 
 return rand_r((unsigned int*)&key);
 }
 
 int main(int argc, char* argv[]) {
 
 int key = 10;
 int ret = my_random(key);
 printf("%d\n", ret);
 return 0;
 }

**提示：**

*  **此法适于：当关键字的长度不等**时**采用**这个方法构造散列函数是比较**合适**的
 *  实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，以及哈希表 长度（哈希地址范围），**总的原则是使产生冲突的可能性降到尽可能地小**

#### 2.3.6 除留余数法 ####

取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即  
 h a s h ( k ) = k     m o d    p p ≤ m \{ hash(k)=k\\,\{\\bmod \{\\,\}\}p\} \\qquad \{ p\\leq m\} hash(k)=kmodpp≤m

例如，已知待散列元素为（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

#include <stdio.h>
 
 int my_mod(int key, int p) {
 
 return key % p;
 }
 
 int main(int argc, char* argv[]) {
 
 int key[] = {
 18, 75, 60, 43, 54, 90, 46};
 int m = 13;
 int p = m;
 for (int i = 0; i < sizeof(key) / sizeof(key[0]); i++) {
 
 int ret = my_mod(key[i], p);
 printf("%d ", ret);
 }
 return 0;
 }

**提示：**

*  此方法为最常用的构造散列函数方法
 *  若散列表表长为 m 通常 p 为小于或等于表长（最好接近 m ）的最小质数或不包含小于 20 质因子的合数
 *  不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。

#### 2.3.7 减去法 ####

f ( k ) = k − b f(k) = k-b f(k)=k−b

举例：公司有一百个员工，而员工的编号介于1001到1100，减去法就是员工编号减去1000后即为数据的位置。编号1001员工的数据在数据中的第一笔。编号1002员工的数据在数据中的第二笔…依次类推。从而获得有关员工的所有信息，因为编号1000以前并没有数据，所有员工编号都从1001开始编号。

#### 2.3.8 基数转换法 ####

将十进制数X看作其他进制，比如十三进制，再按照十三进制数转换成十进制数，提取其中若干为作为X的哈希值。一般取大于原来基数的数作为转换的基数，并且两个基数应该是互素的。

举例： H a s h ( 80127429 ) = ( 80127429 ) 13 = 8 ∗ 1 3 7 + 0 ∗ 1 3 6 + 1 ∗ 1 3 5 + 2 ∗ 1 3 4 + 7 ∗ 1 3 3 + 4 ∗ 1 3 2 + 2 ∗ 1 3 1 + 9 = ( 502432641 ) 10 Hash(80127429)=(80127429)\_\{13\}=8\*13^7+0\*13^6+1\*13^5+2\*13^4+7\*13^3+4\*13^2+2\*13^1+9=(502432641)\_\{10\} Hash(80127429)=(80127429)13=8∗137\+0∗136\+1∗135\+2∗134\+7∗133\+4∗132\+2∗131\+9=(502432641)10

如果取中间六位作为哈希值，得Hash（80127429）= 024326

**提示：**

*  为了获得良好的哈希函数，可以将几种方法联合起来使用，比如先变基，再折叠或平方取中等等，只要散列均匀，就可以随意拼凑。

#### 2.3.9 字符串数值哈希法 ####

在很都情况下关键字是字符串，因此这样对字符串设计Hash函数是一个需要讨论的问题。

这个函数称为 ELF Hash(Exextable and Linking Format ,ELF，可执行链接格式) 函数。它把一个字符串的绝对长度作为输入，并通过一种方式把字符的十进制值结合起来，对长字符串和短字符串都有效，这种方式产生的位置均匀分布。

#include <stdio.h>
 
 unsigned int ELFHash(char* str) {
 
 unsigned int hash = 0;
 unsigned int high = 0;
 while (*str) {
 
 hash = (hash << 4) + (*str++); // hash左移4位，把当前字符ASCII存入hash低四位。
 high = hash & 0xf0000000L;
 if (high) {
 
 // 如果最高的四位不为0，则说明字符多余7个，现在正在存第7个字符，如果不处理，再加下一个字符时，第一个字符会被移出，因此要有如下处理。
 // 该处理，如果最高位为0，就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位
 // 因为1-4位刚刚存储了新加入到字符，所以不能>>28
 hash ^= (high >> 24);
 // 上面这行代码并不会对X有影响，本身X和hash的高4位相同，下面这行代码&~即对28-31(高4位)位清零。
 hash &= ~high;
 }
 }
 // 返回一个符号位为 0 的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负)
 return (hash & 0x7FFFFFFF);
 }
 
 int main(int argc, char* argv[]) {
 
 char* key = (char*)"abcdefg";
 unsigned int ret = ELFHash(key);
 printf("%d\n", ret);
 return 0;
 }

### 2.4 处理冲突（HASH 碰撞） ###

前面介绍：散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同。这通常是两个不同长度的输入值，计算出相同的输出值。

（1）**聚集/堆积（Cluster）**

在函数地址的表中，散列函数的结果不均匀地占据表的单元，形成区块，造成线性探测产生一次聚集（primary clustering）和平方探测的二次聚集（secondary clustering），散列到区块中的任何关键字需要查找多次试选单元才能插入表中，解决冲突，造成时间浪费。对于开放定址法，聚集会造成性能的灾难性损失，是必须避免的。

（2）**负载因子（load factor）**  
 load factor = n k \{\\displaystyle\{\\text\{load factor\}\}=\{\\frac\{n\}\{k\}\}\} load factor=kn

*  n 是哈希表中占用的条目数。
 *  k 是存储桶数

随着负载因子的增大，哈希表变慢，甚至可能无法工作（取决于所使用的方法）。哈希表的预期恒定时间属性假定负载因子保持在某个界限以下。对于固定数量的存储桶，查找时间随条目数量而增加，因此无法实现所需的恒定时间。在某些实现中，解决方案是在达到负载因子限制时自动增大（通常为两倍）表的大小，从而强制重新散列所有条目。作为一个实际示例，Java 10中HashMap的默认加载因子为0.75。

#### 2.4.1 开放定址法 ####

**open addressing**：在另一种称为开放式寻址的策略中，所有条目记录都存储在存储桶数组本身中。当必须插入新条目时，将检查存储桶，从哈希到的插槽开始，并按某些探测顺序进行操作，直到找到未占用的插槽。搜索条目时，将按相同顺序扫描存储桶，直到找到目标记录或找到未使用的阵列插槽为止。

“开放地址”是指以下事实：**项目的位置（“地址”）不是由其哈希值确定的**。（此方法也称为 **封闭式哈希**；请勿将其与“开放式哈希”或“封闭式寻址”混淆

**（1）通用函数**

这种方法有一个通用的再散列函数形式：  
 H i = ( H ( k e y ) + d i ) % m i = 1 , 2 , ⋅ ⋅ ⋅ , m H\_\{i\} = (H(key) + d\_\{i\}) \\% m \\qquad i = 1, 2, ···, m Hi=(H(key)\+di)%mi=1,2,⋅⋅⋅,m  
其中  H ( k e y ) H(key) H(key) 为**哈希函数**， m m m 为**表长**， d i d\_\{i\} di 称为**增量序列。**

**（2）分类**

增量序列的取值方式不同，相应的再散列方式也不同。

1.  **线性探测(Linear Probing)**  
    两次探测之间的间隔是固定的，通常设置为1。
2.  **平方探测(Quadratic Probing)**  
    二次探测：其中探针之间的间隔呈二次方增加（因此，索引由二次函数描述）。
3.  **双重哈希（伪随机探测）**  
    其中每个记录的探测间隔（是固定的？）由另一个哈希函数计算得出。

**这些方法之间线性探测具有最佳的缓存性能对聚类最敏感，而双重哈希的缓存性能较差，但实际上没有聚类。二次探测介于两个区域之间。与其他形式的探测相比，双散列还可能需要更多的计算。**

举例：

关键字为 \{89,18,49,58,69\} 插入到一个散列表中的情况。并假定取关键字除以10的余数为散列函数法则（m = 10）。

显示**线性探测**填装一个散列表的过程，此时线性探测的方法是取  d i = 1 d\_\{i\} = 1 di=1。

表的大小选取至关重要，此处选取10作为大小，发生冲突的几率就比选择质数11作为大小的可能性大。越是质数，mod取余就越可能均匀分布在表的各处。

显示**平方探测**填装一个散列表的过程，此时线性探测的方法是取  d i = ( x % 10 ) 2 d\_\{i\} = (x\\%10)^\{2\} di=(x%10)2。

显示**双重探测**填装一个散列表的过程，此时线性探测的方法是取随机  d i = r a n d \_ r ( i ) % 10 m = 10 d\_\{i\} = rand\\\_r(i)\\%10 \\quad m =10 di=rand\_r(i)%10m=10 。（未验证）

#include <stdio.h>
 #include <stdlib.h>
 
 void displayA(int* array, int size) {
 
 for (int i = 0; i < size; i++) {
 
 printf("%3d|", array[i]);
 }
 printf("\n");
 }
 
 /***************************************************************************
 * @date 2020/12/05
 * @brief 选择插入位置，d = 1
 * @param Hash1 散列地址空间
 * @param size 散列地址大小
 * @param key 关键字
 * @return 插入位置
 ***************************************************************************/
 int open1(int* Hash1, int size, int key) {
 
 int temp = key % size;
 int count = size;
 while (count--) {
 
 if (Hash1[temp] == 0) {
 
 return temp;
 } else {
 
 temp = (temp + 1) % size;
 }
 }
 printf("散列地址已满！");
 exit(-1);
 }
 
 int main(int argc, char* argv[]) {
 
 int key[] = {
 89, 18, 49, 58, 69, 45, 55, 78, 93, 61, 28};
 int key_size = sizeof(key) / sizeof(key[0]);
 int Hash1[10] = {
 0};
 printf(" 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|\n");
 printf("----------------------------------------\n");
 for (int i = 0; i < key_size; i++) {
 
 Hash1[open1(Hash1, 10, key[i])] = key[i];
 displayA(Hash1, 10);
 }
 return 0;
 }

#### 2.4.2 链地址法 ####

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为**同义词链**的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

*  链接列表分开链接

![在这里插入图片描述][20201205221755529.png]

*  列表头单元格分开链接

一些链接实现将每个链的第一条记录存储在插槽阵列本身中。在大多数情况下，指针遍历的数量减少一。目的是提高哈希表访问的缓存效率。缺点是空桶与一个入口的桶占用相同的空间。为了节省空间，此类哈希表通常具有与存储的条目一样多的插槽，这意味着许多插槽具有两个或多个条目。

![在这里插入图片描述][20201205221809853.png]

*  其他数据结构链接

除了列表以外，还可以使用支持所需操作的任何其他数据结构。

举例：已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为13，哈希函数为：H（key）= key % 13

![在这里插入图片描述][20201205221830719.png]

#include <stdio.h>
 #include <stdlib.h>
 
 typedef struct list_node {
 
 int data;
 struct list_node* next;
 } LN;
 
 void display(LN* HashMap, int mod) {
 
 for (int i = 0; i < mod; i++) {
 
 printf("%2d: ", i);
 LN* p = (HashMap + i)->next;
 while (p) {
 
 printf("%d ", p->data);
 p = p->next;
 }
 printf("\n");
 }
 }
 
 /***************************************************************************
 * @date 2020/12/05
 * @brief 插入对应链表，然后顺序插入
 * @param list 链表头
 * @param key 关键字
 * @param mod Hash 表长度
 ***************************************************************************/
 void insert(LN* list, int key, int mod) {
 
 int value = key % mod;
 LN* temp = (list + value);
 LN* node = (LN*)malloc(sizeof(LN));
 node->data = key;
 node->next = NULL;
 if (temp != NULL) {
 
 while (temp->next && temp->next->data < key) {
 
 temp = temp->next;
 }
 }
 // 头插法
 node->next = temp->next;
 temp->next = node;
 }
 
 /***************************************************************************
 * @date 2020/12/05
 * @brief 删除 Hash 值（查找同理）
 * @param list 链表头
 * @param key 关键字
 * @param mod Hash 表长度
 * @return 0/1 完成信息 0-成功
 ***************************************************************************/
 int erase(LN* list, int key, int mod) {
 
 int value = key % mod;
 LN* prev = (list + value);
 LN* temp = prev->next;
 if (temp != NULL) {
 
 while (temp && temp->data < key) {
 
 prev = temp;
 temp = temp->next;
 }
 if (temp->data == key) {
 
 prev->next = temp->next;
 free(temp);
 return 0;
 }
 }
 return -1;
 }
 
 int search(LN* list, int key, int mod) {
 
 int value = key % mod;
 LN* temp = (list + value)->next;
 if (temp != NULL) {
 
 while (temp && temp->data < key) {
 
 temp = temp->next;
 }
 if (temp->data == key) {
 
 return 0;
 }
 if (temp == NULL) {
 
 return -1;
 }
 }
 return -1;
 }
 
 int main(int argc, char* argv[]) {
 
 int key[] = {
 32, 40, 36, 53, 16, 46, 71, 27, 42, 24, 49, 64};
 int size = sizeof(key) / sizeof(key[0]);
 int mod = 13;
 LN* HashMap = (LN*)malloc(sizeof(LN) * mod);
 for (int i = 0; i < mod; i++) {
 
 (*(HashMap + i)).next = NULL;
 }
 
 // 插入
 for (int i = 0; i < size; i++) {
 
 insert(HashMap, key[i], mod);
 }
 display(HashMap, mod);
 // 查找
 (search(HashMap, 40, mod) == 0) ? printf("\ttrue\n") : printf("\tfalse\n");
 // 删除
 erase(HashMap, 40, mod);
 display(HashMap, mod);
 // 查找
 (search(HashMap, 40, mod) == 0) ? printf("\ttrue\n") : printf("\tfalse\n");
 
 return 0;
 }

#### 2.4.3 多重哈希法 ####

*  **再哈希法**

h a s h = H 2 ( H 1 ( k e y ) ) hash = H2(H1(key)) hash=H2(H1(key))

即在上次散列计算发生冲突时，利用该次冲突的散列函数地址产生新的散列函数地址，直到冲突不再发生。这种方法不易产生\*\*“聚集”（Cluster）\*\*，但增加了计算时间。（可以多重哈希算法计算，直到不冲突）。

*  **2-选择散列**

2-选择哈希对哈希表：采用两个不同的哈希函数  h 1 ( k e y ) h1(key) h1(key) 和  h 2 ( k e y ) h2(key) h2(key) 。这两个哈希函数都用于计算两个表位置。将对象插入表中后，会将其放置在包含较少对象的表位置（如果存储桶大小相等，则默认为表  h 1 ( k e y ) h1(key) h1(key) 位置）。2-选择散列采用两种选择的幂的原理。

#### 2.4.4 建立公共溢出区 ####

这种方法的基本思想是：将哈希表分为**基本表**和**溢出表**两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

## 3. 使用及分析 ##

### 3.1 应用 ###

（1）数据库索引

哈希表也可用作基于磁盘的数据结构和数据库索引（例如dbm），尽管B树在这些应用程序中更为流行。在多节点数据库系统中，哈希表通常用于在节点之间分配行，从而减少了哈希联接的网络流量。

（2）高速缓存

哈希表可用于实现高速缓存，辅助数据表，这些数据表用于加快对主要存储在较慢媒体中的数据的访问。在此应用程序中，可以通过丢弃两个冲突条目之一来处理哈希冲突-通常擦除当前存储在表中的旧项目，然后用新项目覆盖它，因此表中的每个项目都具有唯一的哈希值。

（3）密码学

### 3.2 优缺点 ###

（1）优势

*  **哈希表相对于其他表数据结构的主要优点是速度**。当条目数量很大时，此优势更加明显。当可以预先预测最大条目数时，哈希表特别有效，因此可以以最佳大小分配存储桶数组一次，而从不调整大小。
 *  如果一组键值对是固定的，并且提前知道（因此不允许插入和删除），则可以通过仔细选择哈希函数，存储区表大小和内部数据结构来**降低平均查找成本**。特别地，人们可能能够设计出一种无冲突甚至完美的哈希函数。在这种情况下，密钥不必存储在表中。

（2）劣势

*  尽管对哈希表的操作平均需要花费恒定的时间，但良好的哈希函数的成本可能比顺序列表或搜索树的查找算法的内循环高得多。因此，**当条目数很少时，哈希表无效**。如果没有太多可能要存储的键（也就是说，如果每个键可以用足够小的位数表示），则**可以使用该键直接作为数组的索引**，而不使用哈希表价值。请注意，在这种情况下不会发生冲突。
 *  **如果哈希表使用动态调整大小，则插入或删除操作可能会偶尔花费与条目数量成比例的时间**。在实时或交互式应用程序中，这可能是一个严重的缺点。
 *  通常，哈希表的引用局部性很差-也就是说，要访问的数据似乎在内存中随机分布。**因为哈希表会导致访问模式跳来跳去，所以这会触发微处理器高速缓存未命中，从而导致长时间的延迟**。如果表相对较小并且键很紧凑，则紧凑的数据结构（例如使用线性搜索搜索的数组）可能会更快。最佳性能点因系统而异。
 *  **当发生许多冲突时，哈希表的效率变得非常低下**。虽然极不可能偶然出现非常不均匀的哈希分布，但是具有哈希功能知识的恶意攻击者可能会向哈希提供信息，从而通过引起过多的冲突而导致最坏情况的行为，从而导致性能非常差。

## 4. 总结 ##

### 4.1 复杂度 ###

<table> 
 <thead> 
 <tr> 
 <th align="left"></th> 
 <th>平均</th> 
 <th>最坏的情况下</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="left">space</td> 
 <td> O ( n ) O(n) O(n)</td> 
 <td> O ( n ) O(n) O(n)</td> 
 </tr> 
 <tr> 
 <td align="left">search</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td> O ( n ) O(n) O(n)</td> 
 </tr> 
 <tr> 
 <td align="left">insert</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td> O ( n ) O(n) O(n)</td> 
 </tr> 
 <tr> 
 <td align="left">delete</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td> O ( n ) O(n) O(n)</td> 
 </tr> 
 </tbody> 
</table>

### 4.2 理解 ###

Hash算法也被称为散列算法，Hash算法虽然被称为算法，但实际上它更像是一种思想。Hash算法没有一个固定的公式，只要符合散列思想的算法都可以被称为是Hash算法。

## 参考 ##

\[1\] [什么是 hash？][hash]

\[2\] [hash算法原理详解][hash 1]

\[3\] [数据结构—— 构造散列函数的六种方法][Link 1]

\[4\] [程序员必备：字符串哈希函数比较][Link 2]

\[5\] [散列函数][Link 3]

[20201205221755529.png]: /images/20221120/d39fbaa0cfbd4d3395fe8250306373db.png
[20201205221809853.png]: https://img-blog.csdnimg.cn/20201205221809853.png
[20201205221830719.png]: https://img-blog.csdnimg.cn/20201205221830719.png
[hash]: https://www.zhihu.com/question/26762707/answer/40119521
[hash 1]: https://blog.csdn.net/tanggao1314/article/details/51457585
[Link 1]: https://blog.csdn.net/liu17234050/article/details/104270709?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-5.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-5.control#%E4%B8%80%EF%BC%9A%E7%9B%B4%E6%8E%A5%E5%AE%9A%E5%9D%80%E6%B3%95
[Link 2]: https://blog.csdn.net/AlburtHoffman/article/details/19641123
[Link 3]: https://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8