Hash 学习

向右看齐 2022-06-03 07:20 171阅读 0赞

# Hash学习 #

*  Hash学习
    
     *  概念
        
         *  Hash
         *  hash 值（数字摘要）
         *  Hash 函数、算法
         *  Hash table（散列表、哈希表）
     *  Hash算法应用
        
         *  加密散列函数：MD5等
         *  错误校正
         *  语音识别
         *  信息安全
     *  常用的Hash函数
        
         *  RS
         *  JS
         *  PJW
         *  ELF
         *  BKDR
         *  SDBM
         *  DJB
         *  DEK
         *  AP
         *  murmurhash

> **声明**：  
> 参考：[哈希算法集锦][Link 1]

## 概念 ##

### Hash ###

一般翻译为“散列”，也有直接称“哈希”（音译）的。

### hash 值（数字摘要） ###

把任意长度的输入（又叫做预映射， pre-image），通过 Hash 算法，变换成固定长度的输出，该输出就是 Hash 值。

### Hash 函数、算法 ###

**一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。**  
这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间。  
如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。  
不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。但要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以在计算机上可以使用Hash值检验数据的完整性。一般用于快速查找和加密算法。

### Hash table（散列表、哈希表） ###

根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。  
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

## Hash算法应用 ##

由于散列函数的应用的多样性，它们经常是专为某一应用而设计的。

### 加密散列函数：MD5等 ###

一个设计优秀的加密散列函数应该是一个“单向”操作：对于给定的散列值，没有实用的方法可以计算出一个原始输入，也就是说很难伪造。  
为加密散列为目的设计的函数，如MD5，被广泛的用作检验散列函数。这样软件下载的时候，就会对照验证代码之后才下载正确的文件部分。此代码有可能因为环境因素的变化，如机器配置或者IP地址的改变而有变动。以保证源文件的安全性。

### 错误校正 ###

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

### 语音识别 ###

对于像从一个已知列表中匹配一个MP3文件这样的应用，一种可能的方案是使用传统的散列函数——例如MD5，但是这种方案会对时间平移、CD读取错误、不同的音频压缩算法或者音量调整的实现机制等情况非常敏感。使用一些类似于MD5的方法有利于迅速找到那些严格相同（从音频文件的二进制数据来看）的音频文件，但是要找到全部相同（从音频文件的内容来看）的音频文件就需要使用其他更高级的算法了。  
有一个实际的例子是Shazam服务。用户可以用电话机拨打一个特定的号码，并将电话机的话筒靠近用于播放音乐的扬声器。该项服务会分析正在播放的音乐，并将它于存储在数据库中的已知的散列值进行比较。用户就能够收到被识别的音乐的曲名（需要收取一定的费用）

### 信息安全 ###

Hash算法在信息安全方面的应用主要体现在以下的3个方面：

1.  文件校验  
    我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。  
    MD5 Hash算法的”数字指纹”特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。
2.  数字签名  
    Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称”数字摘要”进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。
3.  鉴权协议  
    如下的鉴权协议又被称作挑战–认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

## 常用的Hash函数 ##

通用的哈希函数库有下面这些混合了加法和一位操作的字符串哈希算法。下面的这些算法在用法和功能方面各有不同，但是都可以作为学习哈希算法的实现的例子。  
也可参考：[Hash 算法][Hash]

### RS ###

从Robert Sedgwicks的 Algorithms in C一书中找到。我(原文作者)已经添加了一些简单的优化的算法，以加快其散列过程。

public long RSHash(String str) {  
       int b = 378551;  
       int a = 63689;  
       long hash = 0;  
       for(int i = 0; i < str.length(); i++) {  
          hash = hash * a + str.charAt(i);  
          a = a * b;
       }
       return hash;
    }

### JS ###

Justin Sobel写的一个位操作的哈希函数。

public long JSHash(String str)  
       {  
          long hash = 1315423911;  
          for(int i = 0; i < str.length(); i++)  
          {  
             hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));  
          }  
          return hash;  
       }

### PJW ###

该散列算法是基于贝尔实验室的彼得J温伯格的的研究。在Compilers一书中（原则，技术和工具），建议采用这个算法的散列函数的哈希方法。

public long PJWHash(String str)  
       {  
          long BitsInUnsignedInt = (long)(4 * 8);  
          long ThreeQuarters     = (long)((BitsInUnsignedInt  * 3) / 4);  
          long OneEighth         = (long)(BitsInUnsignedInt / 8);  
          long HighBits          = (long)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);  
          long hash              = 0;  
          long test              = 0;  
          for(int i = 0; i < str.length(); i++)  
          {  
             hash = (hash << OneEighth) + str.charAt(i);  
             if((test = hash & HighBits)  != 0)  
             {  
                hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));  
             }  
          }  
          return hash;  
       }

