mono/mono — pull request #847 by ranma42 (2013-12-26 17:01:38+00:00)
Title: F#-compatible tuple hashing

As pointed out in https://github.com/fsharp/fsharp/issues/188 , currently the F# compiler makes very strong assumptions about the algorithm used for hashing tuples. These assumptions hold on the .NET runtime, but not on Mono, which can result in incorrect behaviour.

This patchset restores the functionality of the Tuples.cs code generator and replaces the current algorithm (h = h*31 + data) with DJB2-XOR (h=h*33 ^ data), using the same parenthesization as in the F# compiler (somewhat like in a balanced binary tree). The original F# implementation is available here: https://github.com/fsharp/fsharp/blob/fsharp_31/src/fsharp/FSharp.Core/prim-types.fs#L488

Some additional thoughts:
Neither	the old	nor the	new hash algorithm are particularly robust, but they are not supposed to be strong hashes. In fact, DJB2 is known to be quite poor with respect to collisions. In my opinion a better (and still reasonably cheap) choice would have been some variant of MurmurHash, but this would break compatibility with .NET.

For future reference it might be worth pointing out that the new hash
requires an amount of memory (in the current implementation,
variables) which is O(log n) with respect to the size of the tuple,
while the previous one used O(1) space.	Right now this is probably not much of a problem, but if in future tuples were allowed to have very big sizes, it might be inappropriate to have the temporary variables explicitly and it might be a good idea to store them in an array.