代码之家 › 专栏 › 技术社区 › Simon

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

wolfram-mathematica hash

Simon · 技术社区 · 14 年前

网上文件上说

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 使用?
是否有其他内置哈希代码?

3 回复 | 直到 9 年前

Michael Pilat 14 年前

默认的哈希算法或多或少是一个基本的32位哈希函数,应用于底层表达式表示,但精确的代码是Mathematica内核的专有组件。它在Mathematica版本之间会发生变化,并且缺少许多理想的加密属性,因此我个人建议您在任何重要的安全应用程序中使用MD5或其中一个SHA变体。内置哈希用于典型的数据结构使用(例如在哈希表中)。

您从文档中列出的命名哈希算法是当前唯一可用的。你在找一个特别的吗?

JavierG 9 年前

我在32位和64位Windows版本的Mathematica 10.4上做了一些反向工程,我发现:

32位

它使用 FowlerâNollâVo hash function (fnv-1,前面有乘法)以16777619作为fnv prime,84696351作为偏移基。此功能应用于 Murmur3-32 表达式数据地址的哈希值(mma使用指针来保存每个数据的一个实例)。地址最终被解析为值——对于简单的机器整数来说,值是立即的,对于其他整数来说,值是比较棘手的。实际上,该杂音3-32实现函数包含一个额外的参数(默认为4,特殊情况下,其行为与维基百科中的一样),该参数从输入的表达式结构中选择多少位。由于正常表达式在内部表示为指针数组,因此可以取第一个、第二个等。通过向表达式的基指针重复添加4(字节=32位)。所以,将8传递给函数将给出第二个指针,12传递给第三个指针,依此类推。由于内部结构(大整数、机器整数、机器实数、大实数等)具有不同的成员变量(例如,机器整数只有指向int的指针、指向数字的复杂2指针等),因此对于每个表达式结构都有一个“包装器”,将其内部成员组合在一个32位散列(基本上使用FNV-1轮次)。哈希最简单的表达式是一个整数。

这个 murmur3_32() 函数有1131470165作为种子,n=0和维基百科中的其他参数。

所以我们有:

  hash_of_number = 16777619 * (84696351â¬ ^ murmur3_32( &number ))

带“^”表示XOR。我真的没试过-指针是用 WINAPI EncodePointer() 所以它们不能在运行时被利用。(可能值得在Wine下运行Linux,修改版本为 EncodePonter ?)

64位

它使用一个fnv-1 64位散列函数,其中0xaf63bd4c8601b7df作为偏移基,0x100000001b3作为fnv prime,以及 SIP64-24 散列 here '是参考代码')的前64位为0x0AE3F68FE7126BBF76F98EF7F39DE1521,最后64位为k0。该函数应用于表达式的基指针并在内部解析。与32位的mundol3一样,还有一个额外的参数(默认为8)来选择从输入表达式结构中选择多少指针。对于每种表达式类型,都有一个包装器,通过fnv-164位循环将结构成员凝聚到单个哈希中。

对于机器整数,我们有:

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

再说一次,我没有真的尝试过。有人能试试吗?

不适合胆小的人

如果你看看他们 notes on internal implementation 他们说,“每个表达式都包含一种特殊形式的哈希代码,用于模式匹配和计算。”

他们引用的哈希代码是由这些函数生成的——在普通表达式包装函数的某个点上,有一个赋值将计算出的哈希放入表达式结构本身。

了解如何利用这些散列进行模式匹配当然很酷。所以我尝试运行biginteger包装器,看看会发生什么——这是最简单的复合表达式。它开始检查返回1-不知道什么。所以它执行

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

hashmachineinteger()是我们之前所说的-包括值。

然后它从结构中读取bigint的长度(以字节为单位)( bignum_length )和跑步

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

注意 杂音3 _32() 如果 4 * bignum_length 大于8(可能与机器整数的最大值有关 $MaxMachineNumber 2^32^32 通过和一个大人物交谈。

所以,最后的代码是

    if (bignum_length > 8){

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

我对这个结构的性质做了一些让步。许多XOR的存在以及 16777619 + 67918732 = 84696351â¬ 可能会让人认为某种循环结构被用来检查模式——即减去偏移量并除以素数,或者类似的东西。软件Cassandra使用杂音哈希算法生成令牌-参见 these images 我所说的“循环结构”。可能每个表达式都使用了不同的素数-必须检查。

希望有帮助

JavierG 9 年前

似乎hash调用内部数据的hashcode函数,然后将其除以2,取n[..]的前20位数字,然后是integerpart,加上1,即:

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