5

我需要在 GetHashCode 中为 BitArray 生成一个快速哈希码。我有一个字典，其中的键是 BitArrays，并且所有 BitArrays 的长度都相同。

有没有人知道一种从可变位数生成良好哈希的快速方法，就像在这种情况下一样？

更新：

我最初采用的方法是直接通过反射访问内部整数数组（在这种情况下，速度比封装更重要），然后对这些值进行异或。XOR 方法似乎运作良好，即在 Dictionary 中搜索时不会过度调用我的“Equals”方法：

    public int GetHashCode(BitArray array)
    {
        int hash = 0;
        foreach (int value in array.GetInternalValues())
        {
            hash ^= value;
        }
        return hash;
    }

然而，Mark Byers 建议并在 StackOverflow 其他地方看到的方法稍微好一些（16570 Equals 调用 vs 16608 用于我的测试数据的 XOR）。请注意，这种方法修复了前一种方法中的一个错误，即位数组末尾之外的位可能会影响哈希值。如果位数组的长度减少，就会发生这种情况。

    public int GetHashCode(BitArray array)
    {
        UInt32 hash = 17;
        int bitsRemaining = array.Length;
        foreach (int value in array.GetInternalValues())
        {
            UInt32 cleanValue = (UInt32)value;
            if (bitsRemaining < 32)
            {
                //clear any bits that are beyond the end of the array
                int bitsToWipe = 32 - bitsRemaining;
                cleanValue <<= bitsToWipe;
                cleanValue >>= bitsToWipe;
            }

            hash = hash * 23 + cleanValue;
            bitsRemaining -= 32;
        }
        return (int)hash;
    }

GetInternalValues 扩展方法是这样实现的：

public static class BitArrayExtensions
{
    static FieldInfo _internalArrayGetter = GetInternalArrayGetter();

    static FieldInfo GetInternalArrayGetter()
    {
        return typeof(BitArray).GetField("m_array", BindingFlags.NonPublic | BindingFlags.Instance);
    }

    static int[] GetInternalArray(BitArray array)
    {
        return (int[])_internalArrayGetter.GetValue(array);
    }

    public static IEnumerable<int> GetInternalValues(this BitArray array)
    {
        return GetInternalArray(array);
    }

... more extension methods
}

欢迎任何改进建议！

4

2 回答 2

3

在字典中充当键是一个可怕的类。实现 GetHashCode() 的唯一合理方法是使用其 CopyTo() 方法将位复制到 byte[] 中。这不是很好，它会产生大量垃圾。

乞求、偷窃或借用 BitVector32 来代替。它对 GetHashCode() 有很好的实现。如果你有超过 32 位，那么考虑旋转你自己的类，这样你就可以得到底层数组而不必复制。

于 2010-06-27T13:28:01.590 回答
1

如果位数组是 32 位或更短，那么您只需将它们转换为 32 位整数（必要时用零位填充）。

如果它们可以更长，那么您可以将它们转换为一系列 32 位整数并对它们进行异或，或者更好：使用有效 Java 中描述的算法。

public int GetHashCode()
{
    int hash = 17;
    hash = hash * 23 + field1.GetHashCode();
    hash = hash * 23 + field2.GetHashCode();
    hash = hash * 23 + field3.GetHashCode();
    return hash;
}

取自这里。field1、field2 对应前 32 位、后 32 位等。

于 2010-06-26T22:35:30.020 回答