Java 內(nèi)建的散列碼[hash code]概念被限制為 32 位,并且沒有分離散列算法和它們所作用的數(shù)據(jù),因此很難用備選算法進行替換。此外,使用 Java 內(nèi)建方法實現(xiàn)的散列碼通常是劣質(zhì)的,部分是因為它們最終都依賴于 JDK 類中已有的劣質(zhì)散列碼。
Object.hashCode 往往很快,但是在預(yù)防碰撞上卻很弱,也沒有對分散性的預(yù)期。這使得它們很適合在散列表中運用,因為額外碰撞只會帶來輕微的性能損失,同時差勁的分散性也可以容易地通過再散列來糾正(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();
HashFunction
HashFunction 是一個單純的(引用透明的)、無狀態(tài)的方法,它把任意的數(shù)據(jù)塊映射到固定數(shù)目的位指,并且保證相同的輸入一定產(chǎn)生相同的輸出,不同的輸入盡可能產(chǎn)生不同的輸出。
Hasher
HashFunction 的實例可以提供有狀態(tài)的 Hasher,Hasher 提供了流暢的語法把數(shù)據(jù)添加到散列運算,然后獲取散列值。Hasher 可以接受所有原生類型、字節(jié)數(shù)組、字節(jié)數(shù)組的片段、字符序列、特定字符集的字符序列等等,或者任何給定了 Funnel 實現(xiàn)的對象。
Hasher 實現(xiàn)了 PrimitiveSink 接口,這個接口為接受原生類型流的對象定義了 fluent 風格的 API
Funnel
Funnel 描述了如何把一個具體的對象類型分解為原生字段值,從而寫入 PrimitiveSink。比如,如果我們有這樣一個類:
class Person {
final int id;
final String firstName;
final String lastName;
final int birthYear;
}
它對應(yīng)的 Funnel 實現(xiàn)可能是:
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(birthYear);
}
}
注:putString(“abc”, Charsets.UTF_8).putString(“def”, Charsets.UTF_8)完全等同于 putString(“ab”, Charsets.UTF_8).putString(“cdef”, Charsets.UTF_8),因為它們提供了相同的字節(jié)序列。這可能帶來預(yù)料之外的散列沖突。增加某種形式的分隔符有助于消除散列沖突。
HashCode
一旦 Hasher 被賦予了所有輸入,就可以通過 [hash()](http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/hash/Hasher.html#hash())方法獲取 HashCode 實例(多次調(diào)用 hash()方法的結(jié)果是不確定的)。HashCode 可以通過 [asInt()](http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/hash/HashCode.html#asInt())、[asLong()](http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/hash/HashCode.html#asLong())、[asBytes()](http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/hash/HashCode.html#asBytes())方法來做相等性檢測,此外,writeBytesTo(array, offset, maxLength)把散列值的前 maxLength字節(jié)寫入字節(jié)數(shù)組。
布魯姆過濾器是哈希運算的一項優(yōu)雅運用,它可以簡單地基于 Object.hashCode()實現(xiàn)。簡而言之,布魯姆過濾器是一種概率數(shù)據(jù)結(jié)構(gòu),它允許你檢測某個對象是一定不在過濾器中,還是可能已經(jīng)添加到過濾器了。布魯姆過濾器的維基頁面對此作了全面的介紹,同時我們推薦 github 中的一個教程。
Guava 散列包有一個內(nèi)建的布魯姆過濾器實現(xiàn),你只要提供 Funnel 就可以使用它。你可以使用 create(Funnel funnel, int expectedInsertions, double falsePositiveProbability)方法獲取 BloomFilter
BloomFilter<Person> friends = BloomFilter.create(personFunnel, 500, 0.01);
for(Person friend : friendsList) {
friends.put(friend);
}
// 很久以后
if (friends.mightContain(dude)) {
//dude不是朋友還運行到這里的概率為1%
//在這兒,我們可以在做進一步精確檢查的同時觸發(fā)一些異步加載
}
Hashing 類提供了若干散列函數(shù),以及運算 HashCode 對象的工具方法。
md5() | murmur3_128() | murmur3_32() | sha1() |
sha256() | sha512() | goodFastHash(int bits) |
方法 | 描述 |
HashCode combineOrdered( Iterable<HashCode>) | 以有序方式聯(lián)接散列碼,如果兩個散列集合用該方法聯(lián)接出的散列碼相同,那么散列集合的元素可能是順序相等的 |
HashCode combineUnordered( Iterable<HashCode>) | 以無序方式聯(lián)接散列碼,如果兩個散列集合用該方法聯(lián)接出的散列碼相同,那么散列集合的元素可能在某種排序下是相等的 |
int consistentHash( HashCode, int buckets) | 為給定的”桶”大小返回一致性哈希值。當”桶”增長時,該方法保證最小程度的一致性哈希值變化。詳見一致性哈希。 |