美文网首页
MurmurHash一致性Hash算法(JAVA版)

MurmurHash一致性Hash算法(JAVA版)

作者: 小波同学 | 来源:发表于2022-07-18 18:38 被阅读0次

一、哈希函数

1.1 定义

散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。

1.2 特点

加密：加密存在数据库中的密码（password）字符串，由于散列算法所计算出来的散列值（Hash Value）具有不可逆（无法逆向演算回原本的数值）的性质，因此可有效的保护密码。

压缩：把任意长度的输入通过散列算法变换成固定长度的输出。

应用：保护资料、确保传递真实的信息、散列表、错误校正、语音识别、信息安全。

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

这里记录一下在第二代中几乎一统江湖的MurmurHash。

二、murmurhash

MurmurHash算法：高运算性能，低碰撞率，由Austin Appleby创建于2008年，现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。2011年Appleby被Google雇佣，随后Google推出其变种的CityHash算法。官方只提供了C语言的实现版本。

MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。

2.1 特点

  • 1.快。
    MurMurHash3 比 MD5 快。

  • 2.低碰撞。
    MurMurHash3 128 位版本哈希值是 128 位的，跟 MD5 一样。128 位的哈希值，在数据量只有千万级别的情况下，基本不用担心碰撞。

  • 3.高混淆。
    散列值比较“均匀”，如果用于哈希表，布隆过滤器等, 元素就会均匀分布。

2.2 介绍

MD5 生成的哈希值是 128 比特的。这里的哈希值指的是二进制的值，而不是 HEX 或 base64 格式化后的人类可读的值。通常我们提到的 32 位 MD5 是指由 32 个字符组成的，HEX 格式的 MD5。MurMurHash 算法家族的最新一员为MurMurHash3，支持32位和128位，推荐使用128位的MurMurHash3。是原作者被Google挖去之后基于Murmur2的缺陷做了改进。

32位的，在某些场景下，比如哈希的对象长度小于 128 位，或者存储空间要求占用小，或者需要把字符串转换成一个整数，这一特性就能帮上忙。当然，32 位哈希值发生碰撞的可能性就比 128 位的要高得多。当数据量达到十万时，就很有可能发生碰撞。

贴一个网上的简单 MurMurHash2、MurMurHash3、MD5 的 benchmark：
https://github.com/spacewander/lua-resty-murmurhash3/blob/master/README.md#when-should-i-use-it

这里的结论：MurMurHash3 128 位版本的速度是 MD5 的十倍。有趣的是，MurMurHash3 生成 32 位哈希的用时比生成 128 位哈希的用时要长。原因在于MurMurHash3_128 针对现代 x64 平台cpu进行了优化。

Murmur是一个良好的通用散列函数系列，适用于非加密用法。MurmurHash提供以下好处：

  • 简单（根据生成的汇编指令数量）。
  • 良好的分布（几乎所有键组和铲斗尺寸均通过卡方检验。
  • 好 雪崩 行为（最大偏差0.5％）。
  • 良好的碰撞阻力（通过Bob Jenkin的frog.c酷刑测试。对于4字节键没有碰撞，没有小的（1到7位）差异）。
  • 在Intel/AMD硬件上表现出色，散列质量和CPU消耗之间的良好折衷。

您当然可以使用它来散列UUID（就像任何其他高级散列函数一样：CityHash，Jenkins，Paul Hsieh等等）。现在，Redis bitset限制为4 GB位（512 MB）。因此，您需要将128位数据（UUID）减少到32位（散列值）。无论散列函数的质量如何，都会发生碰撞。

使用像Murmur这样的工程散列函数可以最大限度地提高分布质量，并最大限度地减少碰撞次数，但它不提供任何其他保证。

2.3 应用

广泛应用于各开源产品，Java 界中 Redis，Memcached，Cassandra，Hadoop，HBase，Lucene，spark，nginx，常见的大数据库底层，都使用了这个算法作为底层的存储算法。

在Java的实现，Guava的Hashing类里有，上面提到的Jedis，Cassandra里都有Util类。

但存在的问题是由于Java的数据类型long与C语言中无符号长整型uint64_t有区别，导致Java输出版本存在负数，针对这个问题进行了修改；另外需要注意的是中文不同编码（UTF-8或GBK）会导致输出结果的不同，使用中需要统一编码。

三、Java编码实现

  • 实现
import java.nio.ByteBuffer;
import java.nio.ByteOrder;

/**
 * @Author: huangyibo
 * @Date: 2022/7/18 17:42
 * @Description: MurMurHash 一致性Hash的一种算法 高效低碰撞率
 */

public class MurMurHashUtil {

