如何选择Hash算法_vlambda技术博客

vlambda
2022-03-16

如何选择Hash算法

什么是Hash？

Hash是把任意长度的输入，转变成固定长度的输出，可以认为这是一种压缩映射。

Hash算法有哪些？

CRC(循环冗余校验)、MD5、SHA1、CityHash、MurmurHash、BKDRHash等等

优秀的Hash算法应有以下特点：

固定长度。散列函数可以接受任意大小的数据，并输出固定长度的散列值。
雪崩效应。原始数据哪怕只有一个字节的修改，得到的 hash 值都会发生巨大的变化。
单向。只能从原始数据计算得到 hash 值，不能从 hash 值计算得到原始数据。
低碰撞率。标准的 MD5 算法理论碰撞概率是 2 的 128 次方分之一。由于这种算法的碰撞概率很小，我们经常用它来当作唯一值。

下面介绍一些常用的Hash算法

BKDRHash

它是常用的字符串Hash函数中较好的一个，类似的还有APHash，DJBHash，JSHash，RSHash，SDBMHash等。用于在为字符串产生一个数字Hash值的场景。

算法实现：

unsigned int BKDRHash1(char *str) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0;while (*str) {  hash = hash * seed + (*str++); } return (hash & 0x7FFFFFFF); // 取模 long int 的上限值}

算法的种子一般都采用2^n-1的奇数，这里采用31，有两个好处：

选择质数作为乘子，会大大降低hash冲突的概率。质数的值越大，hash冲突率越低
31参与乘法运算，可以被 JVM 优化，31 * i = (i << 5) - i

Java中字符串的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;}

MD5

MD5会产生128 比特的hash值，一般应用于一致性验证、数字签名、安全访问认证等场景。算法具有以下特点：

压缩性：任意长度的数据，算出的 MD5 值长度都是固定的。
容易计算：从原数据计算出 MD5 值很容易。
抗修改性：对原数据进行任何改动，哪怕只修改 1 个字节，所得到的 MD5 值都有很大区别。
强抗碰撞：理论碰撞概率是 2 的 128 次方分之一，想找到一个具有相同 MD5 值的数据（即伪造数据）是非常困难的。

前些年，我国的王小云院士已经破解了MD5，她的研究成果是给定消息 M1，能够计算获取 M2，使得 M2 产生的散列值与 M1 产生的散列值相同。业界专家普林斯顿计算机教授 Edward Felten 等强烈呼吁信息体系的设计者赶快更换签名算法，而且他们侧重这是一个需要当即处理的问题。

SHA1

安全哈希算法（Secure Hash Algorithm）主要适用于数字签名标准里面定义的数字签名算法（Digital Signature Algorithm DSA）。对于长度小于 2^64 位的消息，SHA1 会产生一个 160 位的消息摘要。当接收到消息的时候，这个消息摘要可以用来验证数据的完整性。

MD5 与SHA-1均是从MD4 发展而来，它们的结构和强度等特性有很多相似之处；

SHA-1与MD5 的区别：

SHA-1摘要比MD5 摘要长 32 比特；
SHA-1强行破解的强度更大。
SHA-1 的循环计算步骤比MD5 多（80:64）且要处理的缓存大（160 比特:128 比特），SHA-1 的运行速度比MD5 慢。

CRC

循环冗余校验，其特点是:检错能力极强，开销小，易于用编码器及检测电路实现，主要用于数据的完整性校验。从其检错能力来看，它所不能发现的错误的几率仅为0.0047%以下。

基本原理：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC码）r位，并附在信息后边，构成一个新的二进制码序列数共(k+r)位，最后发送出去。在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。

应用：著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC-CCITT，WinRAR、NERO、ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。

MurmurHash

是一种非加密型哈希函数，适用于一般的哈希检索操作。该算法最新版本是 MurmurHash3，基于 MurmurHash2 改进了一些小瑕疵，使得速度更快，实现了 32 位（低延时）、128 位 HashKey，尤其对大块的数据，具有较高的平衡性与低碰撞率。

MurmurHash 的随机分布特征表现更良好，不关注安全性，计算效率比安全散列算法（MD5等）快几十倍。在 Redis，Memcached，Cassandra，HBase，Lucene 都使用了这种 hash 算法。

一些常用的HashCode实例

HashMap中的hashCode

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

这里为什么不直接使用key的hashCode，有以下几个原因：

取模做位与运算的时候，刚开始数组的长度一般比较小，只利用了低16位,高16位是用不到的。这种情况下，产生hash冲突的概率会大大增加。这样保证了对象的hashCode的高16位的变化能反应到低16位中，减少了hash冲突的情况。
选用异或的方式是因为&和|都会使得结果偏向0或者1。

Kafka根据key计算分区，采用了Murmur2算法

public int partition(String topic, Object key, byte[] keyBytes, Object value, byte[] valueBytes, Cluster cluster, int numPartitions) { if (keyBytes == null) { return stickyPartitionCache.partition(topic, cluster); } // hash the keyBytes to choose a partition return Utils.toPositive(Utils.murmur2(keyBytes)) % numPartitions;}