一，什么是哈希

哈希是将任意长度的数据转换为一个数字的过程。这个数字是在一个固定的范围之内的。
转换的方法称为哈希函数，原值经过哈希函数计算后得到的值称为哈希值。

1.哈希特点

(1)一致性：同一个值每次经过同一个哈希函数计算后得到的哈希值是一致的。

F(x)=rand() :每次返回一个随机值,是不好的哈希

(2)散列性：不同的值的哈希值尽量不同，理想情况下每个值对应于不同的数字。

F(x)=1 : 不管输入什么都返回1，是不好的哈希

2.冲突怎么解决

把一个大的集合映射到一个固定大小的集合中，肯定是存在冲突的。这个是抽屉原理或者叫鸽巢理论。

桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

（1）拉链法：

链表地址法是使用一个链表数组来存储相应数据，当hash遇到冲突的时候依次添加到链表的后面进行处理。Java里的HashMap是拉链法解决冲突的典型应用场景。

Java8的HashMap中，使用一个链表数组来存储数据，根据元素的哈希值确定存储的数组索引位置，当冲突时，就链接到元素后面形成一个链表，Java8中当链表长度超过8的时候就变成红黑树以优化性能，红黑树也可以视为拉链法的一种变形。

（2）开放地址法

开放地址法是指大小为 M 的数组保存 N 个键值对，其中 M >N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为“开放地址”哈希表。

线性探测法，就是比较常用的一种“开放地址”哈希表的一种实现方式。线性探测法的核心思想是当冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。简单来说就是：一旦发生冲突，就去寻找下 一个空的散列表地址，只要散列表足够大，空的散列地址总能找到。

Java8中的HashTable就是用线性探测法来解决冲突的。

    public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

    private void addEntry(int hash, K key, V value, int index) {
        modCount++;

        Entry<?,?> tab[] = table;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }

（2）冲突解决示例

举个例子，假如散列长度为8，哈希函数是：y=x%7。两种解决冲突的方式如下：

拉链法解决冲突

线性探测法解决冲突

二，几个常见哈希算法

1.MD5

MD5哈希算法是将任意字符散列到一个长度为128位的Bit数组中，得出的结果表示为一个32位的十六进制数字。

MD5哈希算法有以下几个特点：

1. 正像快速：原始数据可以快速计算出哈希值
2. 逆向困难：通过哈希值基本不可能推导出原始数据
3. 输入敏感：原始数据只要有一点变动，得到的哈希值差别很大
4. 冲突避免：很难找到不同的原始数据得到相同的哈希值

算法过程：

1. 数据填充：

将原数据的二进制值进行补齐。

（1）填充数据：使得长度模除512后得到448，留出64个bit来存储原信息的长度。填充规则是填充一个1，后面全部是0。

（2）填充长度数据：计算原数据的长度数据，填充到最后的64个bit上，如果消息长度数据大于64bit就使用低64位的数据。

2. 迭代计算：

将填充好的数据按照每份512的长度进行切分，对每一份依次进行处理，每份的处理方式是使用四个函数进行依次进行计算，每个函数都有四个输入参数，输出也是四个数字，输出的数字作为下一份数据的输入，所有份数的数据处理完毕，得到的四个数字连接起来就是最终的MD5值。

以下图片是整个迭代计算的过程示意图，其中四个初始参数和四个函数定义如下：

//四个初始参数值
A=0x67452301;
B=0xefcdab89;
C=0x98badcfe;
D=0x10325476;

//四个函数的定义
// a、b、c、d是每次计算时候的四个参数
F=(b&c)|((~b)&d);
F=(d&b)|((~d)&c);
F=b^c^d;
F=c^(b|(~d));

3. md5的java实现

package com.chybin.algorithm.chapter2;

/**
 * Create By 鸣宇淳 on 2019/12/26
 **/
public class MD5{
    /*
     *四个链接变量
     */
    private final int A=0x67452301;
    private final int B=0xefcdab89;
    private final int C=0x98badcfe;
    private final int D=0x10325476;
    /*
     *ABCD的临时变量
     */
    private int Atemp,Btemp,Ctemp,Dtemp;

