Generar un buen código hash (GetHashCode) para un BitArray

Question

Necesito generar un código hash rápido en GetHashCode para un BitArray. Tengo un diccionario donde las claves son BitArrays, y todas las 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 caso?

ACTUALIZACIÓN:

El enfoque Tomé originalmente era para acceder a la matriz interna de enteros directamente a través de la reflexión (la 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 'iguales' método 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 Iguales llamadas vs 16608 para el XOR para mis datos de prueba). Tenga en cuenta que este enfoque corrige un error en el anterior donde los bits más allá del final de la matriz de bits podrían afectar el valor hash. Esto podría suceder si la matriz de bits se redujera 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 esto:

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 de 32 bits o menos, solo tiene que convertirlas en enteros de 32 bits (relleno con cero bits si es necesario).

Si pueden ser más largos, puede convertirlos en una serie de enteros de 32 bits y XOR, o mejor: utilizar el algoritmo descrito en Java efectivo.

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

Tomado de here. El campo1, campo2 correcpond los primeros 32 bits, los segundos 32 bits, etc.

Answer 2

Es una clase terrible para actuar como 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 genial, crea una tonelada de basura.

Pida, robe o pida prestado para usar un BitVector32 en su lugar. Tiene una buena implementación para GetHashCode(). Si tiene más de 32 bits, considere la opción de girar su propia clase para poder acceder a la matriz subyacente sin tener que copiar.