【基础算法】简单了解一下常见的几种散列算法？

2022-08-05 14:46:44

简单了解一下常见的几种散列算法？

如果觉得对你有帮助，能否点个赞或关个注，以示鼓励笔者呢？！博客目录 | 先点这里

前提概念
- 好的哈希函数
MD5 与 SHA
- MD5
- SHA 家族
CRC
MurmurHash
times31/33
- times33
- times31

前提概念

好的哈希函数

好的哈希函数应该具备如下几种特性

One-way 单向性
输出确定，且无法逆推出源数据，即单向散列函数
Collision-resistant 抗冲突性
产生两个相同散列值的概率低
Avalanche effect 雪崩效应
原始数据的微小改动，会导致散列值巨大的差异

MD5 与 SHA

MD5

md5 摘要算法，又称 “MD5 Message-Digest Algorithm”, 是一种不可逆向的密码散列函数。

特性

任意长度的原始数据，都将输出定长为 128 bit 的散列值
属于加密散列函数，计算较为耗费 CPU 资源

SHA 家族

SHA 家族的加密算法，又称 “Secure Hash Algorithm”, 是一个密码散列函数家族，发布了多个版本的 SHA 加密函数，如 SHA-0,SHA-1,SHA-2,SHA-3 等

特性

大部分仅支持 2^64 -1 的输入数据，根据不同的版本，有不同的位长，如 160,224,256,384,512 等，位数较长
- sha-0,sha-1 输入不超过 2^64-1, 输出定长 160 bit

对比

MD5 和 SHA 通常都用在安全加密领域，因为都涉及数字加密，所以计算量都比较大，都比较消费 CPU 资源

CRC

CRC 算法 ("Cyclic Redundancy Check") ，又称循环冗余校验算法，是一种常用于通信链路检错，判断数据是否损坏的散列函数，但也不局限于此，它的基本原理是利用除法与余数的原理来做为错误侦测的

我们进行通信时的网络信道并不总是可靠的。为了增加可靠性，我们需要在传输数据后加上一些冗余的码字。如果接收方能够通过它们直接纠正错误，那么我们就称之为纠错码（Error Correcting Code），而 CRC 就是一种优秀的检错码，因为 CRC 具有良好的雪崩效应，即单个 bit 发生改变，也会导致散列值发生较大的改变，所以得以在通讯领域广泛应用。

原理

计算CRC的过程，就是用一个特殊的“除法”，来得到余数，这个余数就是CRC，而这里的除数则是一种 “模二除法”
通讯传送中，发送方会在原始数据末尾加上 CRC 检错码，并与接收方约定好 “除数 (多项式)”，最会得到余数 (CRC 值)，接收方就会以收到的原始数据除以约定好的除数，看看最终的结果是否与 CRC 检错码一致

比如发送发传输了一段二进制数据，并附上 CRC 校验码。接收方就可以根据所接收到的二进制数据的 CRC 散列值与接收到的 CRC 检错码进行比对，如果不一致，就代表接收的数据可能在通讯传输过程中有缺失或错误

不要跑，CRC没这么难！（简单易懂的CRC原理阐述）

特性

CRC 的协议有非常多种，比如 CCITT, MODBUS 等
CRC 根据多项式的不同也会产生不同长度的检错码 (散列值)，比如 CRC-8,CRC-16,CRC-32,CRC-64, 分别对产生对应 8,16,32,64 位长度的检错码，具有一定的数据压缩映射能力

代码

redis-luttuce-crc16

MurmurHash

MurmurHash 是一种非加密型的散列函数，相比加密型散列函数，速度更快，差值最大可以达到几十倍，所以更适用于一般场景的哈希检索操作。MurmurHash 经历过多个版本的迭代，并有多种变种，当前最新版是 MurmurHash3。
且已被广泛应用在多种分布式系统中，比如 Redis, Kafka, Hbase, ElasticSearch

特性

MurmurHash2 可以产生 32/64 bit 范围的散列值，MurmurHash3 可以产生 32/128bit 范围的散列值

代码

    public static void main(String[] args) {
        HashFunction function = Hashing.murmur3_32();
        System.out.println(function.hashBytes("abcd".getBytes()).asInt());
        // output = 1139631978
    }

MurmurHash 的原理资源还是比较少的，而且细节也比较多，没看懂，就不贴了，这里是一个 Guava 提供的 murmur3 使用例子
murmur3 可以使用在一般的哈希值计算，比如短链系统等
redis-client-murmurhash
guava-murmurhash3

MurmurHash3_最详细的介绍

times31/33

times33

Times33 算法是一个简单的对 “字符串” 进行哈希的函数，又称 “DJB Hash Function” or “DJBX33A”

原理

对字符串 s 进行逐个字符遍历，每次循环乘以 33，并加上 s[i] 字符的 ascii 码 , 然后求和即可
乘数是33, hash 初始值为 5381

代码

    private static int times33(String s) {
        int hash = 5381;

        char[] val = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            hash = ((hash << 5) + hash) + val[i];
        }

        // hash is a positive integer，[0,2^31-1]
        hash &= Integer.MAX_VALUE;
        return hash;
    }

a * 33 = a * 2^5 + a = a * 32 + a
hash &= 0x7fffffff 是为了获得 0 或正整数，因为 Java 的 int 是有符号整数，只能表示 [0, 2^31 -1] 的整数

why

为什么取 33?
- 并没有人给于一个比较充分的理由说明，不过通过对[1,256]数值的实验证明，偶数的哈希分布非常差，冲突较高，所以就剩下 128 个奇数，并不是 33 就是最佳的选项
- 奇素数，哈希分布相比偶数更为良好
初始值为什么是 5381?
- 没有太多特别的理由，仅仅是在测试中，发现 5381 这个数字，在算法中哈希冲突和分布更好表现不错
- Reason for 5381 number in DJB hash function?

times31

times31 其实是 Java String hashcode 函数所采用的算法，因其思想类似 times33, 但数值采用 31 ,所以被习惯性称之 times31

原理

原理与 times33 一致，仅仅是乘数和初始值的选择不一样
乘数是 31，初始值是 0

代码

    private static int times31(String s) {
        int hash = 0;

        char[] val = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            hash = ((hash << 5) - hash) + val[i];
        }
        
        return hash;
    }

hash = ((hash << 5) - hash) + val[i] 等价于 hash = 31 * hash + val[i]
JDK 显式代码是 31 * hash, 是因为编译器会自行优化