    /*
     *常量ti
     *公式:floor(abs(sin(i+1))×(2pow32)
     */
    private final int K[]={
            0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee,
            0xf57c0faf,0x4787c62a,0xa8304613,0xfd469501,0x698098d8,
            0x8b44f7af,0xffff5bb1,0x895cd7be,0x6b901122,0xfd987193,
            0xa679438e,0x49b40821,0xf61e2562,0xc040b340,0x265e5a51,
            0xe9b6c7aa,0xd62f105d,0x02441453,0xd8a1e681,0xe7d3fbc8,
            0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed,0xa9e3e905,
            0xfcefa3f8,0x676f02d9,0x8d2a4c8a,0xfffa3942,0x8771f681,
            0x6d9d6122,0xfde5380c,0xa4beea44,0x4bdecfa9,0xf6bb4b60,
            0xbebfbc70,0x289b7ec6,0xeaa127fa,0xd4ef3085,0x04881d05,
            0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665,0xf4292244,
            0x432aff97,0xab9423a7,0xfc93a039,0x655b59c3,0x8f0ccc92,
            0xffeff47d,0x85845dd1,0x6fa87e4f,0xfe2ce6e0,0xa3014314,
            0x4e0811a1,0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391};
    /*
     *向左位移数,计算方法未知
     */
    private final int s[]={7,12,17,22,7,12,17,22,7,12,17,22,7,
            12,17,22,5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20,
            4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23,6,10,
            15,21,6,10,15,21,6,10,15,21,6,10,15,21};


    /*
     *初始化函数
     */
    private void init(){
        Atemp=A;
        Btemp=B;
        Ctemp=C;
        Dtemp=D;
    }
    /*
     *移动一定位数
     */
    private    int    shift(int a,int s){
        return(a<<s)|(a>>>(32-s));//右移的时候，高位一定要补零，而不是补充符号位
    }
    /*
     *主循环
     */
    private void MainLoop(int M[]){
        int F,g;
        int a=Atemp;
        int b=Btemp;
        int c=Ctemp;
        int d=Dtemp;
        for(int i = 0; i < 64; i ++){
            if(i<16){
                F=(b&c)|((~b)&d);
                g=i;
            }else if(i<32){
                F=(d&b)|((~d)&c);
                g=(5*i+1)%16;
            }else if(i<48){
                F=b^c^d;
                g=(3*i+5)%16;
            }else{
                F=c^(b|(~d));
                g=(7*i)%16;
            }
            int tmp=d;
            d=c;
            c=b;
            b=b+shift(a+F+K[i]+M[g],s[i]);
            a=tmp;
        }
        Atemp=a+Atemp;
        Btemp=b+Btemp;
        Ctemp=c+Ctemp;
        Dtemp=d+Dtemp;

    }
    /*
     *填充函数
     *处理后应满足bits≡448(mod512),字节就是bytes≡56（mode64)
     *填充方式为先加一个0,其它位补零
     *最后加上64位的原来长度
     */
    private int[] add(String str){
        int num=((str.length()+8)/64)+1;//以512位，64个字节为一组
        int strByte[]=new int[num*16];//64/4=16，所以有16个整数
        for(int i=0;i<num*16;i++){//全部初始化0
            strByte[i]=0;
        }
        int    i;
        for(i=0;i<str.length();i++){
            strByte[i>>2]|=str.charAt(i)<<((i%4)*8);//一个整数存储四个字节，小端序
        }
        strByte[i>>2]|=0x80<<((i%4)*8);//尾部添加1
        /*
         *添加原长度，长度指位的长度，所以要乘8，然后是小端序，所以放在倒数第二个,这里长度只用了32位
         */
        strByte[num*16-2]=str.length()*8;
        return strByte;
    }
    /*
     *调用函数
     */
    public String getMD5(String source){
        init();
        int strByte[]=add(source);
        for(int i=0;i<strByte.length/16;i++){
            int num[]=new int[16];
            for(int j=0;j<16;j++){
                num[j]=strByte[i*16+j];
            }
            MainLoop(num);
        }
        return changeHex(Atemp)+changeHex(Btemp)+changeHex(Ctemp)+changeHex(Dtemp);

    }
    /*
     *整数变成16进制字符串
     */
    private String changeHex(int a){
        String str="";
        for(int i=0;i<4;i++){
            str+=String.format("%2s", Integer.toHexString(((a>>i*8)%(1<<8))&0xff)).replace(' ', '0');

        }
        return str;
    }
    /*
     *单例
     */
    private static MD5 instance;
    public static MD5 getInstance(){
        if(instance==null){
            instance=new MD5();
        }
        return instance;
    }

