5

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?

UPDATE:

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;
    }

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;
    }

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!

4

2 に答える 2

3

辞書のキーとして機能するのはひどいクラスです。GetHashCode（）を実装する唯一の合理的な方法は、CopyTo（）メソッドを使用してビットをbyte[]にコピーすることです。それは素晴らしいことではありません、それは大量のゴミを作成します。

代わりにBitVector32を使用するには、頼むか、盗むか、借りてください。GetHashCode（）の優れた実装があります。32ビットを超える場合は、コピーせずに基になる配列に到達できるように、独自のクラスをスピンすることを検討してください。

于 2010-06-27T13:28:01.590 に答える
1

ビット配列が32ビット以下の場合は、それらを32ビット整数に変換する必要があります（必要に応じてゼロビットでパディングします）。

それより長くなる可能性がある場合は、それらを一連の32ビット整数に変換してXORするか、またはより適切に行うことができます。EffectiveJavaで説明されているアルゴリズムを使用してください。

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ビット、2番目の32ビットなどに対応します。

于 2010-06-26T22:35:30.020 に答える