Improve partitioning hash function

[StephanEwen]

Right now, the partitioner (OutputEmitter) used directly the hash code produced by the partitioning elements. Types like Integer have very weak hash functions, so the hash partitioning is very susceptible to skew there.

[vasia]

I'll start working on this.
The idea so far is to use something similar to MurmurHash. I also found that there exists a Guava implementation for the MurmurHash.
Let me know if you have other ideas/suggestions.

[StephanEwen]

The hash implementations are all expecting a byte buffer and hash over the
bytes. Can we use an implementation tailored towards an int (4 bytes) ?

Alternatives could be:

• http://en.wikipedia.org/wiki/Jenkins_hash_function
• http://burtleburtle.net/bob/hash/index.html

We took the HashTable hash function from the Jenkins suite. We need to make
sure that we use a different here.

[vasia]

Murmur loops over 4-byte chunks of the input, so I guess we can use it performing just one loop on the int value. Otherwise, I see you have used the "4-byte integer hash, full avalanche" from the website you gave, for the HashTable. This seems to be the best among the ones described there and then there is the one that uses 7 shifts (doesn't really have a name).

I can try both, but I'm not really sure how to test which is better for what we want. Any hints on that?

[vasia]

Hey,
here's my first take on this.
I did some very basic tests based on the OutputEmitterTest to check the behavior of the hash function.
I'm attaching 3 diagrams, one for integer records, one for strings and one for records with an integer, a string and a double field. Each diagram shows boxplots of the distribution of values to channels. The values are generated as in OutputEmitterTest. I'm using 100000 records and varying the number of channels from 10-100, with a step of 10.
Let me know what you think!