Użyj bajtu [] jako klucza w słowniku

Question

Potrzebuję użyć byte[] jako klucza w Dictionary. Ponieważ byte[] nie zastępuje domyślnej metody GetHashCode, dwa oddzielne obiekty byte[], które zawierają te same dane, będą używać dwóch oddzielnych gniazd w słowniku. Zasadniczo to, czego chcę, to:

Dictionary<byte[], string> dict = new Dictionary<byte[], string>(); 
dict[new byte[] {1,2,3}] = "my string"; 
string str = dict[new byte[] {1,2,3}]; 
// I'd like str to be set to "my string" at this point 

Czy istnieje prosty sposób na zrobienie tego? Jedyne, co mogę wymyślić, to zbudować klasę wrapperów, która zawiera tylko byte[] i zastąpi GetHashCode w oparciu o zawartość byte[], ale wydaje się to podatne na błędy.

Answer 1

Domyślnie byte[] będzie porównywany przez odniesienie, co nie jest w tym przypadku pożądane. To, co musisz zrobić, to określić niestandardowe IEqualityComparer<byte[]> i wykonać porównanie, które chcesz.

Na przykład

public class ByteArrayComparer : IEqualityComparer<byte[]> { 
    public bool Equals(byte[] left, byte[] right) { 
    if (left == null || right == null) { 
     return left == right; 
    } 
    return left.SequenceEqual(right); 
    } 
    public int GetHashCode(byte[] key) { 
    if (key == null) 
     throw new ArgumentNullException("key"); 
    return key.Sum(b => b); 
    } 
} 

Następnie można zrobić

var dict = new Dictionary<byte[], string>(new ByteArrayComparer()); 

rozwiązanie dla 2,0

public class ByteArrayComparer : IEqualityComparer<byte[]> { 
    public bool Equals(byte[] left, byte[] right) { 
    if (left == null || right == null) { 
     return left == right; 
    } 
    if (left.Length != right.Length) { 
     return false; 
    } 
    for (int i= 0; i < left.Length; i++) { 
     if (left[i] != right[i]) { 
     return false; 
     } 
    } 
    return true; 
    } 
    public int GetHashCode(byte[] key) { 
    if (key == null) 
     throw new ArgumentNullException("key"); 
    int sum = 0; 
    foreach (byte cur in key) { 
     sum += cur; 
    } 
    return sum; 
    } 
} 

Answer 2

twojej myśli była moja pierwsza myśl, jak również. Nie sądzę, że byłoby to podatne na błędy. Ale jeśli nie podoba ci się ta opcja, możesz stworzyć klasę, która implementuje IEqualityComparer i przekazuje jej instancję do konstruktora Dictionary.

Answer 3

Podczas pobierania elementów ze słownika korzystasz z operatora new dla bajtu []. Spowoduje to wyszukanie innej (nowej) instancji bajtu [] w Słowniku, która nie jest obecna.

Oto rozwiązanie, które będzie działać:

var dict = new Dictionary<byte[], string>(); 

      var b = new byte[] { 1,2,3}; 

      dict[b] = "my string"; 

      var value = dict[b]; 

      Console.WriteLine(value); 

Answer 4

można przekonwertować byte [] na ciąg i użyć jej jako klucz?

Coś jak:

 ASCIIEncoding enc = new ASCIIEncoding(); 
     byte[] input; 
     string demo = new string(enc.GetChars(input)); 
     byte[] decode = enc.GetBytes(demo.ToCharArray()); 

Answer 5

using System; 
using System.Collections; 
using System.Collections.Generic; 

[Serializable] 
class StructuralEqualityComparer : IEqualityComparer, IEqualityComparer<object> 
{ 
    public new bool Equals(object x, object y) 
    { 
     var s = x as IStructuralEquatable; 
     return s == null ? object.Equals(x, y) : s.Equals(y, this); 
    } 

    public int GetHashCode(object obj) 
    { 
     var s = obj as IStructuralEquatable; 
     return s == null ? EqualityComparer<object>.Default.GetHashCode(obj) : s.GetHashCode(this); 
    } 
} 

Answer 6

Więc odpowiedź JaredPar nie jest złe ale mogłoby być lepiej na kilka sposobów. Przede wszystkim, the IEqualityComparer page mówi: "Zalecamy czerpanie z klasy EqualityComparer zamiast implementowania interfejsu IEqualityComparer."

Po drugie, implementacja GetHashCode ma być szybka. Służy do szybkiej eliminacji oczywiście różnych obiektów, co oczywiście byłoby stratą czasu na uruchomienie Equals. Tak więc GetHashCode powinien być znacznie szybszy niż faktycznie działający Equals.

trzecie, wracając suma tablicy bajtów jako JaredPar zrobił, jest bardzo prawdopodobne, aby produkować kolizji - jeżeli bajty są w innej kolejności, lub względne różnice znoszą się nawzajem, itp

Więc zamiast tego polecam takie rozwiązanie:

