哈希算法与MurmurHash3

MurmurHash 哈希算法

 

MurmurHash：(multiply and rotate) and (multiply and rotate) Hash，乘法和旋转的hash 算法。

MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。目前已经被广泛应用到很多开源的项目当中，如Redis，Memcached，Cassandra，HBase，Lucene等。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。它的名字来源于两个基本操作，乘法（MU）和旋转（R），在它的内部循环中使用。与加密散列函数不同，它不是专门设计为难以被对手逆转，因此不适合用于加密目的。

一、哈希函数

定义

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

特点

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

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

应用

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

常见哈希算法

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年发明，并出现了多个变种，都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。

特点

1.快。

MurMurHash3 比 MD5 快。

2.低碰撞。

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

3.高混淆。

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

应用

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

介绍

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

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

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

简单（根据生成的汇编指令数量）。

良好的分布（几乎所有键组和铲斗尺寸均通过卡方检验。

好 雪崩 行为（最大偏差0.5％）。

良好的碰撞阻力（通过Bob Jenkin的frog.c酷刑测试。对于4字节键没有碰撞，没有小的（1到7位）差异）。

在Intel/AMD硬件上表现出色，散列质量和CPU消耗之间的良好折衷。

您当然可以使用它来散列UUID（就像任何其他高级散列函数一样：CityHash，Jenkins，Paul Hsieh等等）。使用像Murmur这样的工程散列函数可以最大限度地提高分布质量，并最大限度地减少碰撞次数，但它不提供任何其他保证。

三、MurmurHash使用

1.导包

 

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

 

<groupId>com.google.guava</groupId>

<artifactId>guava</artifactId>

<version>30.1.1-jre</version>

2.使用

 

import java.nio.charset.StandardCharsets;

import com.google.common.hash.HashFunction;

import com.google.common.hash.Hashing;

 

public class MurmurHashTest {

 

    public static void main(String[] args) {

        for (int i = 0; i < 100; i++) {

            String hexHashString = getHexHashString("qwerqwerqwer");

            System.out.println(hexHashString);

        }

    }

 

    public static String getHexHashString(String str) {

        HashFunction hashFunction = Hashing.murmur3_128();

        return hashFunction.hashString(str, StandardCharsets.UTF_8).toString();

    }

}

 

代码例子：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>20.0</version>
</dependency>

public class TestMurmurhash3 {
    public static void main(String[] args) {
        String myStr = "ehl-test111";
        String str = Hashing.murmur3_128().newHasher().putString(myStr, StandardCharsets.UTF_8).hash().toString();
        System.out.println("str is:::::"+ str);

        HashFunction function = Hashing.murmur3_32();
        HashCode hascode = function.hashString("hello1", Charset.forName("utf-8"));
        System.out.println(hascode.asInt());
        HashCode hascode2 = function.hashString("hello2", Charset.forName("utf-8"));
        System.out.println(hascode2.asInt());
        HashCode hascode3 = function.hashString("hello3", Charset.forName("utf-8"));
        System.out.println(hascode3.asInt());

        byte[] mm3_le = Hashing.murmur3_128().hashString("abc", Charset.forName("utf-8")).asBytes();
        System.out.println(Hashing.murmur3_128().hashString("abc", Charset.forName("utf-8")).asInt());
        byte[] mm3_be = Bytes.toArray(Lists.reverse(Bytes.asList(mm3_le)));
        System.out.println(new BigInteger(mm3_be).toString());
        System.out.println(Hashing.murmur3_128().newHasher().putString("abc", StandardCharsets.UTF_8).hash().toString());
        System.out.println(Hashing.murmur3_128().newHasher().putString("abc", StandardCharsets.UTF_8).hash().asInt());

        assertEquals("79267961763742113019008347020647561319",new BigInteger(mm3_be).toString());

        HashFunction hashFunction = Hashing.murmur3_128();
        String s2 = hashFunction.hashString(myStr, StandardCharsets.UTF_8).toString();
        System.out.println(s2);


    }


    public static String getHexHashString(String str) {
        HashFunction hashFunction = Hashing.murmur3_128();
        return hashFunction.hashString(str, StandardCharsets.UTF_8).toString();
    }

    public static String getHexMD5String(String str) {
//        return org.springframework.util.DigestUtils.md5DigestAsHex(str.getBytes());
return DigestUtils.md5Hex(str.getBytes());
    }

}

 HIVE UDF函数封装：

package com.xxx.utils.hash;

import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import org.apache.hadoop.hive.ql.exec.UDF;

import java.nio.charset.StandardCharsets;

/**
 * TODO
*
 * @author User
 * @version 1.0
 * @date 2022/4/12 15:38
 */
public class MyHiveUdf extends UDF {

//    重载evaluate方法
//    进入hive客户端，添加jar包：hive> add jar /run/jar/udf_test.jar
//    创建临时函数：hive> CREATE TEMPORARY FUNCTION murmurhash3 AS 'com.ehl.utils.hash.MyHiveUdf';
//    hive> SELECT murmurhash3("gaozz") FROM scores;
//    hive> DROP TEMPORARY FUNCTION murmurhash3;
//    murmurhash3(concat("uid-",uid))   as uidHash,
//    murmurhash3(concat("cre-",credit_id))   as creditCardIdHash

public String evaluate(String inputStr){
        String str = Hashing.murmur3_128().newHasher().putString(inputStr, StandardCharsets.UTF_8).hash().toString();
//        HashFunction hashFunction = Hashing.murmur3_128();
//        String str =  hashFunction.hashString(str, StandardCharsets.UTF_8).toString();
return str;
    }


}

HIVE SQL使用自定义函数：murmurhash3

//    murmurhash3(concat("uid-",uid))   as uidHash,
//    murmurhash3(concat("cre-",credit_id))   as creditCardIdHash