¿Es posible combinar códigos hash para miembros privados para generar un nuevo código hash?

Question

Tengo un objeto para el que quiero generar un hash único (anula 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 generar una clave de caché, por lo que idealmente deberían ser únicos, sin embargo la cantidad de valores posibles que se están reduciendo es pequeña, así que la probabilidad de THINK es a mi favor aquí.

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

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

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

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

Answer 1

Los fundamentos señalados por Marc y Jon son no está mal, pero están lejos de ser óptimos en términos de su distribución equitativa de los resultados. Lamentablemente, el enfoque de "multiplicar por primos" copiado por tanta gente de Knuth es not the best choice in many cases, se puede lograr una mejor distribución con funciones de cálculo más económicas (aunque esto es muy leve en hardware moderno). De hecho, lanzar primos en muchos aspectos de hash es no panacea.

Si esta información se utiliza para tablas hash de gran tamaño, recomiendo leer Bret Mulvey's excellent study and explanation of various modern (and not so modern) hashing techniques, hecho a mano con C#.

Tenga en cuenta que el comportamiento con cadenas de varias funciones hash es muy sesgado hacia wehther las cadenas son cortas (aproximadamente la cantidad de caracteres hashed antes de que los bits comiencen a fluir) o de largo.

Uno de los más simples y fáciles de implementar es también uno de los mejores, el hash de Jenkins One to 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); 
} 

a continuación, puede utilizar este modo:

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

se puede combinar varios tipos diferentes de este modo:

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 sólo tiene acceso al campo como un objeto con sin conocimiento de los aspectos internos, simplemente puede llamar a GetHashCode() en cada uno 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 se puede hacer sizeof (T) por lo que debe hacer cada estructura de forma individual.

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

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

Answer 2

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

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

Answer 3

los valores hash no son significaba que ser único - que sólo están destinados a ser bien distribuidos en la mayoría de las situaciones. Solo están destinados a ser consistentes. Tenga en cuenta que los desbordamientos no deberían ser un problema.

Solo agregar no es una buena idea en general, y dividir ciertamente no lo es. Aquí está el método que suelen utilizar:

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

Si eres de otro modo en un contexto marcado, es posible que desee hacer deliberadamente sin marcar.

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

Answer 4

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

hash ^= item.GetHashCode(); 

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

Si el orden es importante, en su lugar puede multiplicar por un número primo y agrega:.

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

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