一致性hash算法的实现,hash算法和hash一致性
一、哈希函数1.1定义哈希函数(英文：Hash function)，也称为哈希算法和哈希函数，是一种从任何种类的数据中创建小型数字“指纹”的方法。哈希函数将一条消息或数据压缩成摘要，使得数据量变小，数据格式固定。该函数对数据进行加扰和混合，并重新创建一个称为哈希值(哈希代码)的指纹。哈希值通常由一串短的随机字母和数字表示。一个好的散列函数在输入字段中很少出现散列冲突。
1.2特性加密：加密存储在数据库中的密码字符串。因为哈希算法计算出来的哈希值是不可逆的(无法计算回原来的值)，所以可以有效的保护密码。
压缩：通过哈希算法将任意长度的输入转换成固定长度的输出。
应用：数据保护，确保真实信息的传输，哈希表，纠错，语音识别，信息安全。
1.3常见的哈希算法MD系列(MD5)、SHA系列(SHA-1)、CRC，甚至JDK hashCode()也是哈希算法之一。他们可以分为三代：
第一代：SHA-1(1993年)，MD5(1992年)，CRC(1975年)，Lookup3(2006年)
第二代：MurmurHash(2008)
第三代：CityHash，SpookyHash(2011)
它可以分为加密型和非加密型：
加密类型：MD系列(MD5)，SHA系列(SHA-1)
未加密类型：CRC、MurmurHash
这里记录一下murHash，二代几乎称霸江湖。
二。murmurhashMurmurHash算法：高计算性能，低碰撞率。它是由奥斯汀艾波在2008年创立的，已经被应用于Hadoop、libstdc、nginx和libmemcached等开源系统。艾波于2011年被谷歌聘用，随后谷歌推出了其变体CityHash算法。官方只提供了C语言的实现版本。
MurmurHash是一个不加密的哈希函数，适用于一般的哈希检索操作。与其他流行的哈希函数相比，murHash的随机分布特性对于规律性强的密钥更好。
2.1特点1。很快。
Murhash 3比MD5快。
2.低碰撞。
128位版本的murhash 3有一个128位的哈希值，就像MD5一样。18位哈希值，在只有几千万数据的情况下，基本不用担心碰撞。
3.高度混乱。
哈希值是“偶数”，如果用于哈希表、布隆过滤器等。元素会均匀分布。2.2 MD5生成的哈希值为128位。这里的哈希值指的是二进制值，而不是十六进制或base64格式的人类可读值。通常所说的32位MD5是指由32个字符组成的十六进制格式的MD5。MurMurHash算法家族最新成员是MurMurHash3，支持32位和128位，推荐128位MurMurHash3。是原作者被谷歌挖了出来，基于Murmur2的缺陷进行了改进。
32位，在某些场景下，比如哈希对象的长度小于128位，或者存储空间较小，或者需要将字符串转换成整数。这个特性会有所帮助。当然，32位哈希之间发生冲突的可能性要比128位哈希高得多。当数据量达到10万时，发生碰撞的概率很大。
在网上贴一个简单的MurHash2，MurHash3，MD5的基准测试：
https://github . com/space wander/Lua-resty-murmurhash 3/blob/master/readme . MD # when-should-I-use-it
这里的结论：MurMurHash3 128位版本比MD5快十倍。有趣的是，MurMurHash3生成32位Hash比生成128位hash需要更长的时间。原因是MurHash3_128是针对现代x64平台cpu优化的。
Mur是一个很好的通用哈希函数系列，适合不加密使用。MurmurHash提供了以下好处：
简单(根据生成的汇编指令数)。
好的分布(几乎所有的关键组和桶大小都通过了卡方检验。
良好的雪崩行为(最大偏差0.5%)。
抗碰撞性好(通过Bob Jenkin的frog.c酷刑测试。对于4字节的密钥，没有碰撞，没有小(1到7位)的差别)。
在Intel/AMD硬件上的出色性能，哈希质量和CPU消耗之间的良好折衷。
您当然可以使用它来散列UUID(就像任何其他高级散列函数一样：CityHash，Jenkins，Paul Hsieh等等)。现在，Redis位集限制为4 GB位(512兆字节).因此，您需要将128位数据(UUID)减少到32位（散列值)。无论散列函数的质量如何，都会发生碰撞。
使用像低语这样的工程散列函数可以最大限度地提高分布质量，并最大限度地减少碰撞次数，但它不提供任何其他保证。
2.3 应用
广泛应用于各开源产品，Java界中Redis，Memcached，Cassandra，Hadoop，HBase，Lucene，spark，nginx，常见的大数据库底层，都使用了这个算法作为底层的存储算法。
在爪哇的实现，番石榴的散列法类里有，上面提到的卡桑德拉杰迪斯里都有跑龙套类。
但存在的问题是由于爪哇的数据类型长的与C语言中无符号长整型uint64_t有区别，导致爪哇输出版本存在负数，针对这个问题进行了修改；另外需要注意的是中文不同编码(UTF-8或GBK)会导致输出结果的不同，使用中需要统一编码。
三、Java编码实现
导入Java。nio。字节缓冲区；
导入Java。nio。字节顺序；
/**
@作者：黄艺博
@日期：2022/7/18 17:42
@描述：MurMurHash一致性混杂的一种算法高效低碰撞率
*/
公共类MurHashUtil {
/**
* MurMurHash算法，性能高，碰撞率低
* @param密钥字节[]
* @返回长的
公共静态长哈希(byte[] key) {
字节缓冲区。wrap(键)；
int seed=0x1234ABCD
字节顺序字节顺序=buf。order()；
buf.order(ByteOrder .LITTLE _ ENDIAN)；
长m=0 xc6a 4a 7935 bd1e 995 l；
int r=47
长h=种子^(buf。剩余()* m)；
长k；
while (buf.remaining()=8) {
k=buf。getlong()；
k *=m；
^=k
k *=m；
^=k；
h *=m；
if (buf.remaining() 0) {
字节缓冲结束=字节缓冲。分配(8).订单（
字节序.LITTLE _ ENDIAN)；
//对于大端版本，首先执行以下操作：
//完成。位置(8个缓冲器。剩余())；
finish.put(buf).rewind()；
^=完成。getlong()；
h *=m；
^=h
h *=m；
^=h
buf。顺序(字节顺序)；
返回h；
* 计算混杂值
* @param密钥字符串
* @返回长的
公共静态长哈希（字符串密钥){
返回哈希(键。getbytes())；
*长转换成无符号长整型（三)中数据类型)
* Java的数据类型长的与C语言中无符号长整型uint64_t有区别，导致爪哇输出版本存在负数
* @param值
* @返回
public static Long readUnsignedLong(Long value){
如果（值=0){
返回值；
返回值0x7fffffffffffffffL
* 返回无符号杂音散列值
* @param key
* @返回
公共静态长哈希签名（字符串密钥){
返回readUnsignedLong(hash(key))；
* 返回无符号杂音散列值
* @param key
* @返回
public static Long hashUnsigned(byte[]key){
返回readUnsignedLong(hash(key))；
}
}
* 测试
公共静态void main(String[] args) {
list String list=new ArrayList()；
list.add(重庆
list.add(长沙
list.add(广州
list.add(深圳
列表。地址(001 C4 becd 89 f 49 f 7 B1 c 52 Fe 4 fcd 54397
列表。添加(002 b 320 c0e 0347 A8 bcea 7663192d 8303
列表。地址0035420515 a 24d 9d 875 E6 c 4399 bec 8 e 3
列表。地址(00701 f4c 12364 bedb 626 DD 136 CBC 998 b
列表。地址(008d 028903 da 483 fbee8d 721 b2e 73934
列表。地址(00b 9 DC E4 EC 2747 c 0 AEA 6 EB 0494 e 38717)
对于(字符串城市：列表){
长哈希=哈希签名(城市);
系统。出去。println(哈希)；
System.out.println(哈希% 10);
}
}
## 四番石榴碎类
爪哇版：谷歌番石榴包中提供了使用工具类
* 引入谷歌番石榴依赖
属国
groupId com。谷歌。番石榴/groupId
番石榴/artifactId
版本31.1-JRE/版本
/依赖关系
` ` java
导入com。谷歌。常见。哈希。哈希函数；
导入com。谷歌。常见。哈希。哈希；
导入Java。nio。字符集。标准字符集；
* @作者：黄艺博
* @日期：2022/7/18 17:34
* @描述：MurMurHash一致性混杂的一种算法高效低碰撞率
公共类MurHashUtils {
* MurMurHash算法，性能高，碰撞率低
* @param字符串
* @返回长的
公共静态长哈希（字符串str) {
哈希函数哈希函数=哈希。mur mur 3 _ 128()；
返回hashFunction.hashString(str，StandardCharsets .UTF_8).asLong()；
*长转换成无符号长整型（三)中数据类型)
* Java的数据类型长的与C语言中无符号长整型uint64_t有区别，导致爪哇输出版本存在负数
* @param值长
* @返回长的
public static Long readUnsignedLong(Long value){
如果（值=0){
返回值；
返回值长整型最大值
* 返回无符号杂音散列值
* @param key
* @返回
公共静态长哈希签名（字符串密钥){
返回readUnsignedLong(hash(key))；
}
列表。add( 001 C4 becd 89 f 49 f 7 B1 c 52 Fe 4 fcd 54397 )；
列表。add( 002 b 320 c0e 0347 A8 bcea 7663192d 8303 )；
列表。add( 0035420515 a 24d 9d 875 E6 c 4399 bec 8 e 3 )；
列表。add( 00701 f4c 12364 bedb 626 DD 136 CBC 998 b )；
列表。add( 008d 028903 da 483 fbee8d 721 b2e 73934 )；
列表。add( 00 b 9 DC E4 EC 2747 c 0 AEA 6 EB 0494 e 38717 )；
对于(字符串城市：列表){
长哈希=哈希签名(城市);
系统。出去。println(哈希)；
System.out.println(哈希% 10);
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。