MurmurHash 算法

什么是 MurmurHash 算法？

MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。 由 Austin Appleby 在 2008 年发明， 并出现了多个变种，都已经发布到了公有领域（public domain）。与其它流行的哈希函数相比，对于规律性较强的 key，MurmurHash 的随机分布特征表现更良好。

MurmurHash 可以将一个字符串 Hash 出一个碰撞率极低的 long 型数值，且效率很高。

Redis 在实现字典时用到了两种不同的哈希算法，MurmurHash 便是其中一种（另一种是 djb）。在 Redis 中应用十分广泛（Redis 使用的是 MurmurHash2；当字典被用作数据库的底层实现，或者哈希键的底层实现时，使用 MurmurHash2 算法来计算键的哈希值），包括数据库、集群、哈希键、阻塞操作等功能都用到了这个算法。发明算法的作者被邀到 google 工作，该算法最新版本是 MurmurHash3，基于MurmurHash2 改进了一些小瑕疵，使得速度更快，实现了32位（低延时）、128 位 HashKey，尤其对大块的数据，具有较高的平衡性与低碰撞率。

公共广告位-其他

MurmurHash2

该类实现 MurmurHash2 32 位和 64 位哈希函数。

MurmurHash 是一种非加密哈希函数，适用于基于常规哈希的常规查找。该名称来自其内部循环中使用的两个基本运算，即乘法（MU）和旋转（R）。 与加密散列函数不同，它没有专门设计为很难被对手逆转，使其不适合加密目的。

实例：使用 MurmurHash2 类计算指定字符串 32 位和 64 位的 MurMurHash2 算法哈希值，如下：

import org.apache.commons.codec.digest.MurmurHash2;

public class MurmurHash2Demo {

    public static void main(String[] args) {
        String val = "aaaaaa";
        System.out.println(MurmurHash2.hash32(val));
        System.out.println(MurmurHash2.hash64(val));
    }

}

输出结果：

25357950
-3843825703839131154

MurmurHash3

MurmurHash3 32位和128位哈希函数的实现。

MurmurHash 是一种非加密哈希函数，适用于基于常规哈希的常规查找。该名称来自其内部循环中使用的两个基本运算，即乘法（MU）和旋转（R）。与加密散列函数不同，它没有专门设计为很难被对手逆转，使其不适合加密目的。

它包含 32 位哈希函数 MurmurHash3_x86_32 和 128 位哈希函数 MurmurHash3_x64_128 的 Java 端口，这些端口来自于 Austin Applyby's 的 SMHasher 中的原始 C++ 代码。

来自 Apache Hive 的原始改编版。该改编包含一个 hash64 方法，该方法不属于原始 MurmurHash3 的代码。不建议使用这些方法，它们将在将来的版本中删除。要获得 64 位哈希，请使用 hash128x64 方法，并将输入数据转换为字节。

方法说明

• static long[] hash128(byte[] data)

使用默认种子从字节数组生成128位哈希。这是一个助手方法，它将产生与以下相同的结果：

int offset = 0;
int seed = 104729;
int hash = MurmurHash3.hash128(data, offset, data.length, seed);

注意：在 hash128(byte[], int, int, int) 中的符号扩展错误不会影响此结果，因为默认种子为正。

• static long[] hash128x64(byte[] data)

从种子为零的字节数组中生成128位哈希。这是一个助手方法，它将产生与以下相同的结果：

int offset = 0;
int seed = 0;
int hash = MurmurHash3.hash128x64(data, offset, data.length, seed);

• static long[] hash128x64(byte[] data, int offset, int length, int seed)

从具有给定偏移量、长度和种子的字节数组中生成128位哈希。这是一个 128 位哈希函数 MurmurHash3x64_128 的实现，该函数来自于 Austin Applyby's 在 SMHasher 中的原始 MurmurHash3 c++ 代码。参数说明：

• data - 输入字节数组

• offset - 指定从参数 data 字节数组中开始计算哈希值的偏移量

• length - 指定从参数 data 字节数组中，从 offset 开始计算 length 字节的哈希值

• seed - 初始种子值

实例：验证 hash128x64() 方法的参数含义，如下：

import org.apache.commons.codec.digest.MurmurHash3;
import java.util.Arrays;

public class MurmurHash3Demo2 {

    public static void main(String[] args) {
        // 通过 hash128x64() 方法的参数，限制仅仅生成字符串 “aaaaaa” 字符串的哈希值
        String val = "BaaaaaaB";
        long[] result = MurmurHash3.hash128x64(
                val.getBytes(), 1, val.length() - 2, 0);
        System.out.println(Arrays.toString(result));

        // 生成 “aaaaaa” 字符串的哈希值
        result = MurmurHash3.hash128x64("aaaaaa".getBytes());
        System.out.println(Arrays.toString(result));
    }

}

输出结果：

[-6933802564131127315, -6305973827972272179]
[-6933802564131127315, -6305973827972272179]

• static int hash32(long data)

从具有缺省种子值的 long 生成 32 位散列。这是一个助手方法，它将产生与以下相同的结果：

int offset = 0;
int seed = 104729;
int hash = MurmurHash3.hash32x86(
    ByteBuffer.allocate(8).putLong(data).array(), offset, 8, seed);

• static int hash32(long data, int seed)

使用给定的种子从Long生成32位散列。这是一个助手方法，它将产生与以下相同的结果：

int offset = 0;
int hash = MurmurHash3.hash32x86(
    ByteBuffer.allocate(8).putLong(data).array(), offset, 8, seed);

• static int hash32(long data1, long data2)

从两个具有缺省种子值的Long生成32位哈希。这是一个助手方法，它将产生与以下相同的结果：

int offset = 0;
int seed = 104729;
int hash = MurmurHash3.hash32x86(
    ByteBuffer.allocate(16).putLong(data1).putLong(data2).array(), offset, 16, seed);

• static int hash32(long data1, long data2, int seed)

使用给定的种子从两个Long生成32位哈希。这是一个助手方法，它将产生与以下相同的结果：

int offset = 0;
int hash = MurmurHash3.hash32x86(
    ByteBuffer.allocate(16).putLong(data1).putLong(data2).array(), offset, 16, seed);

实例：使用 MurmurHash3 类计算指定字符串 32 位和 64 位的 MurMurHash3 算法哈希值，如下：

import org.apache.commons.codec.digest.MurmurHash3;
import java.util.Arrays;

public class MurmurHash3Demo {

    public static void main(String[] args) {
        String val = "aaaaaa";
        System.out.println(MurmurHash3.hash32(1L));
        System.out.println(MurmurHash3.hash32x86(val.getBytes()));
        System.out.println(Arrays.toString(MurmurHash3.hash128(val.getBytes())));
    }

}

输出结果：

-913662660
1736445713
[8295716659207101544, -3630716032002781079]