Использовать байт [] как ключ в словаре

Question

Мне нужно использовать byte[] в качестве ключа в Dictionary. Поскольку byte[] не переопределяет метод по умолчанию GetHashCode, два отдельных объекта byte[], которые содержат одни и те же данные, будут использовать два отдельных слота в словаре. В основном, я хочу:

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 

Есть ли простой способ сделать это? Единственное, что я могу придумать, это построить класс-оболочку, который содержит только byte[] и переопределить GetHashCode на основе содержимого byte[], но это похоже на склонность к ошибкам.

Answer 1

По умолчанию byte[] будет сравниваться по ссылке, которая не является тем, что вы хотите в этом случае. Что вам нужно сделать, это указать пользовательский IEqualityComparer<byte[]> и выполнить требуемое сравнение.

Например

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

Затем вы можете сделать

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

решения для 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

Вашей мысли была моей первой мыслью, как хорошо. Я не думаю, что это было бы ошибкой. Но если вам не нравится этот параметр, вы можете создать класс, который реализует IEqualityComparer и передать экземпляр его конструктору Dictionary.

Answer 3

Когда вы извлекаете предметы из Словаря, вы используете новый оператор для байта []. Это будет искать другой (новый) байт [] экземпляр в словаре, которого нет.

Вот решение, которое будет работать:

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

Могли бы вы преобразовать байт [] в строку и использовать его в качестве ключа?

Что-то вроде:

 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

Таким образом, ответ JaredPar не является плохо но это может быть лучше несколькими способами. Прежде всего, the IEqualityComparer page говорит: «Мы рекомендуем, чтобы вы вышли из класса EqualityComparer вместо реализации интерфейса IEqualityComparer».

Во-вторых, реализация GetHashCode должна быть быстро. Он используется для быстрого устранения явно разных объектов, что, очевидно, будет пустой тратой времени для запуска Equals on. Таким образом, GetHashCode должен быть намного быстрее, чем на самом деле работает Equals.

В-третьих, возвращение суммы массива байтов, как JaredPar сделал, весьма вероятно, чтобы произвести столкновения - если байты в другом порядке, или относительные различия компенсируют друг друга, и т.д.

Я рекомендовал бы такое решение вместо этого:

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

Вверху, возвращая объект.Длина, действительно быстро и грязно, но также склонны возвращать много столкновений. Я думаю, мы сможем сделать лучше.

Если вы собираетесь исследовать все байты, что-то вроде этого меньше, чем простая сумма байтов, как в ответе JaredPar. Но опять же, это исследует все элементы, поэтому он не будет работать лучше, чем фактически работает Equals. Вы могли бы просто вернуть 0 безоговорочно и всегда принудительно использовать Equals.

Подчеркнем: это лучше, чем возврат суммы, как в ответе ДжаредПар. И всегда возвращение 0 лучше, чем это. И возвращение obj.Length лучше, чем возвращение 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; 
} 

Если вы не знаете, что байты [] массивы, которые вы используете в качестве ключа были сами криптографическими хэш, то вы можете использовать это предположение в вашу пользу , и просто вернуть первые 4 байта, преобразованные в int. Это, вероятно, работает нормально тоже, для общего назначения байтовых массивов:

// 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

Просто сделал немного более общий EqualityComparer, путем не работает с массивами, но на IEnumerable<T>.

В связи с тем, что у нас теперь есть T, нам нужно указать опциональный сравнительный коэффициент для элементов.

И последнее, но не менее важное: GetHashCode() никогда не должен бросать, а иногда вам это нужно быстро, а иногда вам нужно его более точно в первом прогоне. Таким образом, вы можете опционально определить точность, исходя из того, сколько элементов (максимум) хэш-код следует принимать во внимание для нашего собственного хэша.

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