    private MD5(){};

    public static void main(String[] args){
        String str=MD5.getInstance().getMD5("123");
        System.out.println(str);
    }
}

2.SHA

SHA类似MD5，也是一种信息摘要算法，也是将任意长度的字符串转换为固定长度的数字的算法。SHA算法是一个家族，有五个算法：SHA-1、SHA-224、SHA-256、SHA-384，和SHA-512。这些变体除了生成摘要的长度、循环运行的次数等一些微小差异外，算法的基本结构是一致的。

SHA-1算法的结果是一个160个bit的数字，比MD5的128个bit要长32位，碰撞几率要低了2^32倍。可是SHA-1和MD5一样已经被人破解，已经不安全了。

SHA-256从名字上看就表明了它的值存储在长度为256的bit数组中的，SHA-512信息摘要长度是512个bit。

SHA-224是SHA256的精简版本，SHA-384是SHA-512的精简版本，精简版本主要用在安全等级要求不太高的场景，比如只是验证下文件的完整性。使用什么版本的SHA取决于安全要求和算法速度，毕竟长度越长算法计算时间约长，但是安全等级高。

SHA算法过程：

SHA算法的底层原理和MD5很相似，只是在摘要分段和处理细节上有少许差别，他们都是第一步将原数据进行填充，填充到512的整数倍，填充的信息包括10数据填充和长度填充，第二步切分为相同大小的块，第三步进行对每一块迭代，每块进行N轮运算，最终得到的值拼接起来就是最终的哈希值。

以下是MD5、SHA-1、SHA-2系列的算法过程比较：

MD5算法过程示意图：

MD5是对每一块数据分为四个部分，用四个函数进行运算。最终生成128位的哈希值。

SHA-1算法过程示意图：

SHA-1是将每一块数据分为五个部分。

SHA-2算法过程示意图：

SHA-2是分为八个部分，算法也更加复杂。

3.SimHash

SimHash是Google提出的一种判断文档是否重复的哈希算法，他是将文本转换为一个64位的哈希值，然后计算两个哈希值的距离，如果小于n（n一般是3）就认为这两个文本是相似的。

之所以能够这样判断是否相似是因为SimHash算法不同于MD5之类的算法，SimHash算法是局部敏感的哈希算法，MD5算法是全局敏感的哈希算法。在MD5中原数据只要有一个字符的变化，哈希值就会变化很大，而在SimHash算法中，原数据变化一小部分，哈希值也只有很小一部分的变化，所以只要哈希值很类似，就意味着原数据就很类似。

算法实现：

参考这个博客【[Algorithm] 使用SimHash进行海量文本去重】

（1）第一步：哈希

1. 分词： 将文本进行分词，并给单词分配权重。
2. hash： 对每个次进行hash计算，得到哈希值。
3. 加权： 对每个单词的has进行加权。
4. 合并： 把上一步加权hash值合并累计起来。
5. 降维： 把上一步累加起来的值变为01。如果每一位大于0 记为 1，小于0 记为 0。

（2）第二步：计算海明距离

两个simhash对应二进制（01串）取值不同的数量称为这两个simhash的海明距离。

举例如下： 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。

异或就是如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。两个simhash值进行异或，得出的结果中1的个数就是海明距离。

判断两个文本是否相似，就计算两个simhash哈希值的海明距离，根据经验，如果海明距离小于3就可以判定两个文本是相似的。

4.GeoHash

GeoHash 算法将经纬度哈希为一个数字，然后将数字base32编码为一个字符串。

比如：北海公园的经纬度是：(39.928167,116.389550),对应的GeoHash值可以为wx4g、wx4g0、wx4g0s、wx4g0s8、wx4g0s8q。GeoHash值代表的是这个经纬度点所在的一个矩形区域，长度越长矩形面积约小，表示的越精确。

两个位置的GeoHash值前部分一样的位数越多，说明两个位置离得越近，百度地图的查找附近、滴滴打车查找附近的车辆功能就可以使用这个算法。

GeoHash算法过程

下面对于北海公园的经纬度(39.928167,116.389550)进行编码，了解下算法过程。

（1）第一步：纬度编码

将整个地球从水平方向上进行逐步切分，确定纬度39.928167在哪个区域中。

纬度范围是-90到90，每次平均分为两份，进行逐步细化地迭代。

