funcion - sha256cryptoserviceprovider c# example

¿Cómo puedo generar un hashcode de una matriz de bytes en C#?

Question

Supongamos que tengo un objeto que almacena una matriz de bytes y quiero poder generar de manera eficiente un código de hash para ella. 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 me 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 que las dos matrices de bytes tienen los mismos valores, se están refiriendo a diferentes partes de la memoria y darán como resultado (probablemente) diferentes códigos hash. Necesito los códigos hash para dos matrices de bytes con los mismos contenidos para ser iguales.

Answer 1

¿El uso del código hash existente del campo de matriz de bytes no es lo suficientemente bueno? 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 2

¿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 manejador de Identicon que funcionaba bastante bien bajo carga.

Answer 3

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 desea es un algoritmo GetHashCode que divida su colección en grupos aproximadamente uniformes; no debe formar la clave ya que HashTable o Dictionary<> necesitarán usar 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 diferentes códigos hash. Dos objetos diferentes no deben tener 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 4

Encontré resultados interesantes:

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

Luego creé un diccionario con las teclas de tipo MyHash para probar qué tan rápido puedo insertar y también puedo saber cuántas colisiones hay. Hice lo 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 inserte un nuevo elemento en el diccionario, el diccionario calculará el hash de ese objeto. Para que pueda decir qué método es el más eficiente al colocar varias respuestas encontradas aquí en el método public override int GetHashCode() El método que fue con mucho el más rápido y tuvo el menor número de colisiones fue:

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

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

no tuvo colisiones también pero tardó 7 segundos en ejecutarse!

Answer 5

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 era 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 necesitas ... 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.

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

Answer 6

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

Aquí ya ve ... Hash FNV modificado 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 7

Si buscas rendimiento, probé algunas teclas hash, y recomiendo la función hash de Bob Jenkin . Es increíblemente rápido de computar y dará tan pocas colisiones como el hash criptográfico que usaste hasta ahora.

No sé C # en absoluto, y no sé si se puede vincular con C, pero aquí está su implementación en C.

Answer 8

Si desea una función de hash perfecta (valor diferente para cada objeto que equivale a igual) o simplemente una bastante buena es siempre una compensación de rendimiento, normalmente se necesita tiempo para calcular una buena función de hash y si su conjunto de datos es más bien pequeño, 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 forma rápida de ver cómo se desempeña 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 con demasiada frecuencia tiene más trabajo por hacer en la 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) se puede generar un HashCode rápido por ToString (). GetHashCode (), ciertamente no es óptimo, pero es útil ya que las personas tienden a devolver algo cercano 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 alguien por error devolvió una constante de GetHashCode, fácil de detectar con un depurador, especialmente si haces muchas búsquedas en tu hashtable

Answer 9

Tomando prestado del código generado por el software JetBrains, me he decidido por 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) del 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 10

RuntimeHelpers.GetHashCode podría ayudar:

De Msdn:

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

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