    /**
     * MurMurHash算法, 性能高, 碰撞率低
     * @param key byte[]
     * @return Long
     */
    public static Long hash(byte[] key) {

        ByteBuffer buf = ByteBuffer.wrap(key);
        int seed = 0x1234ABCD;

        ByteOrder byteOrder = buf.order();
        buf.order(ByteOrder.LITTLE_ENDIAN);

        long m = 0xc6a4a7935bd1e995L;
        int r = 47;

        long h = seed ^ (buf.remaining() * m);

        long k;
        while (buf.remaining() >= 8) {
            k = buf.getLong();

            k *= m;
            k ^= k >>> r;
            k *= m;

            h ^= k;
            h *= m;
        }

        if (buf.remaining() > 0) {
            ByteBuffer finish = ByteBuffer.allocate(8).order(
                    ByteOrder.LITTLE_ENDIAN);
            // for big-endian version, do this first:
            // finish.position(8-buf.remaining());
            finish.put(buf).rewind();
            h ^= finish.getLong();
            h *= m;
        }

        h ^= h >>> r;
        h *= m;
        h ^= h >>> r;

        buf.order(byteOrder);
        return h;
    }


    /**
     * 计算hash值
     * @param key String
     * @return Long
     */
    public static Long hash(String key) {
        return hash(key.getBytes());
    }


    /**
     * Long转换成无符号长整型（C中数据类型）
     * Java的数据类型long与C语言中无符号长整型uint64_t有区别，导致Java输出版本存在负数
     * @param value
     * @return
     */
    public static Long readUnsignedLong(long value) {
        if (value >= 0){
            return value;
        }
        return value & 0x7fffffffffffffffL;
    }


    /**
     * 返回无符号murmur hash值
     * @param key
     * @return
     */
    public static Long hashUnsigned(String key) {
        return readUnsignedLong(hash(key));
    }


    /**
     * 返回无符号murmur hash值
     * @param key
     * @return
     */
    public static Long hashUnsigned(byte[] key) {
        return readUnsignedLong(hash(key));
    }

}
  • 测试
public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("CHONGQING");
    list.add("CHANGSHA");
    list.add("GUANGZHOU");
    list.add("SHENZHEN");
    list.add("001c4becd89f49f7b1c52fe4fcd54397");
    list.add("002b320c0e0347a8bcea7663192d8303");
    list.add("0035420515a24d9d875e6c4399bec8e3");
    list.add("00701f4c12364bedb626dd136cbc998b");
    list.add("008d028903da483fbee8d721b2e73934");
    list.add("00b9dce4ec2747c0aea6eb0494e38717");
    for (String city : list) {
        long hash = hashUnsigned(city);
        System.out.println(hash);
        System.out.println(hash % 10);
    }
}

四、Guava Hashing类

Java版：google guava 包中提供了使用工具类

  • 引入google guava 依赖
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
</dependency>
  • 使用
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;

import java.nio.charset.StandardCharsets;

/**
 * @Author: huangyibo
 * @Date: 2022/7/18 17:34
 * @Description: MurMurHash 一致性Hash的一种算法 高效低碰撞率
 */

public class MurMurHashUtils {

    /**
     * MurMurHash算法, 性能高, 碰撞率低
     * @param str String
     * @return Long
     */
    public static Long hash(String str) {
        HashFunction hashFunction = Hashing.murmur3_128();
        return hashFunction.hashString(str, StandardCharsets.UTF_8).asLong();
    }

    /**
     * Long转换成无符号长整型（C中数据类型）
     * Java的数据类型long与C语言中无符号长整型uint64_t有区别，导致Java输出版本存在负数
     * @param value long
     * @return Long
     */
    public static Long readUnsignedLong(long value) {
        if (value >= 0){
            return value;
        }
        return value & Long.MAX_VALUE;
    }

    /**
     * 返回无符号murmur hash值
     * @param key
     * @return
     */
    public static Long hashUnsigned(String key) {
        return readUnsignedLong(hash(key));
    }

}
  • 测试
public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("CHONGQING");
    list.add("CHANGSHA");
    list.add("GUANGZHOU");
    list.add("SHENZHEN");
    list.add("001c4becd89f49f7b1c52fe4fcd54397");
    list.add("002b320c0e0347a8bcea7663192d8303");
    list.add("0035420515a24d9d875e6c4399bec8e3");
    list.add("00701f4c12364bedb626dd136cbc998b");
    list.add("008d028903da483fbee8d721b2e73934");
    list.add("00b9dce4ec2747c0aea6eb0494e38717");
    for (String city : list) {
        Long hash = hashUnsigned(city);
        System.out.println(hash);
        System.out.println(hash % 10);

    }
}

参考：
https://www.iteye.com/blog/sgq0085-2230528

https://blog.csdn.net/yjgithub/article/details/120447399

相关文章

网友评论

      本文标题：MurmurHash一致性Hash算法(JAVA版)

      本文链接：https://www.haomeiwen.com/subject/xtedirtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|MurmurHash一致性Hash算法(JAVA版)|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！