Mathematica使用的默认哈希码是什么？

Question

在线文档中说明

Hash[expr] 
  gives an integer hash code for the expression expr.
Hash[expr,"type"]
  gives an integer hash code of the specified type for expr.

它还提供了“可能的哈希代码类型”：

• “Adler32” Adler 32位循环冗余校验
• “CRC32” 32位循环冗余校验
• “MD2” 128位MD2代码
• “MD5” 128位MD5代码
• “SHA” 160位SHA-1代码
• “SHA256” 256位SHA代码
• “SHA384” 384位SHA代码
• “SHA512” 512位SHA代码

然而，上述哈希代码都与 Hash[expr] 默认返回的哈希代码不相对应。

因此，我的问题是：

• Hash 默认使用什么方法？
• 是否有其他内置的哈希码？

- Simon

---

相关："Hash[expr]的默认行为和在不同版本的Mathematica中的哈希"。 - Alexey Popkov

Answer 1

默认哈希算法是基于基本的32位哈希函数应用于底层表达式表示的，但确切的代码是Mathematica内核的专有组件。它随着Mathematica版本的变化而可能发生改变，并缺乏许多理想的加密属性，因此我个人建议您在任何需要安全考虑的严肃应用中使用MD5或SHA变体之一。内置哈希旨在用于典型的数据结构使用（例如在哈希表中）。

你列出的来自文档的命名哈希算法是当前唯一可用的。你是否特别寻找不同的哈希算法？

- Michael Pilat

---

我不确定为什么Hash使用第二个参数而不是选项，也没有办法内省出可能的算法，尽管这是一个很好的建议。 - Michael Pilat

另外，@Simon，请记住大多数哈希函数（包括Hash []，MD5和SHA）并不是“完美”的（即不可逆），而且不幸的是，特别是Hash。请评估并考虑此事：Length [DeleteDuplicates [Hash / @ Range [10 ^ 6]]] =) - Michael Pilat

@Simon 但是 Length@DictionaryLookup[___] - Length@DeleteDuplicates@(Hash /@ DictionaryLookup[___]) == 1 :), 所以我认为你应该测试一下你的应用程序的单射性质。 - Dr. belisarius

@Simon，所以通过了解算法来推导它 :D - Dr. belisarius

公平地说，我不会期望一个名为“Hash”的函数在默认情况下具有加密安全性。有很多哈希的用例不需要这些属性。 - slim

Answer 2

我一直在对Mathematica 10.4的32位和64位Windows版本进行反向工程，发现了以下内容：

32位

它使用Fowler-Noll-Vo哈希函数（FNV-1，乘法在前）作为哈希函数，其中16777619是FNV质数，84696351是偏移基数。该函数应用于表达式数据地址的Murmur3-32哈希值（MMA使用指针以保留每个数据的一个实例）。最终，地址被解析为值 - 对于简单的机器整数，该值是立即的，对于其他类型则有点棘手。实际上，Murmur3-32实现函数包含一个附加参数（默认为4，特殊情况下与维基百科中的行为相同），该参数选择从输入的表达式结构中选择多少位。由于正常表达式在内部表示为指针数组，因此可以通过重复添加4（字节= 32位）到表达式的基指针来取第一个、第二个等等。因此，将8传递给函数将给出第二个指针，12为第三个，依此类推。由于内部结构（大整数、机器整数、机器实数、大实数等）具有不同的成员变量（例如，机器整数仅具有指向int的指针，而复杂的2个指向数字的指针等），因此对于每个表达式结构都有一个“包装器”，将其内部成员组合成一个单一的32位哈希（基本上使用FNV-1轮）。最简单的要哈希的表达式是整数。

"

murmur3_32()函数的种子为1131470165，n=0，其他参数与维基百科相同。

因此我们有：

"

  hash_of_number = 16777619 * (84696351‬ ^ murmur3_32( &number ))

在这里，“ ^ ”表示异或运算。我并没有尝试过这个方法——指针是使用WINAPI EncodePointer()进行编码的，因此无法在运行时被利用。（也许值得在Wine下的Linux中运行，并使用修改版的EncodePonter？）

---

64位

它使用FNV-1 64位哈希函数，偏移基础为0xAF63BD4C8601B7DF，FNV质数为0x100000001B3，以及SIP64-24哈希（这里是参考代码），其中第一个64位为k0，最后一个64位为k1。该函数应用于表达式的基指针并在内部解析。与32位的murmur3一样，还有一个额外参数（默认为8）来选择从输入表达式结构中选择多少个指针。对于每种表达式类型，都有一个包装器通过FNV-1 64位轮来将结构成员压缩为单个哈希。

对于机器整数，我们有：

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

再次强调，我并没有真正尝试过。有人可以试试吗？

---

不适合胆小者

如果您查看他们的 内部实现笔记，他们说：“每个表达式都包含一种特殊形式的哈希码，用于模式匹配和评估。”

他们所指的哈希码是由这些函数生成的-在正常表达式包装函数中的某个点上，有一个赋值将计算出的哈希放置在表达式结构体本身内。

了解他们如何利用这些哈希进行模式匹配肯定很酷。因此，我尝试运行bigInteger包装器以查看会发生什么-那是最简单的复合表达式。 它开始检查返回1的某些内容-不知道是什么。 所以它执行

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

使用hashMachineInteger()是我们之前提到的 - 包括值。

然后它从结构体中读取bigInt的字节长度（bignum_length），并运行。

    result = 16777619 * (v10 ^ murmur3_32(v6, 4 * v4));

请注意，如果4 * bignum_length大于8，则调用murmur3_32()（可能与机器整数的最大值$MaxMachineNumber2^32^32有关，反之则是一个bigInt应该是什么）。

因此，最终代码如下：

    if (bignum_length > 8){

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

我对这个结构的属性做出了一些假设。存在许多异或门，并且 16777619 + 67918732 = 84696351‬ 的事实可能使人们认为某种循环结构被利用来检查模式——即减去偏移量并除以质数，或者类似于此的东西。软件Cassandra使用Murmur哈希算法进行令牌生成——请参见这些图片，了解我所说的“循环结构”。也许每个表达式都使用不同的质数——还需要检查。

---

希望能帮到你

- JavierG

Answer 3

看起来Hash调用了内部的Data`HashCode函数，然后将其除以2，取N[..]的前20位数字，再取整数部分，加1，即：

    IntegerPart[N[Data`HashCode[expr]/2, 20]] + 1

- JavierG

---

有趣的观察，但我认为不完全正确：Tally[(IntegerPart[N[Data`HashCode[#]/2, 20]] + 1) - Hash[#] & /@ RandomReal[{-1, 1}, 1000]] 的结果是 {{0, 256}, {2, 273}, {1, 471}}。 - agentp

这似乎是有效的：myhash[exp_] := ( (# + Mod[#, 2] - 4 Floor[(Mod[#, 4] + 1)/4]) &@ Data`HashCode[exp])/2 - agentp