Verwenden eines Booleschen Arrays als benutzerdefinierten Wörterbuchschlüssel

Question

Ich versuche ein Dictionary in C# zu erstellen, das ein Boolesches Array für seine Schlüssel verwendet.

Das Bool-Array hat eine feste Länge von 1000, und alle haben die gleiche Länge. Ich habe Probleme mit dem Hashcode und die übliche Methode eines 'exklusiven' oder '' 'macht wegen der Länge des Arrays keinen Sinn.

Ähnliche Fragen zu StackOverflow werden mit der 'exklusiven oder' in der GetHashCode-Methode behandelt. Ich denke nicht, dass das in diesem Zusammenhang funktioniert. Ich möchte es benutzen, wie:

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

wo EquaityComparer tut so etwas wie:

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

Natürlich alle üblichen Bedenken über die Bool-Array ist wandelbar und die Größe jeder abgeleiteten Schlüssel relevant Zur Leistung gilt hier ... obwohl ich keine Lösung habe.

Answer 1

Ihre Equals und HashCode sind nicht korrekt.

Vermutlich möchten Sie SequenceEqual verwenden, um die Arrays auf Gleichheit oder eine einfache for-Schleife zu vergleichen.

Um einen Hashcode zu berechnen, können Sie eine der Standardmethoden verwenden. Es ist sehr wichtig, dass wenn zwei Elemente gleich sind, sie denselben Hashwert haben müssen.

Beispiel

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

Verwandte

• Guidelines and rules for GetHashCode

Answer 2

Für eine optimale Leistung nicht bool [] Array verwendet werden, die wirklich langsam Hashing und Vergleiche machen. Zum Beispiel können Sie dieselben Informationen in einem Uint32 [] -Array mit einer Länge von 1/32 speichern, was das Hashing und den Vergleich viel schneller macht.

Wenn Sie das Array bool [] beibehalten, sollten Sie den unsicheren Code für Hashing/Vergleich verwenden.

Wenn Sie nur wollen, sicheren Code verwenden, zumindest in der Schleife bedingten entfernen:

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

auch Ihre eigene Schleife vergleichen verwenden, sollten

Answer 3

Die Regel für die Umsetzung GetHashCode als SequenceEqual schneller ist, dass Alle zwei Objekte, die gleich sind, müssen denselben Hash-Code erzeugen. Eine Richtlinie soll so wenige Kollisionen wie möglich haben (es ist keine Voraussetzung, dass Hash-Codes eindeutig sind).

Diese Implementierung verwendet die BitArray Klasse Ihre boolean-Array in Gruppen von 32 zu nehmen, sie als Bits behandelt und berechnet den Hash-Code der resultierenden 32-Bit-Integer:

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

Für Leistung und Konsistenz würde ich empfehlen, Ihre bool[] in einer anderen Klasse zu speichern. Sie wissen bereits, dass sich der Schlüssel möglicherweise nicht ändert. Sie können dies also nutzen, indem Sie den Hash in der Schlüsselklasse speichern. Die wörterbuchinternen Operationen können diesen Hash mehrmals für einen einzelnen Zugriff verwenden (wir brauchen die internen Implementierungsdetails nicht zu kennen, daher ist es am besten anzunehmen, dass dies mehrfach ausgeführt werden kann).

Für die Leistung möchten Sie vielleicht immer noch auf die bool[] extern zugreifen oder sie sogar beibehalten, aber die sicherste Technik wäre, eine sichere Kopie in der Schlüsselklasse zu erstellen.

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

Wenn ein Sie sind eine häufige Hash-Wert von 0 erwarten, dann könnten Sie eine andere bool Variable verwenden, wenn der Wert berechnet worden war, um anzuzeigen.