跟着 Guava 学 java 之 Hashing

雨点打透心脏的1/2处 2023-10-03 23:41 6阅读 0赞

![format_png][]

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

![format_png 1][]

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

以下为 `String` 类的 `hashCode()` 方法

![format_png 2][]

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();
    复制代码

我们看下源码：

![format_png 3][]

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)` 和 `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%
        //在这儿，我们可以在做进一步精确检查的同时触发一些异步加载
    }
    复制代码

### 其他 ###

#### hash 算法 ####

guava 主要提供的方法包括：

*  `md5()`
 *  `murmur3_128()`
 *  `murmur3_32()`
 *  `sha1()`
 *  `sha256()`
 *  `sha512()`
 *  `goodFastHash(int bits)`

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

#### HashCode 操作 ####

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

[format_png]: https://img-blog.csdnimg.cn/img_convert/adf1846550edc1aaec68cecfbf258762.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/8ff2b901fbb931fede0a4198b3b24472.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/39995385cbfff1a9ab17e955657b7c91.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/e72c2e73db6c624ba80a1900f691fec1.webp?x-oss-process=image/format,png