Generar un código de buena almohadilla (GetHashCode) para un BitArray

Question

necesito para generar un código hash rápido en GetHashCode para un BitArray. Tengo un diccionario donde las claves son BitArrays, y todos los BitArrays son de la misma longitud.

¿Alguien sabe de una manera rápida de generar un buen hash a partir de un número variable de bits, como en este escenario?

ACTUALIZACIÓN:

El enfoque Tomé originalmente era para acceder a la matriz interna de enteros directamente a través de la reflexión (velocidad es más importante que la encapsulación en este caso), entonces XOR esos valores. El enfoque XOR parece funcionar bien, es decir, mi método de 'iguales' no se llama excesivamente la hora de buscar en el diccionario:

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

Sin embargo, el enfoque sugerido por Mark Byers y visto en otros lugares en StackOverflow fue ligeramente mejor (16570 Igual a llamadas vs 16608 para el XOR para mi de datos de prueba). Tenga en cuenta que este enfoque corrige un error en el anterior donde los bits más allá del extremo de la matriz de bits podrían afectar el valor hash. Esto podría suceder si la matriz de bits se reduce en longitud.

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

El método de extensión GetInternalValues ??se implementa como sigue:

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
}

¿Alguna sugerencia para mejorar son bienvenidos!

Answer 1

Si las matrices de bits son 32 bits o más corto a continuación, sólo tiene que convertirlos a números enteros de 32 bits (bits de relleno con cero si es necesario).

Si pueden ser más largo entonces usted puede convertir a una serie de enteros de 32 bits y XOR, o mejor: utilizar el algoritmo descrito en 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;
}

aquí . El campo1, campo2 correcpond los los primeros 32 bits, segundos 32 bits, etc.

Answer 2

Es una clase terrible de actuar como una clave en un diccionario. La única forma razonable de implementar GetHashCode () es mediante el uso de su método CopyTo () para copiar los bits en un byte []. Eso no es grande, se crea una tonelada de basura.

Beg robar o pedir prestado a utilizar un BitVector32 lugar. Tiene una buena aplicación para GetHashCode (). Si usted tiene más de 32 bits y luego considerar hacer girar su propia clase para que pueda llegar a la matriz subyacente sin tener que copiar.