Использование байтового массива в качестве словарного ключа

Question

Я хочу использовать байтовый массив в качестве ключа поиска в concurentDictionary. В настоящее время я решаю это, используя пользовательский EqualityComparer<byte[]>.

Это прекрасно работает, но я понимаю, что генератор hashcode генерирует много перекрытий, когда вещи оказываются в одном и том же хэш-ведре.

public class ByteArrayEqualityComparer : EqualityComparer<byte[]> 
{ 
    public override bool Equals(byte[] x, byte[] y) 
    { 
     //fast buffer compare 
     return UnsafeCompare(x, y); 
    } 

    public override int GetHashCode(byte[] obj) 
    { 
     int hash = 0; 
     for (int i = 0; i < obj.Length; i += 2) 
     { 
      hash += obj[i]; //xor? shift? black magic? 
     } 
     return hash; 
    } 
} 

Что было бы хорошей формулой для создания относительно быстрого хеша из массива байтов?

Моя идея состоит в том, что я могу вычислить хэш-код, пропустив каждый x байтов для скорости. Поскольку окончательное сравнение все еще выполняется по полному набору данных, кажется бессмысленным сравнивать все байты несколько раз.

Я предполагаю, что некоторая магия xor и смещение на хэш-var сделают все лучше.

Это чрезвычайно критичная производительность, поэтому любой ярлык, который можно использовать, тоже приветствуется.

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

public struct ByteArrayKey 
{ 
    public readonly byte[] Bytes; 
    private readonly int _hashCode; 

    public override bool Equals(object obj) 
    { 
     var other = (ByteArrayKey) obj; 
     return Compare(Bytes, other.Bytes); 
    } 

    public override int GetHashCode() 
    { 
     return _hashCode; 
    } 

    private static int GetHashCode([NotNull] byte[] bytes) 
    { 
     unchecked 
     { 
      var hash = 17; 
      for (var i = 0; i < bytes.Length; i++) 
      { 
       hash = hash*23 + bytes[i]; 
      } 
      return hash; 
     } 
    } 

    public ByteArrayKey(byte[] bytes) 
    { 
     Bytes = bytes; 
     _hashCode = GetHashCode(bytes); 
    } 

    public static ByteArrayKey Create(byte[] bytes) 
    { 
     return new ByteArrayKey(bytes); 
    } 

    public static unsafe bool Compare(byte[] a1, byte[] a2) 
    { 
     if (a1 == null || a2 == null || a1.Length != a2.Length) 
      return false; 
     fixed (byte* p1 = a1, p2 = a2) 
     { 
      byte* x1 = p1, x2 = p2; 
      var l = a1.Length; 
      for (var i = 0; i < l/8; i++, x1 += 8, x2 += 8) 
       if (*(long*) x1 != *(long*) x2) return false; 
      if ((l & 4) != 0) 
      { 
       if (*(int*) x1 != *(int*) x2) return false; 
       x1 += 4; 
       x2 += 4; 
      } 
      if ((l & 2) != 0) 
      { 
       if (*(short*) x1 != *(short*) x2) return false; 
       x1 += 2; 
       x2 += 2; 
      } 
      if ((l & 1) != 0) if (*x1 != *x2) return false; 
      return true; 
     } 
    } 
} 

Answer 1

MurmurHash довольно быстро и довольно просто. Существует ряд реализаций на основе .NET, но я точно не знаю, насколько они эффективны.

Answer 2

Лучший выбор для хэш может быть что-то вроде этого:

public override int GetHashCode(byte[] obj) 
{ 
    int hash = 0; 
    for (int i = 0; i < obj.Length; i++) 
    { 
     exponents = [0, 8, 16, 24]; 
     exponent = exponents[i % 4]; 

     unchecked 
     { 
      hash += obj[i] * (1 << i); 
     } 
    } 
    return hash; 
} 

Концептуально, это преобразует каждый блок из 4 байтов в междунар, так как 32 бита, а затем складывает их вместе со стандартным целым числом переполнение. Таким образом, все уникальные байтовые массивы длиной 4 или менее будут отображаться на разные хеш-коды и (учитывая случайные данные) большие массивы должны хорошо распределяться в хэш-пространстве. Если вы ожидаете множество очень похожих массивов или массивов, которые повторяются каждые 4 или что-то еще, это может быть не лучшая стратегия.