2

我有以下代码：

    public void AddHash( int val )
    {
        m_Hash ^= (val & 0x3FFFFFF);
        m_Hash ^= (val >> 26) & 0x3F;
    }

我非常想知道它到底做了什么，但我很高兴知道如何构建一个bool HasHash( int val )告诉我 m_Hash 是否有那个数字的...

像这样的东西？

    public bool HasHash( int val )
    {
        return (m_Hash & val) == 0;
    }
4

2 回答 2

3

代码的作用

它采用最后 26 位val并将其与XORm_Hash结合使用。之后，它将它与前 6 位相结合。所以一个 32 位长度的整数将减少到 26 位。根据鸽巢原理，这是不可逆的。val

哈希函数

HasHash因此，即使您只调用AddHash一次，您也无法创建函数，因为其中的多个输入值val将产生相同的m_hash值。

于 2011-04-30T19:01:42.790 回答
3

编辑以修复@schnaader 发现的错误：它的作用是什么？这段代码可能想要向左（顺时针）旋转val6 位并形成补码和（编辑：不是乘积，正如我之前所说的）m_Hash - xor - 该旋转值和to的当前值产生一个新的m_Hash. m_Hash下一次将使用新的AddHash( )被调用。

但是，所编写的代码有一个错误：它只向左旋转了高 6 位val，而将val. 然后代码将三个值异或在一起：

  1. 新的低位（旧的高位）6位val；
  2. 的原始未移位的低 26 位val；和
  3. 的当前值m_Hash

将结果留在m_Hash.

它是如何做到的？你可以把它映射出来并模拟它：

  1. val & 0x3FFFFFF表示提取 的低位 26 位val。

  2. xor当前值为的那些 26 位m_Hash

  3. 现在val向右移动，使低 26 位从低位下降，将过去的高 6 位val留在 的低 6 位中val。

  4. 掩码0x3f仅提取那些低位 6 位（以防一些无关位转移到 的高位部分val）。
  5. xor那些具有当前值的低 6 位m_Hash给出新的m_Hash.

您知道旋转和异或是计算哈希的常见操作。

编辑： @schnaader 指出了原始代码中的错误：该代码忘记执行轮换的另一条腿：将低 26 位左移 6。要解决此问题，代码应如下所示：

public void AddHash( int val )
{
  m_Hash ^= ((val & 0x3FFFFFF) << 6);
  m_Hash ^= (val >> 26) & 0x3F;
}

至于你的HasHash( )功能：你应该知道这句话

return (m_Hash & val) == 0;

在许多情况下会返回 TRUE，包括一些您可能不想要的情况。例如，如果m_Hash == 0xC0和，该函数将返回 TRUE val == 0x03。

于 2011-04-30T19:05:03.747 回答