c# - tipos - tablas hash

¿Es posible combinar códigos hash para que los miembros privados generen un nuevo código hash?

Question

Tengo un objeto para el que quiero generar un hash único (anular GetHashCode ()) pero quiero evitar desbordamientos o algo impredecible.

El código debe ser el resultado de combinar los códigos hash de una pequeña colección de cadenas.

Los códigos hash serán parte de la generación de una clave de caché, por lo que idealmente deberían ser únicos, sin embargo, el número de valores posibles que se están procesando es pequeño, por lo que creo que la probabilidad está a mi favor aquí.

¿Sería algo como esto suficiente Y hay una mejor manera de hacer esto?

int hash = 0;
foreach(string item in collection){
hash += (item.GetHashCode() / collection.Count)
}
return hash;

EDIT: Gracias por las respuestas hasta ahora. @Jon Skeet: No, el orden no es importante

Supongo que esta es otra pregunta, pero ya que estoy usando el resultado para generar una clave de caché (cadena), ¿tendría sentido usar una función de hash criptográfica como MD5 o simplemente usar la representación de cadena de este int?

Answer 1

Los fundamentos señalados por Marc y Jon no son malos, pero distan mucho de ser óptimos en términos de su uniformidad en la distribución de los resultados. Lamentablemente, el enfoque de ''multiplicar por números primos'' copiado por tanta gente de Knuth no es la mejor opción, en muchos casos se puede lograr una mejor distribución con funciones de cálculo más baratas (aunque esto es muy leve en el hardware moderno). De hecho, lanzar primos en muchos aspectos del hash no es una panacea .

Si se usan estos datos para tablas hash de tamaño significativo, recomiendo leer el excelente estudio de Bret Mulvey y la explicación de varias técnicas de hashing modernas (y no tan modernas) hechas fácilmente con c #.

Tenga en cuenta que el comportamiento con cadenas de varias funciones hash está muy inclinado hacia las demás cadenas cortas (en términos generales, cuántos caracteres se hashean antes de que los bits comiencen a desbordarse) o largos.

Uno de los más sencillos y fáciles de implementar es también uno de los mejores, el hash Jenkins One at a time.

private static unsafe void Hash(byte* d, int len, ref uint h)
{
for (int i = 0; i < len; i++)
{
h += d[i];
h += (h << 10);
h ^= (h >> 6);
}
}
public unsafe static void Hash(ref uint h, string s)
{
fixed (char* c = s)
{
byte* b = (byte*)(void*)c;
Hash(b, s.Length * 2, ref h);
}
}
public unsafe static int Avalanche(uint h)
{
h += (h<< 3);
h ^= (h>> 11);
h += (h<< 15);
return *((int*)(void*)&h);
}

entonces puedes usar esto asi

uint h = 0;
foreach(string item in collection)
{
Hash(ref h, item);
}
return Avalanche(h);

Puedes fusionar múltiples tipos diferentes de esta manera:

public unsafe static void Hash(ref uint h, int data)
{
byte* d = (byte*)(void*)&data;
AddToHash(d, sizeof(int), ref h);
}
public unsafe static void Hash(ref uint h, long data)
{
byte* d= (byte*)(void*)&data;
Hash(d, sizeof(long), ref h);
}

Si solo tiene acceso al campo como un objeto sin conocimiento de las partes internas, simplemente puede llamar a GetHashCode () en cada una y combinar ese valor de la siguiente manera:

uint h = 0;
foreach(var item in collection)
{
Hash(ref h, item.GetHashCode());
}
return Avalanche(h);

Lamentablemente, no puede hacer sizeof (T), por lo que debe hacer cada estructura individualmente.

Si desea utilizar la reflexión, puede construir en función de cada tipo una función que haga identidad estructural y hash en todos los campos.

Si desea evitar el código inseguro, puede utilizar técnicas de enmascaramiento de bits para extraer bits individuales de caracteres (y caracteres si se trata de cadenas) sin demasiada molestia.

Answer 2

Los hash no deben ser únicos, solo deben estar bien distribuidos en la mayoría de las situaciones. Sólo están destinados a ser consistentes. Tenga en cuenta que los desbordamientos no deberían ser un problema.

Simplemente agregar no es generalmente una buena idea, y dividir ciertamente no lo es. Aquí está el enfoque que suelo usar:

int result = 17;
foreach (string item in collection)
{
result = result * 31 + item.GetHashCode();
}
return result;

Si, de lo contrario, se encuentra en un contexto marcado, es posible que desee hacerlo deliberadamente sin marcar.

Tenga en cuenta que esto supone que el orden es importante, es decir, que {"a", "b"} debe ser diferente de {"b", "a"}. Por favor, háganos saber si ese no es el caso.

Answer 3

No hay nada de malo en este enfoque, siempre y cuando los miembros cuyos hashcodes estén combinando sigan las reglas de los hash. En breve ...

1. El código hash de los miembros privados no debe cambiar durante la vida útil del objeto
2. El contenedor no debe cambiar el objeto que los miembros privados apuntan para que, a su vez, no cambie el código hash del contenedor

Answer 4

Si el orden de los elementos no es importante (es decir, {"a", "b"} es el mismo que {"b", "a"}), entonces puede usar exclusivos o para combinar los códigos hash:

hash ^= item.GetHashCode();

[Editar: Como Mark señaló en un comentario a una respuesta diferente, esto tiene el inconveniente de que también proporciona colecciones como {"a"} y {"a", "b", "b"} el mismo código hash.]

Si el orden es importante, puede multiplicar por un número primo y agregar:

hash *= 11;
hash += item.GetHashCode();

(Cuando multiplicas, a veces obtendrás un desbordamiento que se ignora, pero al multiplicar con un número primo, perderás un mínimo de información. Si en lugar de multiplicarte con un número como 16, perderías cuatro bits de información cada vez, así que después ocho elementos el código hash del primer elemento desaparecería por completo.)