Hash算法小结

https://www.jianshu.com/p/bf1d7eee28d0
http://blog.jobbole.com/106733/
https://blog.csdn.net/v_JULY_v/article/details/6256463
http://www.alloyteam.com/2017/05/hash-functions-introduction/
http://blog.csdn.net/l1028386804/article/details/54573106

Hash算法，我们经常碰到，最近抽空整理一下哈希相关的东西

• Hash简介
• Hash在数据结构中的应用
• Hash碰撞的一些解决方法
• Hash在安全领域的应用

Hash 简介

什么是Hash

Hash算法又称为杂凑算法、摘要（digest）算法、散列算法、指纹（fingerprint）算法，可以将任意长度的二进制明文映射成较短（固定长度）二进制串（hash值）。与指纹一样，这种标志与明文中的每一个字节都相关，当原文件发生变化时，其标志值也会发生变化。

Hash算法的特点

一个优秀的Hash算法,具有一下几个特点：

• 正向快速：给定原文和Hash算法，在有限时间和资源内能计算得到Hash值
• 逆向困难：给定若干Hash值，在有限时间内无法（基本不可能）逆推出原文
• 输入敏感：原始输入信息发生任何变化，新产生的Hash值应该发生很大变化
• 避免碰撞：很难找到两段内容不同的明文，使得他们Hash值一致（即发生碰撞）

对于任意两个不同的数据块，其Hash值相同的可能性绩效；对于一个给定的数据块，找到和其Hash值相同的数据块极为困难。

在不同的使用场景，如数据将结构或者安全领域，会对其中某一些特点有一些侧重点。

Hash 在数据结构中的应用

在数据结构中，对速度比较重视，对抗碰撞不太看重，只要保证Hash均匀分布就可以了。例如hashmap,hash(key)的目的加快键值对的查找，key的作用是将元素适当地放在各个桶里，只要保证元素尽量均匀。

• JDK中String.hashCode()

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }
  

  hash值的计算公式：s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]

这里为什么选用31作为hashcode乘子

• 31是一个不大不小的奇质数。选择偶数在乘法运算中会溢出，乘2相当与移位。

• 可以被JVM优化，31*i=(2<<5)-i,乘法运算可以被移位和减法代替;

• HashMap中的hash(Object obj)方法

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
  

这里进行了一次抑或运算，可以降低冲突。

Hash碰撞的一些解决方法

由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。
通过构造性能良好的哈希函数，可以减少冲突，但一般不可避免完全冲突。
常用的解决冲突的方法有一下几种：

开放定址法

从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素。
在开放定址法中解决冲突的方法有：线行探查法、平方探查法、双散列函数探查法。
开放定址法的缺点在于删除元素的时候不能真的删除，否则会引起查找错误，只能做一个特殊标记。只到有下个元素插入才能真正删除该元素。
简而言之：发生冲突，计算出来的hash值上加一个增量，增量可以有以下几种取法

• 线性探测再散列

  增量为1，依次向后查找。

• 二次探测再散列

  增量为平方，依次查找

• 伪随机探测再散列

  生成一个随机增量，进行查找

再哈希法

就是同时构造多个不同的哈希函数：
Hi = RHi(key) i= 1,2,3 … k;
当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。

链地址法

链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。

建立公共溢出区

将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区

Hash在安全领域的应用

在加解密技术中，hash算法常用于消息摘要和签名，对消息进行完整性校验。因此，对于抗碰撞和抗篡改的要求比较高。

Hash算法的实现：求模算法，异或，附加运算

目前比较常见的摘要算法有：MD5、SHA-1、SHA256、SM3等。

MD5算法

/**
 * MD5摘要算法
 * @param plain 明文
 * @return 密文
 * @throws Exception 异常
 */
public static byte[] MD5Digest(byte[] plain)throws Exception{
    MessageDigest md = null;
    md = MessageDigest.getInstance(MD5);
    md.reset();
    md.update(plain);
    byte[] result = md.digest();
    return result;

}

SHA-1算法

/**
 * SHA-1
 * @param plain
 * @return
 */
public static byte[] SHA1Digest(byte[] plain) throws Exception{
    MessageDigest md = null;
    md = MessageDigest.getInstance(SHA1);
    md.reset();
    md.update(plain);
    byte[] result = md.digest();
    return result;
}

SHA256

/**
 * SHA-256
 * @param plain
 * @return
 */
public static byte[] SHA256Digest(byte[] plain) throws Exception {
    MessageDigest md = null;
    md = MessageDigest.getInstance(SHA256);
    md.reset();
    md.update(plain);
    byte[] result = md.digest();
    return result;
}

SM3

/**
 * SM3 摘要算法
 * @param plain 明文
 * @return
 */
public static byte[] SM3Digest(byte[] plain) throws Exception {
    SM3Digest sm3Digest = new SM3Digest();
    byte[] result = null;
    try {
        sm3Digest.update(plain,0,plain.length);
        result = new byte[sm3Digest.getDigestSize()];
        sm3Digest.doFinal(result,0);
    }catch (Exception ex){
        throw new Exception(ex);
    }
    return result;
}