1. 第一次迭代：处于-90到0的标记为0,0到90的标记为1，39.928167处于1的区间，所以最终结果的第一位是1。
2. 第二次迭代：对上一步标记为1的部分平分，0到45标记为0,45到90标记为1，39.928167标记为1处于0的区间，所以最终结果的第二位是0。
3. 第三次迭代：对上一步标记为0的部分平分，0到22.5标记为0,22.5到45标记为1，39.928167标记为1处于0的区间，所以最终结果的第三位是0
4. 第四次迭代：对上一步标记为0的部分平分，22.5到33.75标记为0,33.75到45标记为1，39.928167标记为1处于1的区间，所以最终结果的第三位是1。

经过N次迭代后，得到一个长度为N的二进制值，比如得到的值为1011100011，这个就是对纬度进行的编码最终值。

（2）第二步：经度编码

对经度的编码过程跟对纬度编码过程十分类似，不同点是经度范围是-180到180，对经度116.389550经过N次迭代后得到编码值。比如得到1101001011。这个就是对经度编码的最终值。

（3）第三步：合并经纬度

对纬度编码值、经度编码值进行合并，合并规则是奇数位放纬度、偶数位放经度，合并为一个新的二进制串。

（4）第四步：转换为字符串

将上一步合并的二进制11100 11101 00100 01111每5位一段转换为十进制，结果是28、29、4、15，Base32编码后为wx4g。这个就是北海公园的经纬度(39.928167,116.389550)最终的GeoHash编码值。

以下图表是二进制数字、base32字符对应表：

目录

一，什么是哈希函数？

二，哈希表（hash table）原理

三，为什么不是所有的 hash 函数都可以被用来加密？

四，哈希碰撞（hash collision）的解决方式

五，什么是好的哈希函数？

六，哈希函数的构造方法

七，为什么不能对可变的对象进行 hash 处理？

八，大型网站如何利用 hash 函数保护用户密码？

九，Python3.x 增加的随机性

十，其他 hash 算法

背景

哈希（hash）算法，原先是一种被用在资料编码中的技术，可以被用来加密要隐藏的资料，还可以被用来，比较不同文本的相似度。哈希算法属于信息摘要（Message Digest）算法。

区块链技术背后的底层原理之一，即为哈希算法。理解了哈希函数，自然就会理解区块链的挖矿模式。

