Uso de una matriz booleana como clave de diccionario personalizada

Question

Estoy tratando de crear un diccionario en C# que use una matriz booleana para sus claves.

Dictionary<bool[], string> 

La matriz bool tiene una longitud fija de 1000, y todas son de la misma longitud. Tengo problemas con el código hash y el método común de 'exclusivo o' no tiene tanto sentido debido a la longitud de la matriz.

Las preguntas similares en StackOverflow se tratan con el método 'exclusivo o' en el método GetHashCode. No creo que eso funcione en este contexto. Me gustaría utilizarlo como:

Dictionary<bool[], string> myDict = 
      new Dictionary<bool[], string>(EqualityComparer); 

donde EquaityComparer hace algo como:

public class EqualityComparer : IEqualityComparer<bool[]> 
    { 
     public bool Equals(bool[] x, bool[] y) 
     { 
      return x.SequenceEqual(y); 
     } 

     public int GetHashCode(bool[] x) 
     { 
      // this part doesn't work correctly 
      int hc = x.GetHashCode(); 
      return hc; 
     } 
    } 

Por supuesto, todas las preocupaciones habituales sobre la matriz bool ser mutable y el tamaño de cualquier clave derivada de ser relevante para el rendimiento se aplican aquí ... aunque no tengo una solución.

Answer 1

Tanto su Equals como HashCode son incorrectos.

Es de suponer que desea utilizar SequenceEqual para comparar las matrices de igualdad, o bien un bucle simple.

Para calcular un hashcode puede usar cualquiera de los métodos estándar. Es muy importante que si dos elementos son iguales, deben tener el mismo hash.

Ejemplo

public int GetHashCode(bool[] x) 
{ 
    int result = 29; 
    foreach (bool b in x) 
    { 
     if (b) { result++; } 
     result *= 23; 
    } 
    return result; 
} 

relacionados

• Guidelines and rules for GetHashCode

Answer 2

Para un mejor rendimiento, no utilice bool array [] que hará hash y comparación muy lento. Por ejemplo, puede almacenar la misma información en una matriz Uint32 [] de 1/32 de longitud, lo que hace que el hash y la comparación sean mucho más rápidos.

Si mantiene bool [] array, considere utilizar un código no seguro para hashing/comparison.

Si desea utilizar sólo el código de seguridad, al menos eliminar condicional en el bucle:

hash = hash * 3 + (int) x[i]; 

comparar también la utilización de su propio bucle debe ser más rápido que SequenceEqual

Answer 3

La regla para la implementación de GetHashCode es que dos objetos iguales que sean iguales deben generar el mismo código hash. Una de las directrices es tener el menor número posible de colisiones (no es un requisito que los códigos hash sean únicos).

Esta aplicación utiliza la clase BitArray tomar su matriz booleana en grupos de 32, los trata como bits y calcula el código hash de los enteros de 32 bits resultantes:

public int GetHashCode(bool[] x) 
{ 
    // Trivial case 
    if (x.Length == 0) return 0; 

    // Convert the bool array to a BitArray to use framework functions 
    BitArray binary = new BitArray(x); 

    //Determine the max # of 32-bit INTS this array represents 
    int intLength = (x.Length-1)/32 + 1; 
    int [] ints = new int[intLength]; 

    // Copy each block of 32-bits to an int 
    binary.CopyTo(ints, 0); 

    // Take the exclusive OR of each int and return the result's hash code 
    return ints.Aggregate((i1, i2) => i1^i2).GetHashCode(); 
} 

Answer 4

Para obtener un rendimiento y consistencia que lo haría recomendamos almacenar su bool[] en otra clase. Ya sabes que la clave puede no cambiar, así que puedes aprovechar esto almacenando el hash en la clase de clave. Las operaciones internas del diccionario pueden usar este hash varias veces para un solo acceso (no se supone que tengamos que conocer los detalles de la implementación interna, por lo que es mejor suponer que esto se puede ejecutar muchas veces).

Para obtener rendimiento, es posible que desee acceder o incluso mantener una referencia externa al bool[], pero la técnica más segura sería hacer una copia segura en la clase de llave.

public class BoolArrayKey 
{ 
    private int hash; 
    private bool[] data; 

    public BoolArrayKey(bool[] source) 
    { 
     data = new bool[source.Length]; 
     Array.Copy(source, data, source.Length); 
    } 

    public override bool Equals(object obj) 
    { 
     BoolArrayKey other = obj as BoolArrayKey; 
     if (other == null) 
     { 
      return false; 
     } 

     return other.data.SequenceEqual(data); 
    } 

    public override int HashCode() 
    { 
     if (hash == 0) 
     { 
      // Mark's hash implementation here, store the result in `hash`. 
     } 

     return hash;  
    } 
} 

Si una se espera un valor hash frecuente de 0 entonces usted podría utilizar otra variable bool para indicar si el valor se ha calculado.