¿Métodos de código hash adecuados para una matriz de bytes?

Question

¿Cuál es el mejor método hash para una matriz de byte?

Las matrices son objetos de clase serializados que contienen imágenes jpeg pasadas entre aplicaciones a través de TCP/IP.

El tamaño de la matriz es de aproximadamente 200k.

Answer 1

Cualquiera de las funciones hash incorporadas debería hacer; dependiendo de la cantidad que se preocupan por las colisiones estos son sus opciones (en la mayoría de las colisiones a menos):

• MD5
• SHA1
• SHA256
• SHA384
• SHA512

Ellos son tan simples de usar como:

var hash = SHA1.Create().ComputeHash(data); 

Marcas de bonificación: Si no te importa la seguridad (que no creo que hagas dado que estás obteniendo los valores hash para las imágenes) es posible que desees consultar Murmur hash, que está diseñado para hash de contenido y no hashing seguro (y por lo tanto es mucho más rápido). Sin embargo, no está en el marco, por lo que tendrá que encontrar una implementación (y probablemente debería optar por Murmur3).

Editar: Si usted está buscando un código hash para una matriz de bytes [] es totalmente de usted, por lo general consiste en el desplazamiento de bits (por números primos) y la operación XOR. P.ej.

public class ByteArrayEqualityComparer : IEqualityComparer<byte[]> 
{ 
    public static readonly ByteArrayEqualityComparer Default = new ByteArrayEqualityComparer(); 
    private ByteArrayEqualityComparer() { } 

    public bool Equals(byte[] x, byte[] y) 
    { 
     if (x == null && y == null) 
      return true; 
     if (x == null || y == null) 
      return false; 
     if (x.Length != y.Length) 
      return false; 
     for (var i = 0; i < x.Length; i++) 
      if (x[i] != y[i]) 
       return false; 
     return true; 
    } 

    public int GetHashCode(byte[] obj) 
    { 
     if (obj == null || obj.Length == 0) 
      return 0; 
     var hashCode = 0; 
     for (var i = 0; i < obj.Length; i++) 
      // Rotate by 3 bits and XOR the new value. 
      hashCode = (hashCode << 3) | (hashCode >> (29))^obj[i]; 
     return hashCode; 
    } 
} 
// ... 
var hc = ByteArrayEqualityComparer.Default.GetHashCode(data); 

EDIT: Si desea validar que el valor no ha cambiado usted debe utilizar CRC32.

Answer 2

Cualquiera de las cosas hash de cifrado debería funcionar. No estoy seguro de la velocidad. Tal vez MD5?

Answer 3

Sobre la base de la Compiler Generated GetHashCode()

public static int GetHashCode(byte[] array) { 
    unchecked { 
     int i = 0; 
     int hash = 17; 
     int rounded = array.Length & ~3; 

     hash = 31 * hash + array.Length; 

     for (; i < rounded; i += 4) { 
      hash = 31 * hash + BitConverter.ToInt32(array, i); 
     } 

     if (i < array.Length) { 
      int val = array[i]; 
      i++; 

      if (i < array.Length) { 
       val |= array[i] << 8; 
       i++; 

       if (i < array.Length) { 
        val |= array[i] << 16; 
       } 
      } 

      hash = 31 * hash + val; 
     } 

     return hash; 
    } 
} 

Ah ... y un enlace a C# Murmurhash http://landman-code.blogspot.com/2009/02/c-superfasthash-and-murmurhash2.html

Answer 4

Jon Skeet has a good answer sobre cómo anular GetHashCode, que se basa en técnicas de hash eficaces generales donde se empieza con una número primo, agréguelo a los códigos hash de los componentes multiplicados por otro número primo, permitiendo el desbordamiento.

Para su caso, se debe hacer:

static int GetByteArrayHashCode(byte[] array) 
{ 
    unchecked 
    { 
     int hash = 17; 

     // Cycle through each element in the array. 
     foreach (var value in array) 
     { 
      // Update the hash. 
      hash = hash * 23 + value.GetHashCode();    
     } 

     return hash; 
    } 
} 

nota en la respuesta de Jon va de por qué esto es mejor que XORing los hashes de los elementos individuales (y que los tipos anónimos en C# en la actualidad no XOR la hash de los elementos individuales, pero use algo similar a los anteriores).

Si bien esto será más rápido que los algoritmos hash del System.Security.Cryptography namespace (porque se trata de hash más pequeños), la desventaja es que es posible que tenga más colisiones.

Debería comprobar sus datos y determinar la frecuencia con la que se producen las colisiones en comparación con el trabajo que se debe realizar en caso de colisión.