全面的 hash 算法列表网址： ( http://burtleburtle.net/bob/hash/ )

一，什么是哈希函数？

哈希函数（hash function）: 也称为「散列函数」或「杂凑函数」。

h = H(M)

哈希函数将任意长度的消息 M，映射成为一个长度较短且长度固定的值 H（M）。H(M)即为散列值或哈希值（hash value）。

哈希算法是一种信息摘要（Message Digest）算法。对象的 hash 值比原对象拥有更低的内存复杂度。是一种压缩映射。

根据哈希函数所建立的表为哈希表。

2

二，哈希表（hash table）原理

哈希表（hash table）|散列表，是根据关键码值进行访问的数据结构。属于键和值之间的一 一对应关系。

通常提供查找（search），插入（insert），删除（delete）等操作。跟数组一样都是一种数据结构。与字典类似，通过键值对（key-indexed）来保存数据。

目前大部分动态语言的实现中都使用了哈希表。有些语音将哈希表乘坐字典，但是哈希表跟字典并不完全相同。哈希表是弱类型的，而字典是强类型的。

哈希表查找一个元素的时间复杂度为0（1），效率极高，这也是它的一个重要优点。

键（key）：操作数据的标识。

槽（bucket）：用于存放数据的单元。

创建自己的哈希表的一种方法：

class hashtable(object):
     
     def _int_ (self,length = 4): #在这里length = 4，即设置哈希表的初始长度为4
         self.array = [none]*length
         
     def hash1(self,key):
         length = len(self.array)
         return hash(key)%length # key的哈希值除以array列表的长度取余
     
     def is_full(self): # 根据哈希表里面项目的数量来更新长度
         items = 0
         for item in self.array: #通过self.array将项目的数量增加
             if items is not None:
                 items +=1
         return items > len(self.array)/2 #判断项目个数是否比array列表总长度的1/2大
     
     def double(self): #定义当容量过小时更新列表的方法
         hashtable2 = hashtable(length = len(self.array)*2) #设置hashble2的长度
         for i in range(len(self.array)):
             if self.array[i] is None:
                 contune
             for zep in self.array[i]:
                 hashble2.add(zep[0] , zep[1]) #将原hashtable2中的数据转移到hashtable2中
         self.array = hashtable2.array
         
     def add(self,key,value):
         index = self.hash1(key) #index设为（key）的hash1值
         if self.array[index] is not None: #如果array列表中的该位置已被占领
             for zep in self.array[index]:
                 if zep[0] == key: #如果zep为[key,_],则设置zep为[key，value]，
                    zep[1] == value  #即更新该位置存储的键对值
                    break
             else:
                 self.array[index].append([key,value]) #否则，在该位置添加键值对
         else:
             self.array[index] = []
             self.array[index].append([key,value]) #该位置为None，直接添加键值对
         if self.is_full():
             self.double()
             
     def get(self , key):
         index = self.hash(key)
         if self.zed[index] is None:
             raise KeyError() #所要寻找的键并不存在
         else:
             for zep in self.array[index]:
                 if zep[0] == key:
                     return zep[1]
                 raise KeyError() #并不存在

三，大型网站如何利用 hash 函数保护用户密码？

即使大型网站的数据库被攻破，也不会造成太大损失。为什么呢？这涉及到了哈希函数的两个主要特性：不可逆性与抗碰撞性。

利用哈希函数对用户密码进行加密：用户设置完密码后，会被转换成 hash 值，并保存到数据库中。如下图。

pip3 installsimhash

​被保存的只是转换后的哈希值，而不是原密码。

由于哈希（hash）函数是不可逆的，只能由输入产生输出，不能由输出产生输入。系统服务器无法根据每个 hash 值逆过来推算出原密码。因此即使是后台工作人员，也无法得知用户的原密码。

用户登录的时候，输入密码，经过 hash 操作后转换成 hash 值，再与数据库中被保存的 hash 值进行对比。hash 值完全一样，则密码正确。

四，为什么不是所有的 hash 函数都可以被用来加密？

不是所有的 hash 函数都可以被用来加密，这就涉及到了哈希碰撞（hash collision）。

对于 hash 算法，一般情况下，不同的数据会生成不同的哈希值。但是如果两个不同的数据，经过 Hash 函数计算后，得到的 Hash 值一样，则为哈希碰撞（collision）。

即 f (key1) = f(key2)

哈希碰撞无法被完全避免。只能降低其发生概率。

碰撞攻击则是找到另一个跟原密码具有相同 hash 值的字符串。

为了提高安全性，只有加密哈希函数（cryptgraphic hash functions）可以被用来加密。如 SHA256, SHA512, Ripemd， WHIRLPOOL 等 。这类函数的 hash 破解异常困难，几乎不太可能出现 hash 碰撞。

五，哈希碰撞（hash collision）的解决方式

一，开放寻址法（open addressing)

二，拉链法

开放寻址法的总体设计原理为：出现哈希碰撞时，重新检测一个空闲位置，并插入。

但是这样会产生一个问题，即占用其他槽位的空间，以致于后续的插入操作更容易出现冲突。因此在利用开放寻址法的时候，装载因子最好保持在0.5以下。

装载因子 = 

[1] 开放寻址法有：

• 线性探测器（Linear Probing）
• 二次探测法（Quadratic Probing）
• 随机探测法
• 双散列（Double hashing）
• 再哈希法
• 建立一个公共溢出区

线性探测法介绍：

线性探测法为开放寻址法最简单的一种实现。

线性探测法用来解决哈希碰撞的原理是：当某个被给定键在散列表中的对应单元已被占用时（即我们向当前哈希表写入数据时发生了冲突），会检测散列表中离冲突单元最近的空闲单元。并把该键值对写入到下一个不为空的位置。

只要哈希表未被填满，总能找到一个不发生冲突的单元。

再哈希法：

再哈希法用来解决哈希碰撞的原理是：两个值产生冲突时，通过下面算式，计算另一地址，直到不再冲突。

Hi = R * Hi(key) [i = 1,2,...k]

同样的关键字，同样的哈希函数，用不同的处理哈希碰撞的方法，得到的哈希函数值也不同。

6

六，什么是好的哈希函数？

哈希表的关键点就在于哈希函数的选择。

若对于关键字集合中的，任意一个关键字，经过哈希函数，映像到地址集合中，任何一个地址的概率是相等的，则为均匀散列函数（uniform hash function）。也即好的哈希函数。

这种方法通过将关键字映射到“均匀分布的随机地址”来减少冲突。

