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

简单了解一下常见的几种散列算法&＃xff1f;

如果觉得对你有帮助&＃xff0c;能否点个赞或关个注&＃xff0c;以示鼓励笔者呢&＃xff1f;&＃xff01;博客目录 | 先点这里

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

前提概念

好的哈希函数

• list of hash functions - wikipedia

好的哈希函数

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

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

MD5 与 SHA

MD5

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

特性

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

SHA 家族

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

特性

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

对比

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

CRC

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

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

原理

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

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

• 不要跑&＃xff0c;CRC没这么难&＃xff01;&＃xff08;简单易懂的CRC原理阐述&＃xff09;

特性

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

代码

• redis-luttuce-crc16

MurmurHash

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

特性

• MurmurHash2 可以产生 32/64 bit 范围的散列值&＃xff0c;MurmurHash3 可以产生 32/128bit 范围的散列值
• MurmurHash 支持加盐&＃xff0c;即支持加一个种子值&＃xff0c;而获得不同的 hash 规律&＃xff0c;可以防止哈希洪水攻击&＃xff08;Hash-Flooding Attack

代码

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


• MurmurHash 的原理解析细节比较多&＃xff0c;没看懂&＃xff0c;就不贴了&＃xff0c;这里是一个 Guava 提供的 murmur3 使用例子
• murmur3 可以使用在一般的哈希值计算&＃xff0c;比如短链系统等
• redis-client-murmurhash
• guava-murmurhash3

MurmurHash3_最详细的介绍

times31/33

times33

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

原理

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

代码

private static int times33(String s) {int hash &＃61; 5381;char[] val &＃61; s.toCharArray();for (int i &＃61; 0; i < s.length(); i&＃43;&＃43;) {hash &＃61; ((hash << 5) &＃43; hash) &＃43; val[i];}// hash is a positive integer&＃xff0c;[0,2^31-1]hash &&＃61; Integer.MAX_VALUE;return hash;}


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

why

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

times31

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

原理

• 原理与 times33 一致&＃xff0c;仅仅是乘数和初始值的选择不一样
• 乘数是 31&＃xff0c;初始值是 0

代码

private static int times31(String s) {int hash &＃61; 0;char[] val &＃61; s.toCharArray();for (int i &＃61; 0; i < s.length(); i&＃43;&＃43;) {hash &＃61; ((hash << 5) - hash) &＃43; val[i];}return hash;}


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

why

• 为什么取 31
  31 和 33 都是奇素数&＃xff0c;理由其实跟 times33 差不多&＃xff0c;都是实验数据中&＃xff0c;采取比较好的奇素数

参考资料

• Time33 算法 - &＃64;作者&＃xff1a;wzcu

• Reason for 5381 number in DJB hash function?

• MurmurHash3_最详细的介绍 - &＃64;作者&＃xff1a;旧夏季 听风起

• 哈希洪水攻击&＃xff08;Hash-Flooding Attack&＃xff09;&＃xff1f;-&＃64;知乎

• 如果觉得对你有帮助&＃xff0c;能否点个赞或关个注&＃xff0c;以示鼓励笔者呢&＃xff1f;&＃xff01;