程序喵
Guava hashing 散列
提供比 Object.hashCode() 更复杂的散列实现，并提供布鲁姆过滤器的实现。
一、概述
Java内建的散列码[hash code]概念被限制为32位，并且没有分离散列算法和它们所作用的数据，因此很难用备选算法进行替换。此外，使用Java内建方法实现的散列码通常是劣质的，部分是因为它们最终都依赖于JDK类中已有的劣质散列码。
Object.hashCode 往往很快，但是在预防碰撞上却很弱，也没有对分散性的预期。这使得它们很适合在散列表中运用，因为额外碰撞只会带来轻微的性能损失，同时差劲的分散性也可以容易地通过再散列来纠正（Java中所有合理的散列表都用了再散列方法）。然而，在简单散列表以外的散列运用中，Object.hashCode 几乎总是达不到要求，因此，有了 com.google.common.hash 包。
二、散列包的组成
在这个包的Java doc中，我们可以看到很多不同的类，但是文档中没有明显地表明它们是怎样一起配合工作的。
在介绍散列包中的类之前，让我们先来看下面这段代码范例：
HashFunction hf = Hashing.md5(); HashCode hc = hf.newHasher() .putLong(id) .putString(name, Charsets.UTF_8) .putObject(person, personFunnel) .hash();
1、HashFunction
HashFunction 是一个单纯的（引用透明的）、无状态的方法，它把任意的数据块映射到固定数目的位指，并且保证相同的输入一定产生相同的输出，不同的输入尽可能产生不同的输出。
2、Hasher
HashFunction 的实例可以提供有状态的 Hasher，Hasher提供了流畅的语法把数据添加到散列运算，然后获取散列值。Hasher 可以接受所有原生类型、字节数组、字节数组的片段、字符序列、特定字符集的字符序列等等，或者任何给定了 Funnel 实现的对象。
Hasher 实现了 PrimitiveSink 接口，这个接口为接受原生类型流的对象定义了 fluent 风格的API。
3、Funnel
Funnel 描述了如何把一个具体的对象类型分解为原生字段值，从而写入 PrimitiveSink。
比如，如果我们有这样一个类：
class Person {
final int id;
final String firstName;
final String lastName;
final int birthYear;
}它对应的 Funnel 实现可能是：
Funnel<Person> personFunnel = new Funnel<Person>() {
@Override
public void funnel(Person person, PrimitiveSink into) {
into
.putInt(person.id)
.putString(person.firstName, Charsets.UTF_8)
.putString(person.lastName, Charsets.UTF_8)
.putInt(person.birthYear);
}
}注：putString("abc", Charsets.UTF_8).putString("def", Charsets.UTF_8) 完全等同于 putString("ab", Charsets.UTF_8).putString("cdef", Charsets.UTF_8)，因为它们提供了相同的字节序列。这可能带来预料之外的散列冲突。增加某种形式的分隔符有助于消除散列冲突。
4、HashCode
一旦 Hasher 被赋予了所有输入，就可以通过 hash() 方法获取 HashCode 实例（多次调用 hash() 方法的结果是不确定的）。
HashCode 可以通过 asInt()、asLong()、asBytes() 方法来做相等性检测，此外，writeBytesTo(array, offset, maxLength) 把散列值的前 maxLength 字节写入字节数组。
三、布鲁姆过滤器[BloomFilter]
布鲁姆过滤器是哈希运算的一项优雅运用，它可以简单地基于 Object.hashCode() 实现。简而言之，布鲁姆过滤器是一种概率数据结构，它允许你检测某个对象是一定不在过滤器中，还是可能已经添加到过滤器了。布鲁姆过滤器的维基页面 对此作了全面的介绍，同时我们推荐github中的一个教程。
Guava散列包有一个内建的布鲁姆过滤器实现，你只要提供 Funnel 就可以使用它。你可以使用 create(Funnel funnel, int expectedInsertions, double falsePositiveProbability) 方法获取 BloomFilter<T>，缺省误检率为3%。BloomFilter<T> 提供了 boolean mightContain(T) 和 void put(T)，它们的含义都不言自明了。
BloomFilter<Person> friends = BloomFilter.create(personFunnel, 500, 0.01);
for(Person friend : friendsList) {
friends.put(friend);
}
// 很久以后
if (friends.mightContain(dude)) {
//dude不是朋友还运行到这里的概率为1%
//在这儿，我们可以在做进一步精确检查的同时触发一些异步加载
}四、Hashing类
Hashing 类提供了若干散列函数，以及运算 HashCode 对象的工具方法。
1、已提供的散列函数
md5()
murmur3_128()
murmur3_32()
sha1()
sha256()
sha512()
goodFastHash(int bits)
2、HashCode运算
| 方法 | 描述 |
|---|---|
HashCode combineOrdered(Iterable<HashCode>) | 以有序方式联接散列码，如果两个散列集合用该方法联接出的散列码相同，那么散列集合的元素可能是顺序相等的 |
HashCode combineUnordered(Iterable<HashCode>) | 以无序方式联接散列码，如果两个散列集合用该方法联接出的散列码相同，那么散列集合的元素可能在某种排序下是相等的 |
int consistentHash(HashCode, int buckets) | 为给定的”桶”大小返回一致性哈希值。当”桶”增长时，该方法保证最小程度的一致性哈希值变化。详见一致性哈希。 |
3、测试类
package com.example.guava.hash;
import com.google.common.base.Charsets;
import com.google.common.hash.*;
import org.junit.Test;
public class HashingTest {
@Test
public void test() {
String input = "hello, world";
// 计算MD5
System.out.println(Hashing.md5().hashBytes(input.getBytes()).toString());
System.out.println(Hashing.md5().hashUnencodedChars(input).toString());
System.out.println(Hashing.farmHashFingerprint64().hashBytes(input.getBytes()));
System.out.println(Hashing.farmHashFingerprint64().hashUnencodedChars(input).toString());
// 计算sha256
System.out.println(Hashing.sha256().hashBytes(input.getBytes()).toString());
System.out.println(Hashing.sha256().hashUnencodedChars(input).toString());
// 计算sha512
System.out.println(Hashing.sha512().hashBytes(input.getBytes()).toString());
System.out.println(Hashing.sha512().hashUnencodedChars(input).toString());
// 计算crc32
System.out.println(Hashing.crc32().hashBytes(input.getBytes()).toString());
System.out.println(Hashing.crc32().hashUnencodedChars(input).toString());
// 计算adler32
System.out.println(Hashing.adler32().hashBytes(input.getBytes()).toString());
System.out.println(Hashing.adler32().hashUnencodedChars(input).toString());
// 计算crc32c
System.out.println(Hashing.crc32c().hashBytes(input.getBytes()).toString());
System.out.println(Hashing.crc32c().hashUnencodedChars(input).toString());
// 计算murmur3_32
System.out.println(Hashing.murmur3_32().hashBytes(input.getBytes()).toString());
System.out.println(Hashing.murmur3_32().hashUnencodedChars(input).toString());
// 计算murmur3_128
System.out.println(Hashing.murmur3_128().hashBytes(input.getBytes()).toString());
System.out.println(Hashing.murmur3_128().hashUnencodedChars(input).toString());
// 计算sha384
System.out.println(Hashing.sha384().hashBytes(input.getBytes()).toString());
System.out.println(Hashing.sha384().hashUnencodedChars(input).toString());
// 计算sipHash24
System.out.println(Hashing.sipHash24().hashBytes(input.getBytes()).toString());
System.out.println(Hashing.sipHash24().hashUnencodedChars(input).toString());
}
@Test
public void test2() {
// HashFunction function_0 = Hashing.md5();
// HashFunction function_1 = Hashing.md5();
HashFunction function_0 = Hashing.murmur3_128();
HashFunction function_1 = Hashing.murmur3_128();
Person person = new Person();
person.setAge(27);
person.setName("hahahah");
person.setAddress("北京三里屯");
person.setPhoneNumber(16666666666L);
person.setMale(Male.man);
HashCode code_0 = function_0.newHasher()
.putInt(person.getAge())
.putString(person.getName(), Charsets.UTF_8)
.putString(person.getAddress(), Charsets.UTF_8)
.putLong(person.getPhoneNumber())
.putObject(person.getMale(), new Funnel<Male>() {
@Override
public void funnel(Male from, PrimitiveSink into) {
into.putString(from.name(), Charsets.UTF_8);
}
}).hash();
HashCode code_1 = function_1.newHasher()
.putInt(person.getAge())
.putString(person.getName(), Charsets.UTF_8)
.putString(person.getAddress(), Charsets.UTF_8)
.putLong(person.getPhoneNumber())
.putObject(person.getMale(), new Funnel<Male>() {
@Override
public void funnel(Male from, PrimitiveSink into) {
into.putString(from.name(), Charsets.UTF_8);
}
}).hash();
System.out.println(code_0.asLong());
System.out.println(code_1.asLong());
System.out.println(code_0.equals(code_1));
}
}Person.java
package com.example.guava.hash;
public class Person {
private int age;
private String name;
private String address;
private long phoneNumber;
private Male male;
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getAddress() {
return address;
}
public void setAddress(String address) {
this.address = address;
}
public long getPhoneNumber() {
return phoneNumber;
}
public void setPhoneNumber(long phoneNumber) {
this.phoneNumber = phoneNumber;
}
public Male getMale() {
return male;
}
public void setMale(Male male) {
this.male = male;
}
}Male.java
package com.example.guava.hash;
public enum Male {
man, woman;
}五、相关文章
未经允许请勿转载：程序喵 » Google Guava 快速入门 —— hashing 散列