目前的哈希算法都能良好的将key进行比较均匀的分布。

6

七，哈希函数的构造方法：

• 直接定址法
• 除留余数法
• 数字分析法
• 折叠法
• 平方取中法

直接定址法：取关键字，或关键字的某个线性函数值，为哈希地址。

即：H（key） = key 或 H (key) = a * key + b

链地址法：将所有相似关键词的记录存储在同一线性链表中。

8

八，为什么不能对可变的对象进行 hash 处理？

首先要了解两个概念，可哈希性（hashable）与不可哈希性（unhashable）。

可哈希性（hashable）：可哈希的数据类型为不可变的数据结构（如字符串 srt，元组 tuple，对象集 objects 等）。这种数据被称为可哈希性。

不可哈希性：不可哈希的数据类型，为可变的数据结构（如字典 dict，列表 list 和集合 set 等）。

如果对可变的对象进行哈希处理，则每次对象更新时，都需要更新哈希表。这样我们则需要将对象移至不同的数据集，这种操作会使花费过大。

因此设定不能对可变的对象进行 hash 处理。

九，Python3.x 增加的随机性

Python3.x添加了 hash 算法的随机性，以提高安全性，因此对于每个新的 python 调用，同样的数据源生成的结果都将不同。 下面为算法实例。

​

哈希方法有（MD5, SHA1, SHA256 与 SHA512 等）。常用的有 SH256 与 SHA512，即上文提到的加密哈希函数（cryptgraphic hash functions）。MD5 与 SHA1 不再常用。

• MDH5 (不常用)
• SHA1 (不常用)
• SHA256 (常用)
• SHA512 (常用)

10

十，其他 hash 算法**

1. simhash 算法:

这是一种局部敏感的 hash 算法，它产生的签名在一定程度上可以表征原内容的相似度。

可以被用来比较文本的相似度。

如下代码安装 simhash 模块。

pip3 installsimhash

2. Imagehash 算法:

Imagehash 算法为感知哈希算法（perceptual Hash Algorithm）。

常被用来检测图像和视频的差异。

如下代码安装 Imagehash 模块。

pip3 install simhash

例如：可以通过比较两张图片的 hash 值来判断相似度。下面为比较两张相似图片的代码示例。

​

​

输出为：

hash(image1) =00fd43c3**f**fffffff

hash(image2) =00fd43c3f**e**ffffff

从输出结果可以看到两张图片的 hash 值非常相似。相似的图片可以生成相似的哈希值是 Imagehash 的特点。

后续再详细更新哈希碰撞的解决方式

​

哈希原理

C++11提供的unordered系列的容器之所以在查找方面能够达到$O(1)$的复杂度，是因为其底层使用了哈希的结构

一、哈希的概念：

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为$O(N)$，平衡树中为树的高度，即$O(log2N)$，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素

当向该结构中:

1. 插入元素
   根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

2. 搜索元素
   对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？

二、哈希冲突

对于两个数据元素的关键字ki 和kj (i != j)，有 ki != kj ，但有：Hash( ki) == Hash(kj)，即：不同关键字通过 相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 发生哈希冲突该如何处理呢？

三、哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。 哈希函数设计原则：

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0 到m-1之间
• 哈希函数计算出来的地址能均匀分布在整个空间中
• 哈希函数应该比较简单

常见哈希函数

1. 直接定制法–(常用)
   取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
   优点：简单、均匀 。
   缺点：需要事先 知道关键字的分布情况
   使用场景：适合查找比较小且连续的情况

2. 除留余数法--(常用)
   设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函 数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3. 平方取中法
   假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

4. 折叠法
   折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加 求和，并按散列表表长，取后几位作为散列地址。
   折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5. 随机数法
   选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为 随机数函数。
   通常应用于关键字长度不等时采用此法

6. 数学分析法

四、解决哈希冲突的方法

1. 闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那 么可以把key存放到冲突位置中的“下一个” 空位置中去。

那如何寻找下一个空位置呢？

1. 线性探测
   比如前面的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论 上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
   线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

• 插入
  a.通过哈希函数获取待插入元素在哈希表中的位置
  b.如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探 测找到下一个空位置，插入新元素
  
• 删除
  采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他 元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标 记的伪删除法来删除一个元素

// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE}

线性探测的实现

