如何以与 List.hashCode() 相同的方式计算流的哈希码 [英] How to compute the hash code for a stream in the same way as List.hashCode()

问题描述

我刚刚意识到使用 Stream.reduce(...).问题是哈希码的初始种子是 1，它不是累加器的标识.

I just realized that implementing the following algorithm to compute the hash code for a stream is not possible using Stream.reduce(...). The problem is that the initial seed for the hash code is 1 which is not an identity for the accumulator.

List.hashCode的算法():

int hashCode = 1;
for (E e : list)
  hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

您可能会认为以下内容是正确的，但事实并非如此，尽管如果不拆分流处理它会起作用.

You might be tempted to think that the following is correct but it isn't, although it will work if the stream processing is not split up.

List<Object> list = Arrays.asList(1,null, new Object(),4,5,6);
int hashCode = list.stream().map(Objects::hashCode).reduce(1, (a, b) -> 31 * a + b);

似乎唯一明智的做法是获取 Stream 的 Iterator 并进行正常的顺序处理或将其收集到 List 首先.

It seems that the only sensible way of doing it would be to get the Iterator of the Stream and do normal sequential processing or collect it to a List first.

推荐答案

虽然乍一看，哈希码算法由于其非结合性似乎是不可并行化的，但如果我们变换函数，则是可能的:

While, at the first glance, the hash code algorithm seems to be non-parallelizable due to its non-associativity, it is possible, if we transform the function:

((a * 31 + b) * 31 + c ) * 31 + d

到

a * 31 * 31 * 31 + b * 31 * 31 + c * 31 + d

基本上是

a * 31³ + b * 31² + c * 31¹ + d * 31⁰

或对于大小为 n 的任意 List:

or for an arbitrary List of size n:

1 * 31ⁿ + e₀ * 31ⁿ⁻¹ + e₁ * 31ⁿ⁻² + e₂ * 31ⁿ⁻³ +  …  + eₙ₋₃ * 31² + eₙ₋₂ * 31¹ + eₙ₋₁ * 31⁰

第一个 1 是原始算法的初始值，eₓ 是索引 x 处的列表元素的哈希码.虽然加数现在与评估顺序无关，但显然对元素的位置有依赖性，我们可以通过首先对索引进行流式处理来解决这个问题，这适用于随机访问列表和数组，或者一般解决，用一个收集器跟踪遇到的对象的数量.收集器可以借助重复乘法进行累加，而只能借助幂函数来组合结果:

with the first 1 being the initial value of the original algorithm and eₓ being the hash code of the list element at index x. While the summands are evaluation order independent now, there’s obviously a dependency to the element’s position, which we can solve by streaming over the indices in the first place, which works for random access lists and arrays, or solve generally, with a collector which tracks the number of encountered objects. The collector can resort to the repeated multiplications for the accumulation and has to resort to the power function only for combining results:

static <T> Collector<T,?,Integer> hashing() {
    return Collector.of(() -> new int[2],
        (a,o)    -> { a[0]=a[0]*31+Objects.hashCode(o); a[1]++; },
        (a1, a2) -> { a1[0]=a1[0]*iPow(31,a2[1])+a2[0]; a1[1]+=a2[1]; return a1; },
        a -> iPow(31,a[1])+a[0]);
}
// derived from http://stackoverflow.com/questions/101439
private static int iPow(int base, int exp) {
    int result = 1;
    for(; exp>0; exp >>= 1, base *= base)
        if((exp & 1)!=0) result *= base;
    return result;
}

List<Object> list = Arrays.asList(1,null, new Object(),4,5,6);
int expected = list.hashCode();

int hashCode = list.stream().collect(hashing());
if(hashCode != expected)
    throw new AssertionError();

// works in parallel
hashCode = list.parallelStream().collect(hashing());
if(hashCode != expected)
    throw new AssertionError();

// a method avoiding auto-boxing is more complicated:
int[] result=list.parallelStream().mapToInt(Objects::hashCode)
    .collect(() -> new int[2],
    (a,o)    -> { a[0]=a[0]*31+Objects.hashCode(o); a[1]++; },
    (a1, a2) -> { a1[0]=a1[0]*iPow(31,a2[1])+a2[0]; a1[1]+=a2[1]; });
hashCode = iPow(31,result[1])+result[0];

if(hashCode != expected)
    throw new AssertionError();

// random access lists allow a better solution:
hashCode = IntStream.range(0, list.size()).parallel()
    .map(ix -> Objects.hashCode(list.get(ix))*iPow(31, list.size()-ix-1))
    .sum() + iPow(31, list.size());

if(hashCode != expected)
    throw new AssertionError();

这篇关于如何以与 List.hashCode() 相同的方式计算流的哈希码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！