Używanie tablicy logicznej jako niestandardowego klucza słownika

Question

Próbuję utworzyć słownik w języku C#, który używa tablicy boolowskiej dla kluczy.

Dictionary<bool[], string> 

Tablica bool ma stałą długość równą 1000, a wszystkie mają tę samą długość. Mam problem z hashcode i powszechna metoda "exclusive" lub "nie ma tyle sensu ze względu na długość tablicy.

Podobne pytania dotyczące StackOverflow są adresowane za pomocą metody "exclusive" lub "w metodzie GetHashCode". Nie sądzę, że działa w tym kontekście. Chciałbym używać go jako:

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

gdzie EquaityComparer robi coś takiego:

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

oczywiście wszystko z typowych obaw o tablica bool jest zmienny i wielkości dowolny klawisz pochodzi jest istotne do wykonania tutaj ... chociaż nie mam rozwiązania.

Answer 1

Zarówno numery Equals, jak i HashCode są niepoprawne.

Prawdopodobnie chcesz użyć SequenceEqual do porównania macierzy dla równości, lub prostej pętli for.

Aby obliczyć kod skrótu, można użyć dowolnej ze standardowych metod. Bardzo ważne jest, że jeśli dwa elementy są równe, muszą mieć ten sam skrót.

Przykład

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

Podobne

• Guidelines and rules for GetHashCode

Answer 2

Aby uzyskać najlepszą wydajność, nie należy używać bool [] tablicę, która pozwoli mieszania i porównania bardzo powolny. Na przykład możesz przechowywać te same informacje w tablicy Uint32 [] o długości 1/32, co znacznie przyspiesza mieszanie i porównywanie.

Jeśli przechowujesz tablicę bool [], rozważ użycie niebezpiecznego kodu do mieszania/porównywania.

Jeśli chcesz tylko używać bezpiecznego kodu, przynajmniej usunąć warunkowe w pętli:

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

porównać również z wykorzystaniem własnego pętli powinno być szybsze niż SequenceEqual

Answer 3

Reguła dla realizacji GetHashCode jest to, że dwa dowolne obiekty, które są równe, muszą generować ten sam kod skrótu. Jedna z nich musi mieć jak najmniej kolizji (nie jest to wymaganie, aby kody mieszania były unikalne).

Ta implementacja wykorzystuje klasę BitArray zabrać logiczną tablicę w grupach 32, traktuje je jako bity i oblicza kod skrótu powstałych 32-bitowych liczb całkowitych:

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

kątem wydajności i spójności bym zalecamy przechowywanie swojego bool[] w innej klasie. Wiesz już, że klucz nie może się zmienić, więc możesz to wykorzystać, przechowując skrót w klasie klucza. Wewnętrzne operacje słownika mogą używać tego skrótu wielokrotnie dla pojedynczego dostępu (nie powinniśmy jednak znać wewnętrznych szczegółów implementacji, więc najlepiej jest założyć, że może to być wykonywane wiele razy).

Aby uzyskać wydajność, możesz nadal chcieć uzyskać dostęp, a nawet zachować odniesienie do numeru bool[] z zewnątrz, ale najbezpieczniejszą techniką byłoby wykonanie bezpiecznego egzemplarza w klasie klucza.

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

Jeśli oczekujesz częstym wartość hash 0 następnie można użyć innej zmiennej bool aby wskazać, czy wartość została obliczona.