¿Cómo puedo generar un código hash a partir de una matriz de bytes en C#?

Question

Digamos que tengo un objeto que almacena una matriz de bytes y quiero poder generar un hashcode de manera eficiente. He usado las funciones hash criptográficas para esto en el pasado porque son fáciles de implementar, pero están haciendo mucho más trabajo de lo que deberían para ser criptográficamente de una sola dirección, y eso no me importa (solo estoy usando el hashcode como clave en una tabla hash).

Esto es lo que tengo hoy:

struct SomeData : IEquatable<SomeData> 
{ 
    private readonly byte[] data; 
    public SomeData(byte[] data) 
    { 
     if (null == data || data.Length <= 0) 
     { 
      throw new ArgumentException("data"); 
     } 
     this.data = new byte[data.Length]; 
     Array.Copy(data, this.data, data.Length); 
    } 

    public override bool Equals(object obj) 
    { 
     return obj is SomeData && Equals((SomeData)obj); 
    } 

    public bool Equals(SomeData other) 
    { 
     if (other.data.Length != data.Length) 
     { 
      return false; 
     } 
     for (int i = 0; i < data.Length; ++i) 
     { 
      if (data[i] != other.data[i]) 
      { 
       return false; 
      } 
     } 
     return true; 
    } 
    public override int GetHashCode() 
    { 
     return BitConverter.ToInt32(new MD5CryptoServiceProvider().ComputeHash(data), 0); 
    } 
} 

¿Alguna idea?

---

dp: Tienes razón en que perdí un cheque en Equals, lo he actualizado. El uso del código hash existente de la matriz de bytes dará como resultado la igualdad de referencia (o al menos ese mismo concepto traducido a hashcodes). por ejemplo:

byte[] b1 = new byte[] { 1 }; 
byte[] b2 = new byte[] { 1 }; 
int h1 = b1.GetHashCode(); 
int h2 = b2.GetHashCode(); 

Con ese código, a pesar de las dos matrices de bytes que tienen los mismos valores dentro de ellos, se refieren a diferentes partes de la memoria y dará lugar a (probablemente) diferentes códigos hash. Necesito los códigos hash para dos matrices de bytes con los mismos contenidos para ser iguales.

Answer 1

Si está buscando un rendimiento, probé algunas teclas hash, y Recomiendo Bob Jenkin's hash function. Es tan loco rápido para calcular y dará tan pocas colisiones como el hash criptográfico que has usado hasta ahora.

No sé C# en absoluto, y no sé si se puede vincular con C, pero aquí es its implementation in C.

Answer 2

El código hash de un objeto no necesita ser único.

La regla de verificación es:

• son los códigos hash iguales? Luego llame al método completo (lento) Equals.
• ¿Los códigos hash no son iguales? Entonces los dos elementos definitivamente no son iguales.

Todo lo que quieres es un algoritmo de GetHashCode que divide su colección en más o menos incluso grupos - no debe formar la clave como el HashTable o Dictionary<> tendrá que utilizar el hash para optimizar la recuperación.

¿Cuánto tiempo espera que sean los datos? ¿Qué tan aleatorio? Si las longitudes varían mucho (por ejemplo, para los archivos), simplemente devuelva la longitud. Si es probable que las longitudes sean similares, observe un subconjunto de bytes que varía.

GetHashCode debe ser mucho más rápido que Equals, pero no necesita ser único.

Dos cosas idénticas nunca deben tener tienen diferentes códigos hash. Dos objetos diferentes no deberían tener con el mismo código hash, pero se esperan algunas colisiones (después de todo, hay más permutaciones que posibles enteros de 32 bits).

Answer 3

¿No es suficiente usar el hashcode existente del campo de matriz de bytes?También tenga en cuenta que en el método Equals debe verificar que las matrices tengan el mismo tamaño antes de hacer la comparación.

Answer 4

Generar un buen hash es más fácil decirlo que hacerlo. Recuerde, básicamente representa n bytes de datos con m bits de información. Cuanto mayor sea el conjunto de datos y menor sea m, más probabilidades habrá de que se produzca una colisión ... dos datos que se resuelven en el mismo hash.

