为BitArray生成良好的哈希码(GetHashCode) [英] Generating a good hash code (GetHashCode) for a BitArray

问题描述

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

I need to generate a fast hash code in GetHashCode for a BitArray. I have a Dictionary where the keys are BitArrays, and all the BitArrays are of the same length.

在这种情况下，有人知道从可变数量的位生成良好哈希的快速方法吗?

Does anyone know of a fast way to generate a good hash from a variable number of bits, as in this scenario?

更新:

我最初采用的方法是直接通过反射访问内部整数数组(在这种情况下，速度比封装更重要)，然后对这些值进行XOR.XOR方法似乎很好用，即在字典中搜索时，我的'Equals'方法没有被过度调用:

The approach I originally took was to access the internal array of ints directly through reflection (speed is more important than encapsulation in this case), then XOR those values. The XOR approach seems to work well i.e. my 'Equals' method isn't called excessively when searching in the Dictionary:

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

但是，Mark Byers建议的方法以及在StackOverflow的其他地方看到的方法要好一些(对于我的测试数据，XOR等于16570，而XOR等于16608).请注意，此方法修复了前一个错误，该错误中，超出位数组末尾的位可能会影响哈希值.如果位数组的长度减小，则可能会发生这种情况.

However, the approach suggested by Mark Byers and seen elsewhere on StackOverflow was slightly better (16570 Equals calls vs 16608 for the XOR for my test data). Note that this approach fixes a bug in the previous one where bits beyond the end of the bit array could affect the hash value. This could happen if the bit array was reduced in length.

    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扩展方法是这样实现的:

The GetInternalValues extension method is implemented like this:

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
}

欢迎提出任何改进建议！

Any suggestions for improvement are welcome!

推荐答案

如果位数组为32位或更短，则只需将它们转换为32位整数(必要时填充零位).

If the bit arrays are 32 bits or shorter then you just need to convert them to 32 bit integers (padding with zero bits if necessary).

如果它们可以更长，则可以将它们转换为一系列32位整数并对它们进行XOR，或者更好:使用Effective Java中描述的算法.

If they can be longer then you can either convert them to a series of 32-bit integers and XOR them, or better: use the algorithm described in Effective 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位，等等.

Taken from here. The field1, field2 correcpond the the first 32 bits, second 32 bits, etc.

这篇关于为BitArray生成良好的哈希码(GetHashCode)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！