小盒子

V1

2023/01/14阅读:11主题:红绯

跟着 Guava 学 java 之 Hashing

Java 内建的 hash code 为 32 位的,但是没有分离散列算法和它们所作用的数据,因此很难用备选算法进行替换。

此外,使用 Java 内建方法实现的散列码通常是劣质的,部分是因为它们最终都依赖于 JDK 类中已有的劣质散列码。

以下为 String 类的 hashCode() 方法

Object.hashCode 往往很快,但是在预防碰撞上却很弱,也没有对分散性的预期。这使得它们很适合在散列表中运用,因为额外碰撞只会带来轻微的性能损失,同时差劲的分散性也可以容易地通过再散列(rehash)来纠正(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 是一个纯粹的无状态函数,它将任意数据块映射到固定数量的位。并且保证相同的输入一定产生相同的输出,不同的输入尽可能产生不同的输出。

HashFunction hf = Hashing.md5();

注意:上面这行代码中是调用了 md5 方法,不过最新的 API 已经废弃了 (Deprecated) 此方法

 @Deprecated
  public static HashFunction md5() {
    return Md5Holder.MD5;
  }

官方建议:

如果必须与需要 MD5 的系统进行互操作,请使用此方法,尽管它已弃用。但是,如果您可以选择哈希函数,请避免使用 MD5,它既不快速也不安全。截至 2017 年 1 月,我们建议: 为了安全起见:sha256 或更高级别的 API。 为了速度:使用 goodFastHash

Hasher

  • HashFunction 的实例可以提供有状态的 Hasher, Hasher 提供了流式语法把数据添加到散列运算,然后获取散列值。
  • Hasher 实现了 PrimitiveSink 接口,这个接口为接受原生类型流的对象定义了 fluent 风格的 API
  • Hasher 可以接受所有原生类型、字节数组、字节数组的片段、字符序列、特定字符集的字符序列等等,或者任何给定了 Funnel 实现的对象。

“或者任何给定了 Funnel 实现的对象” ? 啥意思 ?

其实说的就是下面这行代码的 putObject 部分

HashCode hc = hf.newHasher()
       .putLong(id)
       .putString(name, Charsets.UTF_8)
       .putObject(person, personFunnel)
       .hash();

我们看下源码:

Funnel 又是啥 ?

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(birthYear);
    }
}

putString(“abc”, Charsets.UTF_8).putString(“def”, Charsets.UTF_8) 完全等同于 putString(“ab”, Charsets.UTF_8).putString(“cdef”, Charsets.UTF_8),因为它们提供了相同的字节序列。这可能带来预料之外的散列冲突。增加某种形式的分隔符有助于消除散列冲突。

HashCode

一旦 Hasher 被赋予了所有输入,就可以通过 hash()方法获取 HashCode 实例(多次调用 hash() 方法的结果是不确定的)。

HashCode hc = hf.newHasher()
                .putLong(id)
                .putString(name, Charsets.UTF_8)
                .putObject(person, personFunnel)
                .hash();

HashCode 可以通过asInt()asLong()asBytes() 方法来做相等性检测,此外,writeBytesTo(array,offset,maxLength) 可以把散列值的前 maxLength 字节写入字节数组。

至此,咱们回头再来看看文章最开始的那句话:

Java 内建的 hash code 为 32 位的,但是没有分离散列算法和它们所作用的数据,因此很难用备选算法进行替换。

再看一看 Guava 提供的方法,确实解决了 散列算法所作用的数据

应用

一般用法

对于原始数据类型,直接调用现成的 API 就可以了,比如:

Hashing.sha256().hashBytes(input.getBytes()).toString()

如果是对象类型,稍微麻烦一点点:

Person person = new Person();
        person.setAge(27);
        person.setName("张三");
        person.setAddress("北京");
        person.setPhoneNumber(13666666666L);
        person.setMale(Male.man);

HashCode code = Hashing.sha256().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();        

BloomFilter

布隆过滤器是哈希运算的一项优雅运用,它可以简单地基于 Object.hashCode() 实现。简而言之,布隆过滤器是一种概率数据结构,它允许你检测某个对象是一定不在过滤器中,还是可能已经添加到过滤器了。

对于查询某个元素,只能判定某个元素一定不存在或者有可能存在,并不能判定某个元素一定存在

Guava 散列包有一个内建的布隆过滤器实现,你只要提供 Funnel 就可以使用它。

你可以使用create(Funnel funnel, int expectedInsertions, double falsePositiveProbability)方法获取 BloomFilter ,缺省误检率 [falsePositiveProbability] 为 3%。BloomFilter 提供了 boolean mightContain(T)[ ](http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/hash/BloomFilter.html#create(com.google.common.hash.Funnel, int, double)) 和 void put(T) ,它们的含义都不言自明了。

BloomFilter<Person> friends = BloomFilter.create(personFunnel, 5000.01);
for(Person friend : friendsList) {
    friends.put(friend);
}

// 很久以后
if (friends.mightContain(dude)) {
    //dude 不是朋友还运行到这里的概率为 1%
    //在这儿,我们可以在做进一步精确检查的同时触发一些异步加载
}

其他

hash 算法

guava 主要提供的方法包括:

  • md5()
  • murmur3_128()
  • murmur3_32()
  • sha1()
  • sha256()
  • sha512()
  • goodFastHash(int bits)

其他方法可以参考官方文档

HashCode 操作

Method Description
HashCode combineOrdered(Iterable<HashCode>) 以有序方式联接散列码,如果两个散列集合用该方法联接出的散列码相同,那么散列集合的元素可能是顺序相等的
HashCode combineUnordered(Iterable<HashCode>) 以无序方式联接散列码,如果两个散列集合用该方法联接出的散列码相同,那么散列集合的元素可能在某种排序下是相等的
int consistentHash(HashCode, int buckets) 为给定的”桶”大小返回一致性哈希值。当”桶”增长时,该方法保证最小程度的一致性哈希值变化 (有没有想到 Redis 和一致性哈希算法?)

参考

分类:

后端

标签:

后端

作者介绍

小盒子
V1