// 注意：假如实现的哈希表中元素唯一，即key相同的元素不再进行插入
// 为了实现简单，此哈希表中我们将比较直接与元素绑定在一起
template<class K, class V>
class HashTable
{
	struct Elem
	{
		pair<K, V> _val;
		State _state;
	};
	
public:
	HashTable(size_t capacity = 3)
	: _ht(capacity)
	, _size(0)
	{
		for(size_t i = 0; i < capacity; ++i)
		_ht[i]._state = EMPTY;
	}
	
	bool Insert(const pair<K, V>& val)
	{
		// 检测哈希表底层空间是否充足
		// _CheckCapacity();
		size_t hashAddr = HashFunc(key);
		// size_t startAddr = hashAddr;
		while(_ht[hashAddr]._state != EMPTY)
		{
			if(_ht[hashAddr]._state == EXIST &&
 				    _ht[hashAddr]._val.first == key)
				return false;
			hashAddr++;
			if(hashAddr == _ht.capacity())
				hashAddr = 0;
		/*
		// 转一圈也没有找到，注意：动态哈希表，该种情况可以不用考		虑，哈希表中元素个数
		到达一定的数量，哈希冲突概率会增大，需要扩容来降低哈希冲突，	因此哈希表中元素是不会存满的
		if(hashAddr == startAddr)
				return false;
		*/
		}
		// 插入元素
		_ht[hashAddr]._state = EXIST;
		_ht[hashAddr]._val = val;
		_size++;
		return true;
	}
	
	int Find(const K& key)
	{
		size_t hashAddr = HashFunc(key);
		while(_ht[hashAddr]._state != EMPTY)
		{
			if(_ht[hashAddr]._state == EXIST && 					
				_ht[hashAddr]._val.first == key)
				return hashAddr;
				
			hashAddr++;
		}
		return hashAddr;
	}
	
	bool Erase(const K& key)
	{
		int index = Find(key);
		if(-1 != index)
		{
			_ht[index]._state = DELETE;
			_size++;
			return true;
		}
		return false;
	}
	
	size_t Size()const;
	
	bool Empty() const;
	
	void Swap(HashTable<K, V, HF>& ht);
	
private:
	size_t HashFunc(const K& key)
	{
		return key % _ht.capacity();
	}
	
private:
	vector<Elem> _ht;
	size_t _size;
};

思考：哈希表什么情况下进行扩容？如何扩容？

void CheckCapacity()
{
	if(_size * 10 / _ht.capacity() >= 7)
	{
		HashTable<K, V, HF> newHt(GetNextPrime(ht.capacity));
		for(size_t i = 0; i < _ht.capacity(); ++i)
		{
			if(_ht[i]._state == EXIST)
				newHt.Insert(_ht[i]._val);
		}
		Swap(newHt);
	}
}

线性探测优点：实现非常简单，

线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据 了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。如何缓解呢？

2.二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就 是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi = （H0 + i^2)%m, 或者： Hi = （H0 + i^2）% m，H（i + 1） = （H0 + （i + 1）^2）% m,所以H（i + 1） = Hi + 2i + 1。其中：i = 1,2,3…， 是通过散列函数Hash(x)对元素的关键码 key 进行 计算得到的位置，m是表的大小。

对于前面如果要插入44，产生冲突，使用解决后的情况为：

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置 都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装 满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷

2. 开散列

1. 开散列概念
   开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码 归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结 点存储在哈希表中。

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

2. 开散列实现

template<class V>
struct HashBucketNode
{
	HashBucketNode(const V& data)
	: _pNext(nullptr), _data(data)
	{}
	HashBucketNode<V>* _pNext;
	V _data;
};
// 本文所实现的哈希桶中key是唯一的