### ELF ###

和PJW很相似，在Unix系统中使用的较多。

public long ELFHash(String str)  
       {  
          long hash = 0;  
          long x    = 0;  
          for(int i = 0; i < str.length(); i++)  
          {  
             hash = (hash << 4) + str.charAt(i);  
             if((x = hash & 0xF0000000L) != 0)  
             {  
                hash ^= (x >> 24);  
             }  
             hash &= ~x;  
          }  
          return hash;  
       }

### BKDR ###

这个算法来自Brian Kernighan 和 Dennis Ritchie的 The C Programming Language。这是一个很简单的哈希算法,使用了一系列奇怪的数字,形式如31,3131,31…31,看上去和DJB算法很相似。

public long BKDRHash(String str)  
       {  
          long seed = 131; // 31 131 1313 13131 131313 etc.. 
          long hash = 0;  
          for(int i = 0; i < str.length(); i++)  
          {  
             hash = (hash * seed) + str.charAt(i);  
          }  
          return hash;  
       }

### SDBM ###

这个算法在开源的SDBM中使用，似乎对很多不同类型的数据都能得到不错的分布。

public long SDBMHash(String str)  
       {  
          long hash = 0;  
          for(int i = 0; i < str.length(); i++)  
          {  
             hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;  
          }  
          return hash;  
       }

### DJB ###

这个算法是Daniel J.Bernstein 教授发明的，是目前公布的最有效的哈希函数。

public long DJBHash(String str)  
       {  
          long hash = 5381;  
          for(int i = 0; i < str.length(); i++)  
          {  
             hash = ((hash << 5) + hash) + str.charAt(i);  
          }  
          return hash;  
       }

### DEK ###

由伟大的Knuth在《编程的艺术 第三卷》的第六章排序和搜索中给出。

public long DEKHash(String str)  
       {  
          long hash = str.length();  
          for(int i = 0; i < str.length(); i++)  
          {  
             hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i);  
          }  
          return hash;  
       }

### AP ###

public long APHash(String str)  
       {  
          long hash = 0xAAAAAAAA;  
          for(int i = 0; i < str.length(); i++)  
          {  
             if ((i & 1) == 0)  
             {  
                hash ^= ((hash << 7) ^ str.charAt(i) * (hash >> 3));  
             }  
             else  
             {  
                hash ^= (~((hash << 11) + str.charAt(i) ^ (hash >> 5)));  
             }  
          }  
          return hash;  
       }

### murmurhash ###

redis底层使用的哈希算法是murmurhash

unsigned long long MurmurHash64B ( const void * key, int len, unsigned int seed )
    {
    const unsigned int m = 0x5bd1e995;
    const int r = 24;
    
    unsigned int h1 = seed ^ len;
    unsigned int h2 = 0;
    
    const unsigned int * data = (const unsigned int *)key;
    
    while(len >= 8)
    {
    unsigned int k1 = *data++;
    k1 *= m; k1 ^= k1 >> r; k1 *= m;
    h1 *= m; h1 ^= k1;
    len -= 4;
    
    unsigned int k2 = *data++;
    k2 *= m; k2 ^= k2 >> r; k2 *= m;
    h2 *= m; h2 ^= k2;
    len -= 4;
    }
    
    if(len >= 4)
    {
    unsigned int k1 = *data++;
    k1 *= m; k1 ^= k1 >> r; k1 *= m;
    h1 *= m; h1 ^= k1;
    len -= 4;
    }
    
    switch(len)
    {
    case 3: h2 ^= ((unsigned char*)data)[2] << 16;
    case 2: h2 ^= ((unsigned char*)data)[1] << 8;
    case 1: h2 ^= ((unsigned char*)data)[0];
    h2 *= m;
    };
    
    h1 ^= h2 >> 18; h1 *= m;
    h2 ^= h1 >> 22; h2 *= m;
    h1 ^= h2 >> 17; h1 *= m;
    h2 ^= h1 >> 19; h2 *= m;
    
    unsigned long long h = h1;
    
    h = (h << 32) | h2;
    
    return h;
    }

[Link 1]: https://www.cnblogs.com/hzorac/p/5399042.html
[Hash]: https://baike.baidu.com/item/%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95/4960188?fr=aladdin&fromid=5737278&fromtitle=Hash%E7%AE%97%E6%B3%95