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

Question

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

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

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

Answer 1

作为第一种方法，只要您不担心性能问题，我就会使用“收集到列表”解决方案。这样你就可以避免重新实现轮子和 if 有一天哈希算法会改变你从中受益并且如果流是并行化的你也是安全的（即使我不确定这是真的关注）。

我实现它的方式可能会有所不同，具体取决于您需要比较不同数据结构的方式和时间（我们称之为 Foo）。

如果您手动且少量地执行此操作，一个简单的静态函数可能就足够了：

public static int computeHash(Foo origin, Collection<Function<Foo, ?>> selectors) {
    return selectors.stream()
            .map(f -> f.apply(origin))
            .collect(Collectors.toList())
            .hashCode();
}

然后像这样使用它

if(computeHash(foo1, selectors) == computeHash(foo2, selectors)) { ... }

但是，如果 Foo 的实例本身存储在 Collection 中并且您需要同时实现 hashCode() 和 equals()（来自 Object），我会把它包在 FooEqualable:

public final class FooEqualable {
    private final Foo origin;
    private final Collection<Function<Foo, ?>> selectors;

    public FooEqualable(Foo origin, Collection<Function<Foo, ?>> selectors) {
        this.origin = origin;
        this.selectors = selectors;
    }

    @Override
    public int hashCode() {
        return selectors.stream()
                .map(f -> f.apply(origin))
                .collect(Collectors.toList())
                .hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof FooEqualable) {
            FooEqualable that = (FooEqualable) obj;

            Object[] a1 = selectors.stream().map(f -> f.apply(this.origin)).toArray();
            Object[] a2 = selectors.stream().map(f -> f.apply(that.origin)).toArray();

            return Arrays.equals(a1, a2);
        }
        return false;
    }
}

我完全知道，如果多次调用 hashCode() 和 equals()，此解决方案未优化（性能方面），但我倾向于不优化，除非它成为关注。

Answer 2

Holger wrote the right ，如果您想要一种简单的方法，还有两种可能性：

1。收集到 `List` 并致电 `hashCode()`

Stream<? extends Object> stream;
int hashCode = stream.collect(toList()).hashCode();

2。使用 `Stream.iterator()`

Stream<? extends Object> stream;
Iterator<? extends Object> iter = stream.iterator();
int hashCode = 1;
while(iter.hasNext()) {
  hashCode = 31 *hashCode + Objects.hashCode(iter.next());
}

提醒一下List.hashCode()使用的算法：

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

Answer 3

虽然乍一看，哈希码算法似乎由于其非关联性而无法并行化，但如果我们转换函数，则有可能：

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

Answer 4

我发现的最简单和最短的方法是使用 Collectors.reducing:

实现 Collector

/**
 * Creates a new Collector that collects the hash code of the elements.
 * @param <T> the type of the input elements
 * @return the hash code
 * @see Arrays#hashCode(java.lang.Object[])
 * @see AbstractList#hashCode()
 */
public static <T> Collector<T, ?, Integer> toHashCode() {
    return Collectors.reducing(1, Objects::hashCode, (i, j) -> 31 *  i + j);
}

@Test
public void testHashCode() {
    List<?> list = Arrays.asList(Math.PI, 42, "whosebug.com");
    int expected = list.hashCode();
    int actual = list.stream().collect(StreamUtils.toHashCode());
    assertEquals(expected, actual);
}

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

How to compute the hash code for a stream in the same way as List.hashCode()

java

hash

hashcode

java-stream

1。收集到 `List` 并致电 `hashCode()`

2。使用 `Stream.iterator()`

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

How to compute the hash code for a stream in the same way as List.hashCode()

java

hash

hashcode

java-stream

1。收集到 List 并致电 hashCode()

2。使用 Stream.iterator()

1。收集到 `List` 并致电 `hashCode()`

2。使用 `Stream.iterator()`