Default behaviour of Hash[expr] and hashing in different versions of Mathematica

Question

In different versions of Mathematica, Wolfram silently changed the behaviour of Hash when the algorithm is not specified explicitly

Hash[1]
(* 6568131406215528669 (Version 10.1) *)

Hash[1]
(* 4371187653775642860 (Version 9.0.1) *)

Hash[1]
(* 1742717557 (Version 8.0.4) *)

This is a serious violation of how a public function/API should be supported in such a large software as Mathematica. Especially, since the documentation of Hash suggests that the behaviour will be consistent:

Hash[expr,...] will always give the same result for the same expression expr.

More importantly, the default hashing algorithms seems to be completely detached from all available settings, as it seems impossible to recreate the default hash when explicitly choosing one.

Hash[1]
(* 6568131406215528669 *)

Hash[1,#]&/@{"Adler32","CRC32","MD2","MD5","SHA","SHA256","SHA384","SHA512"}//Column
(* 
3959688615
3017272578
277753940344783714340401450212752361952
68231128815270908652080701364659390939
846778260378026149058641558857036959755342858310
35440229038221092521327873929090932360118094198559938935455836283354874680335
32975197285603495667013724312557093882636446440150950620624270433328413926233671687205762131877578287401554708845055
12579926171497332473039920596952835386489858401292624452730263741969134739018228297640298179049647746066620814234742520593670116132355345543156774710409041
*)

Does someone know, 1. how to reproduce the default hashing behaviour when explicitly choosing a method and 2. re-create the default hashing behaviour in different versions?

Answer 1

1. how to reproduce the default hashing behaviour when explicitly choosing a method

Hash[1, "Expression"]

(* 6568131406215528669 *)

Hash[1, "Expression"] === Hash[1]

(* True *)

2. re-create the default hashing behaviour in different versions?

Not possible as far as I know. The one-argument Hash implementation may change between versions. The algorithm has been most recently changed to improve the distribution of hash values. For example, this

Length[Union[Map[Hash, Range[10^7]]]]

(* 10000000 *)

is much better with respect to collisions than in version 9 and earlier.

Something else to keep in mind is that there will be two different results for Hash[expr] with the same expression expr in the same version: one for 64-bit and one for 32-bit:

(* evaluated in a 32-bit 10.2 kernel *)

Hash[1]

(* 1585106035 *)

To my understanding, the rationale is that it is better to use the extra bits to achieve a better distribution rather than have the exact same values. For that purpose, one of the other named algorithm hashes should be used:

(* version 8, 64-bit *)

Hash[1, "MD5"]

(* 68231128815270908652080701364659390939 *)

(* version 10, 32-bit *)

Hash[1, "MD5"]

(* 68231128815270908652080701364659390939 *)

Answer 2

I repost here from https://stackoverflow.com/a/39029618/3449795 (more visible)

The code below is pseudo-C, the highlight is wrong. Not my fault :D

---

I've been doing some reverse engeneering on 32 and 64 bit Windows version of Mathematica 10.4 and that's what I found:

32 BIT

It uses a Fowler–Noll–Vo hash function (FNV-1, with multiplication before) with 16777619 as FNV prime and ‭84696351‬ as offset basis. This function is applied on Murmur3-32 hashed value of the address of expression's data (MMA uses a pointer in order to keep one instance of each data). The address is eventually resolved to the value - for simple machine integers the value is immediate, for others is a bit trickier. The Murmur3-32 implementing function contains in fact an additional parameter (defaulted with 4, special case making behaving as in Wikipedia) which selects how many bits to choose from the expression struct in input. Since a normal expression is internally represented as an array of pointers, one can take the first, the second etc.. by repeatedly adding 4 (bytes = 32 bit) to the base pointer of the expression. So, passing 8 to the function will give the second pointer, 12 the third and so on. Since internal structs (big integers, machine integers, machine reals, big reals and so on) have different member variables (e.g. a machine integer has only a pointer to int, a complex 2 pointers to numbers etc..), for each expression struct there is a "wrapper" that combine its internal members in one single 32-bit hash (basically with FNV-1 rounds). The simplest expression to hash is an integer.

The murmur3_32() function has 1131470165 as seed, n=0 and other params as in Wikipedia.

So we have:

  hash_of_number = 16777619 * (84696351‬ ^ murmur3_32( pointer_to_number,  4))

with " ^ " meaning XOR and 4 is the number of bytes to take. I really didn't try it. Keep in mind that, while hashing an integer may be simple, other expressions need knowing their complete internal struct - and pointers cannot be exploited due to their encryption using WINAPI EncodePointer().

---

64 BIT

It uses a FNV-1 64 bit hash function with 0xAF63BD4C8601B7DF as offset basis and 0x100000001B3 as FNV prime, along with a SIP64-24 hash (here's the reference code) with the first 64 bit of 0x0AE3F68FE7126BBF76F98EF7F39DE1521 as k0 and the last 64 bit as k1. The function is applied to the base pointer of the expression and resolved internally. As in 32-bit's murmur3, there is an additional parameter (defaulted to 8) to select how many pointers to choose from the input expression struct. For each expression type there is a wrapper to condensate struct members into a single hash by means of FNV-1 64 bit rounds.

For a machine integer, we have:

    hash_number_64bit = 0x100000001B3 * (0xAF63BD4C8601B7DF ^ SIP64_24( &number, 8 ))

Again, I didn't really try it. Could anyone try?

---

Not for the faint-hearted

If you take a look at their notes on internal implementation, they say that "Each expression contains a special form of hash code that is used both in pattern matching and evaluation."

The hash code they're referring to is the one generated by these functions - at some point in the normal expression wrapper function there's an assignment that puts the computed hash inside the expression struct itself.

It would certainly be cool to understand HOW they can make use of these hashes for pattern matching purpose. So I had a try running through the bigInteger wrapper to see what happens - that's the simplest compound expression. It begins checking something that returns 1 - dunno what. So it executes

    var1 = 16777619 * (67918732 ^ hashMachineInteger(1));

with hashMachineInteger() is what we said before - including values.

Then it reads the length in dword of the bigInt from the struct (bignum_length) and runs

    result = 16777619 * (var1 ^ murmur3_32( &bignum_base_pointer, 4 * bignum_length ));

Note that murmur3_32() is called if bignum_length is greater than 8 (may be related to the max value of machine integers $MaxMachineNumber 2^32^32 and to what a bigInt is supposed to be).

So, the final code is

    if (bignum_length > 8){

    result = 16777619 * (16777619 * (67918732 ^ ( 16777619 * (84696351‬ ^ murmur3_32( 1, 4 )))) ^ murmur3_32( &bignum, 4 * bignum_length ));
    }

The value murmur3_32(1, 4) is of course a constant. I've made some hypoteses on the properties of this construction. The presence of many XORs and the fact that 16777619 + 67918732 = 84696351‬ may make one think that some sort of cyclic structure is exploited to check patterns. The software Cassandra uses the Murmur hash algorithm for token generation - see these images for what I mean for "cyclic structure". Maybe various primes are used for each expression - must still check.

---

Hope it helps

Note: informational only, not law infringiment intended

Creative Commons Attribution License applies