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

Question

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.

The algorithm for 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);

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.

Answer 1

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

to

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

which basically is

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

or for an arbitrary List of size n:

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

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,h)    -> { a[0]=a[0]*31+h; 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 2

As a first approach I would use the collect-to-a-list solution as long as you don't have performance concerns. That way you avoid reimplementing the wheel and if one day the hash algorithm changes you benefit from that and you are also safe if the stream is parallelized (even if I'm not sure that's a real concern).

The way I would implement it can vary depending on how and when you need to compare your different datastructures (let's call it Foo).

If you do it manually and sparsly a simple static function may be enough:

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

And use it like this

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

However, if instances of Foo are themselves stored in Collection and you need both hashCode() and equals() (from Object) to be implemented, I would wrap it inside a 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;
    }
}

I'm fully aware that this solution isn't optimized (performance-wise) if multiple calls to hashCode() and equals() are made but I tend not to optimize except if it becomes a concern.

Answer 3

Holger wrote the right solution, if you want a simple way of doing it there are two additional possibilities:

1. collect to List and call hashCode()

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

2. use 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());
}

Just as a reminder the algorithm that List.hashCode() uses:

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

Answer 4

The easiest and shortest way I found was to implement a Collector using Collectors.reducing:

/**
 * 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, "stackoverflow.com");
    int expected = list.hashCode();
    int actual = list.stream().collect(StreamUtils.toHashCode());
    assertEquals(expected, actual);
}

Answer 5

If parallel processing is not a hard requirement, the answer is very simple. You don't need to do anything special to ensure correct ordering for a List, or any other type that has an ORDERED Spliterator such as LinkedHashSet.

From the JavaDoc for Spliterator.ORDERED:

API Note:
Encounter order is guaranteed to be ascending index order for any List. But no order is guaranteed for hash-based collections such as HashSet. Clients of a Spliterator that reports ORDERED are expected to preserve ordering constraints in non-commutative parallel computations.

Since the encounter order is already guaranteed, all you need to do is ensure your Stream is sequential. This requires no effort in most cases, since Collection.stream() returns a sequential Stream. Thus, this code is already correct:

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