public class ByteArrayComparer : EqualityComparer<byte[]> 
{ 
    public override bool Equals(byte[] first, byte[] second) 
    { 
     if (first == null || second == null) { 
      // null == null returns true. 
      // non-null == null returns false. 
      return first == second; 
     } 
     if (ReferenceEquals(first, second)) { 
      return true; 
     } 
     if (first.Length != second.Length) { 
      return false; 
     } 
     // Linq extension method is based on IEnumerable, must evaluate every item. 
     return first.SequenceEqual(second); 
    } 
    public override int GetHashCode(byte[] obj) 
    { 
     if (obj == null) { 
      throw new ArgumentNullException("obj"); 
     } 
     // quick and dirty, instantly identifies obviously different 
     // arrays as being different 
     return obj.Length; 
    } 
} 

Powyżej, wracając obj.Długość, to naprawdę szybkie i brudne, ale także podatne na powrót wielu kolizji. Myślę, że możemy zrobić lepiej.

Jeśli zamierzasz zbadać wszystkie bajty, coś takiego jest mniej podatne na kolizję niż prosta suma bajtów, jak w odpowiedzi JaredPar. Ale znowu, to bada wszystkie elementy, więc nie będzie lepiej, niż faktycznie działa Equals. Równie dobrze możesz po prostu zwrócić zero bezwarunkowo i zawsze wymuszać użycie równań.

Podkreślam: jest to lepsze niż zwrócenie kwoty, jak w odpowiedzi JaredPar. I zawsze zwracanie 0 jest lepsze niż to. A wracając obj.Length jest lepsze niż powrót 0.

// This is not recommended. Performance is too horrible. 
public override int GetHashCode(byte[] obj) 
{ 
    // Inspired by fletcher checksum. Not fletcher. 
    if (obj == null) { 
     throw new ArgumentNullException("obj"); 
    } 
    int sum = 0; 
    int sumOfSum = 0; 
    foreach (var val in obj) { 
     sum += val; // by default, addition is unchecked. does not throw OverflowException. 
     sumOfSum += sum; 
    } 
    return sum^sumOfSum; 
} 

Jeśli zdarzy się, że bajt [] tablice których używasz jako klucz były same skróty kryptograficzne, to można wykorzystać to założenie do zasiłku i po prostu zwróć pierwsze 4 bajty skonwertowane na int. Prawdopodobnie działa zbyt dobrze, dla tablic bajtowych ogólnego przeznaczenia:

// This implementation works great if you assume the byte[] arrays 
// are themselves cryptographic hashes. It probably works alright too, 
// for general-purpose byte arrays. 
public override int GetHashCode(byte[] obj) 
{ 
    if (obj == null) { 
     throw new ArgumentNullException("obj"); 
    } 
    if (obj.Length >= 4) { 
     return BitConverter.ToInt32(obj, 0); 
    } 
    // Length occupies at most 2 bits. Might as well store them in the high order byte 
    int value = obj.Length; 
    foreach (var b in obj) { 
     value <<= 8; 
     value += b; 
    } 
    return value; 
} 

Answer 7

Podobnie uczynił EqualityComparer trochę bardziej uniwersalne, a przez nie pracy na tablicach, lecz na IEnumerable<T>.

Ze względu na to, że mamy teraz T, musimy mieć możliwość określenia opcjonalnego porównywalnika równości dla elementów.

Last but not least, GetHashCode() nigdy nie powinien rzucać, a czasami potrzebujesz go szybko, a czasami potrzebujesz go dokładniej w pierwszym uruchomieniu. Możesz więc opcjonalnie określić dokładność, od ilu pozycji (maksimum) kod haszujący powinien być brany pod uwagę dla naszego własnego skrótu.

public class EnumerableEqualityComparer<T> : IEqualityComparer<IEnumerable<T>> 
{ 
    private static readonly Lazy<IEqualityComparer<IEnumerable<T>>> Lazy = new Lazy<IEqualityComparer<IEnumerable<T>>>(() => new EnumerableEqualityComparer<T>()); 
    private int accuracy; 
    private IEqualityComparer<T> comparer; 

    public EnumerableEqualityComparer() 
     : this(-1) 
    { 
    } 

    public EnumerableEqualityComparer(int accuracy) 
     : this(accuracy, null) 
    { 
    } 

    public EnumerableEqualityComparer(IEqualityComparer<T> elementEqualityComparer) 
     : this(-1, elementEqualityComparer) 
    { 
    } 

    public EnumerableEqualityComparer(int accuracy, IEqualityComparer<T> elementEqualityComparer) 
    { 
     if (accuracy < 0) 
     { 
      accuracy = 4; 
     } 

     this.accuracy = accuracy; 
     comparer = elementEqualityComparer ?? EqualityComparer<T>.Default; 
    } 

    public static IEqualityComparer<IEnumerable<T>> Default { get; private set; } = Lazy.Value; 

    public bool Equals(IEnumerable<T> x, IEnumerable<T> y) 
    { 
     if (ReferenceEquals(x, y)) 
     { 
      return true; 
     } 

     if (ReferenceEquals(x, null) 
      || ReferenceEquals(y, null)) 
     { 
      return false; 
     } 

     return x.SequenceEqual(y, comparer); 
    } 

    public int GetHashCode(IEnumerable<T> obj) 
    { 
     if (ReferenceEquals(obj, null)) 
     { 
      return -1; 
     } 

     var count = (obj as ICollection<T>)?.Count ?? 1; 
     var hashCode = count * 49297; 

     foreach (var item in obj.Take(accuracy)) 
     { 
      hashCode += comparer.GetHashCode(item) * 17123; 
     } 

     return hashCode; 
    } 
}