El hash más simple que he aprendido es simplemente XORing todos los bytes juntos. Es fácil, más rápido que la mayoría de los algoritmos de hash complicados y un algoritmo de hash de propósito general medio decente para pequeños conjuntos de datos. Es el tipo de burbuja de los algoritmos hash realmente. Dado que la implementación simple te dejaría con 8 bits, eso es solo 256 hashes ... no tan calientes. Podría hacer fragmentos XOR en lugar de bytes individuales, pero luego el algoritmo se vuelve mucho más complicado.

Por lo tanto, los algoritmos criptográficos tal vez están haciendo algunas cosas que no necesita ... pero también son un gran paso en la calidad de hash de uso general. El hash MD5 que está utilizando tiene 128 bits, con miles de millones y miles de hashes posibles. La única forma en que es probable que obtenga algo mejor es tomar algunas muestras representativas de los datos que espera encontrar en su aplicación y probar varios algoritmos para ver cuántas colisiones obtiene.

Así que hasta que vea alguna razón para no usar un algoritmo de hash enlatado (¿rendimiento, quizás?), Voy a tener que recomendar que se quede con lo que tiene.

Answer 5

¿Ha comparado con el método SHA1CryptoServiceProvider.ComputeHash? Se necesita una matriz de bytes y devuelve un hash SHA1, y creo que está bastante bien optimizado. Lo usé en un Identicon Handler que funcionó bastante bien bajo carga.

Answer 6

RuntimeHelpers.GetHashCode pueden ayudar:

partir de MSDN:

Sirve como función hash para un tipo particular , adecuado para su uso en algoritmos hash y estructuras de datos como una tabla hash.

Answer 7

Tanto si quieres un hashfunction perfecto (valor diferente para cada objeto que se evalúa como iguales) o simplemente una muy buena es siempre un equilibrio del rendimiento, se necesita normalmente tiempo para calcular una buena hashfunction y si el conjunto de datos es pequeña es mejor con una función rápida. Lo más importante (como señala su segunda publicación) es la corrección, y para lograr eso, todo lo que necesita es devolver la longitud de la matriz. Dependiendo de su conjunto de datos que incluso podría estar bien. Si no lo es (digamos que todas sus matrices son igualmente largas) puede ir con algo barato como mirar el primer y último valor y XORing sus valores y luego agregar más complejidad como mejor le parezca a sus datos.

Una manera rápida de ver cómo funciona su función en sus datos es agregar todos los datos a una tabla hash y contar el número de veces que se llama a la función Equals, si es demasiado seguido tiene más trabajo que hacer en el función. Si hace esto, tenga en cuenta que el tamaño del hashtable debe establecerse más grande que su conjunto de datos cuando comience; de ​​lo contrario, volverá a generar los datos que desencadenarán reinserts y más evaluaciones iguales (aunque posiblemente sean más realistas)

Para algunos objetos (no este), ToString() puede generar un HashCode rápido.GetHashCode(), ciertamente no es óptimo, pero es útil ya que las personas tienden a devolver algo parecido a la identidad del objeto de ToString() y eso es exactamente lo que GetHashcode está buscando

Trivia: El peor rendimiento que he visto fue cuando a alguien por error volvió una constante de GetHashCode, fácil de detectar con un depurador sin embargo, especialmente si lo hace un montón de búsquedas en su tabla hash

Answer 8

préstamos del código generado por el software de JetBrains, he asentado en esta función:

public override int GetHashCode() 
    { 
     unchecked 
     { 
      var result = 0; 
      foreach (byte b in _key) 
       result = (result*31)^b; 
      return result; 
     } 
    } 

El problema con solo XOring los bytes es que 3/4 (3 bytes) de th El valor devuelto tiene solo 2 valores posibles (todo encendido o todo apagado). Esto extiende los bits un poco más.

Establecer un punto de interrupción en Equals fue una buena sugerencia. Al agregar unas 200,000 entradas de mis datos a un diccionario, veo aproximadamente 10 llamadas equivalentes (o 1/20,000).

Answer 9

No utilice hashes criptográficos para una tabla hash, eso es ridículo/excesivo.