template<class V>
class HashBucket
{
	typedef HashBucketNode<V> Node;
	typedef Node* PNode;
public:
	HashBucket(size_t capacity = 3)
	: _size(0)
	{ 
		_ht.resize(GetNextPrime(capacity), nullptr);
	}
	// 哈希桶中的元素不能重复	
	PNode* Insert(const V& data)
	{
		// 确认是否需要扩容。。。
		// _CheckCapacity();
		// 1. 计算元素所在的桶号
		size_t bucketNo = HashFunc(data);
		// 2. 检测该元素是否在桶中
		PNode pCur = _ht[bucketNo];
		while(pCur)
		{
			if(pCur->_data == data)
				return pCur;
			pCur = pCur->_pNext;
		}
		// 3. 插入新元素
		pCur = new Node(data);
		pCur->_pNext = _ht[bucketNo];
		_ht[bucketNo] = pCur;
		_size++;	
		return pCur;
	}
	// 删除哈希桶中为data的元素(data不会重复)，返回删除元素的下一个节点
	PNode* Erase(const V& data)
	{
		size_t bucketNo = HashFunc(data);
		PNode pCur = _ht[bucketNo];
		PNode pPrev = nullptr, pRet = nullptr;
		while(pCur)
		{
			if(pCur->_data == data)
			{
				if(pCur == _ht[bucketNo])
					_ht[bucketNo] = pCur->_pNext;
				else
					pPrev->_pNext = pCur->_pNext;
				pRet = pCur->_pNext;
				delete pCur;
				_size--;
				return pRet;
			}
		}
	return nullptr;
	}
	
	PNode* Find(const V& data);

	size_t Size()const;

	bool Empty()const;

	void Clear();

	bool BucketCount()const;

	void Swap(HashBucket<V, HF>& ht;

	~HashBucket();

private:

	size_t HashFunc(const V& data)
	{
		return data%_ht.capacity();
	}
private:
	vector<PNode*> _ht;
	size_t _size; // 哈希表中有效元素的个数
}；

3. 开散列增容
   桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件

怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容

void _CheckCapacity()
{
	size_t bucketCount = BucketCount();
	if(_size == bucketCount)
	{
		HashBucket<V, HF> newHt(bucketCount);
		for(size_t bucketIdx = 0; bucketIdx < bucketCount; 			
							++bucketIdx)
		{
			PNode pCur = _ht[bucketIdx];
			while(pCur)
			{
				// 将该节点从原哈希表中拆出来
				_ht[bucketIdx] = pCur->_pNext;
				// 将该节点插入到新哈希表中
				size_t bucketNo = newHt.HashFunc(pCur->_data);
				pCur->_pNext = newHt._ht[bucketNo];
				newHt._ht[bucketNo] = pCur;
				pCur = _ht[bucketIdx];
			}
		}
		newHt._size = _size;
		this->Swap(newHt);
	}
}

4. 开散列的思考

只能存储key为整形的元素，其他类型怎么解决？

// 哈希函数采用处理余数法，被模的key必须要为整形才可以处理，此处提供将key转化为整形的方法
// 整形数据不需要转化
template<class T>
class DefHashF
{
public:
	size_t operator()(const T& val)
	{
		return val;
	}
};

// key为字符串类型，需要将其转化为整形
class Str2Int
{
public:
	size_t operator()(const string& s)
	{
		const char* str = s.c_str();
		unsigned int seed = 131; // 31 131 1313 13131 131313
		unsigned int hash = 0;
		while (*str)
		{
			hash = hash * seed + (*str++);
		}
	return (hash & 0x7FFFFFFF);
	}
};

// 为了实现简单，此哈希表中我们将比较直接与元素绑定在一起
template<class V, class HF>
class HashBucket
{
	// ……
private:
	size_t HashFunc(const V& data)
	{
		return HF()(data.first)%_ht.capacity();
	}
};

除留余数法，最好模一个素数，如何每次快速取一个类似两倍关系的素数？

const int PRIMECOUNT = 28;
const size_t primeList[PRIMECOUNT] =
{
	53ul, 97ul, 193ul, 389ul, 769ul,
	1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
	49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
	1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
	50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
	1610612741ul, 3221225473ul, 4294967291ul
};

size_t GetNextPrime(size_t prime)
{
	size_t i = 0;
	for(; i < PRIMECOUNT; ++i)
	{
		if(primeList[i] > prime)
			return primeList[i];
	}
	return primeList[PRIMECOUNT - 1];
}

开散列与闭散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间

最后最后再说一下开散列和闭散列能否用vector自定义的扩容方式？
答案是不可以。

• vector底层的扩容方式为：申请新空间–>拷贝元素—>释放旧空间,
• 在闭散列和开散列中共同的问题是：在计算哈希地址的时候用到data%capacity，而vector是直接拷贝过来，在完成扩容后，capacity已经改变，再去用data%capacity就无法正确找到元素。
• 而在开散列中，vector每个元素存放的是每个哈希链的首地址，在释放旧空间的时候就已经把哈希链释放掉了，在新空间中却仍然在使用，就会发生错误

五、模拟实现哈希

github源码