如何以与List.hashCode()相同的方式计算流的哈希码

Question

我刚刚意识到使用Stream.reduce(...)实现以下算法来计算流的哈希码是不可能的.问题是哈希码的初始种子1不是累加器的标识.

List.hashCode()的算法 :

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

您可能会想到以下内容是正确的,但事实并非如此,尽管如果流处理没有拆分它会起作用.

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);

看来,这样做的唯一明智的方法是得到Iterator的Stream和做正常的顺序处理或将其收集到List第一.

Answer 1

虽然乍一看,哈希码算法由于其非关联性似乎是不可并行化的,但如果我们转换函数,它是可能的:

((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?

或任意List大小n:

1 * 31? + e? * 31??¹ + e? * 31??² + e? * 31??³ +  …  + e??? * 31² + e??? * 31¹ + e??? * 31?

第一个1是原始算法的初始值,并且e?是索引处的列表元素的哈希码x.虽然求和现在是独立于评估顺序的,但显然存在对元素位置的依赖性,我们可以通过首先在索引上流式传输来解决这个问题,这对于随机访问列表和数组是有效的,或者通常使用跟踪的收集器来解决遇到的对象数量.收集器可以求助于重复乘法进行累加,并且必须求助于幂函数才能合并结果:

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