Aquí ya go ... Modificado FNV hash en C#

http://bretm.home.comcast.net/hash/6.html

public static int ComputeHash(params byte[] data) 
    { 
     unchecked 
     { 
      const int p = 16777619; 
      int hash = (int)2166136261; 

      for (int i = 0; i < data.Length; i++) 
       hash = (hash^data[i]) * p; 

      hash += hash << 13; 
      hash ^= hash >> 7; 
      hash += hash << 3; 
      hash ^= hash >> 17; 
      hash += hash << 5; 
      return hash; 
     } 
    } 

Answer 10

He encontrado resultados interesantes:

que tienen la clase:

public class MyHash : IEquatable<MyHash> 
{   
    public byte[] Val { get; private set; } 

    public MyHash(byte[] val) 
    { 
     Val = val; 
    } 

    /// <summary> 
    /// Test if this Class is equal to another class 
    /// </summary> 
    /// <param name="other"></param> 
    /// <returns></returns> 
    public bool Equals(MyHash other) 
    { 
     if (other.Val.Length == this.Val.Length) 
     { 
      for (var i = 0; i < this.Val.Length; i++) 
      { 
       if (other.Val[i] != this.Val[i]) 
       { 
        return false; 
       } 
      } 

      return true; 
     } 
     else 
     { 
      return false; 
     }    
    } 

    public override int GetHashCode() 
    {    
     var str = Convert.ToBase64String(Val); 
     return str.GetHashCode();   
    } 
} 

Entonces creó un diccionario con las teclas de tipo MyHash para probar qué tan rápido puedo nsert y también puedo saber cuántas colisiones hay. Hice la siguiente

 // dictionary we use to check for collisions 
     Dictionary<MyHash, bool> checkForDuplicatesDic = new Dictionary<MyHash, bool>(); 

     // used to generate random arrays 
     Random rand = new Random(); 



     var now = DateTime.Now; 

     for (var j = 0; j < 100; j++) 
     { 
      for (var i = 0; i < 5000; i++) 
      { 
       // create new array and populate it with random bytes 
       byte[] randBytes = new byte[byte.MaxValue]; 
       rand.NextBytes(randBytes); 

       MyHash h = new MyHash(randBytes); 

       if (checkForDuplicatesDic.ContainsKey(h)) 
       { 
        Console.WriteLine("Duplicate"); 
       } 
       else 
       { 
        checkForDuplicatesDic[h] = true; 
       } 
      } 
      Console.WriteLine(j); 
      checkForDuplicatesDic.Clear(); // clear dictionary every 5000 iterations 
     } 

     var elapsed = DateTime.Now - now; 

     Console.Read(); 

Cada vez que se inserta un nuevo elemento al diccionario el diccionario calculará el hash de ese objeto. Por lo tanto se puede decir qué método es más eficiente mediante la colocación de varias respuestas que se encuentran aquí en el método public override int GetHashCode() El método que era, con mucho, el más rápido y tenía el menor número de colisiones fue:

public override int GetHashCode() 
    {    
     var str = Convert.ToBase64String(Val); 
     return str.GetHashCode();   
    } 

que tomó 2 segundos para ejecutar . El método

public override int GetHashCode() 
    { 
     // 7.1 seconds 
     unchecked 
     { 
      const int p = 16777619; 
      int hash = (int)2166136261; 

      for (int i = 0; i < Val.Length; i++) 
       hash = (hash^Val[i]) * p; 

      hash += hash << 13; 
      hash ^= hash >> 7; 
      hash += hash << 3; 
      hash ^= hash >> 17; 
      hash += hash << 5; 
      return hash; 
     } 
    } 

tenía ninguna colisión también pero tardó 7 segundos para ejecutar!

Answer 11

private int? hashCode; 

public override int GetHashCode() 
{ 
    if (!hashCode.HasValue) 
    { 
     var hash = 0; 
     for (var i = 0; i < bytes.Length; i++) 
     { 
      hash = (hash << 4) + bytes[i]; 
     } 
     hashCode = hash; 
    } 
    return hashCode.Value; 
}