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 * 313 + b * 312 + c * 311 + d * 31?
or for an arbitrary List
of size n
:
1 * 31? + e? * 31??1 + e? * 31??2 + e? * 31??3 + … + e??? * 312 + e??? * 311 + 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,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();