Combinaciones rápidas y simples de código hash

¿Pueden las personas recomendar formas rápidas y simples de combinar los códigos hash de dos objetos? No estoy demasiado preocupado por las colisiones ya que tengo una Hash Table que manejará de manera eficiente. Solo quiero algo que genere un código lo más rápido posible.

Al leer SO y la web parece que hay algunos candidatos principales:

  1. XORing
  2. XORing con Prime Multiplication
  3. Operaciones numéricas simples como multiplicación / división (con control de desbordamiento o ajuste)
  4. Construyendo una Cadena y luego usando el método de Código Hash de clases de Cadena

¿Qué recomendaría la gente y por qué?

Yo personalmente evitaría XOR – significa que dos valores iguales darán como resultado 0 – entonces hash (1, 1) == hash (2, 2) == hash (3, 3) etc. También hash (5, 0) == hash (0, 5) etc. que pueden aparecer de vez en cuando. Lo he usado deliberadamente para establecer el hash: si quieres hacer una secuencia de elementos y no te importa el orden, es bueno.

Usualmente uso:

unchecked { int hash = 17; hash = hash * 31 + firstField.GetHashCode(); hash = hash * 31 + secondField.GetHashCode(); return hash; } 

Esa es la forma que Josh Bloch sugiere en Effective Java. La última vez que respondí una pregunta similar, logré encontrar un artículo donde se discutió en detalle: IIRC, nadie sabe realmente por qué funciona bien, pero lo hace. También es fácil de recordar, fácil de implementar y fácil de extender a cualquier cantidad de campos.

Si bien la plantilla descrita en la respuesta de Jon Skeet funciona bien en general como una familia de funciones hash, la elección de las constantes es importante y la similitud de 17 y el factor 31 como se indica en la respuesta no funcionan para casos de uso común. En la mayoría de los casos de uso, los valores hash están mucho más cerca de cero que int.MaxValue , y el número de elementos que se int.MaxValue conjuntamente es de unas pocas docenas o menos.

Para hash una tupla entera {x, y} donde -1000 <= x <= 1000 y -1000 <= y <= 1000 , tiene una tasa de colisión abismal de casi 98.5%. Por ejemplo, {1, 0} -> {0, 31} , {1, 1} -> {0, 32} , etc. Si ampliamos la cobertura también incluiremos n-tuplas donde 3 <= n <= 25 , lo hace menos terrible con una tasa de colisión de alrededor del 38%. Pero podemos hacerlo mucho mejor.

 public static int CustomHash(int seed, int factor, params int[] vals) { int hash = seed; foreach (int i in vals) { hash = (hash * factor) + i; } return hash; } 

Escribí un bucle de búsqueda de muestreo de Monte Carlo que probó el método anterior con varios valores para semilla y factor sobre varias n-tuplas aleatorias de enteros aleatorios i . Los rangos permitidos fueron 2 <= n <= 25 (donde n fue aleatorio pero sesgado hacia el extremo inferior del rango) y -1000 <= i <= 1000 . Se realizaron al menos 12 millones de pruebas de colisión únicas para cada par de semillas y factores.

Después de aproximadamente 7 horas seguidas, el mejor par encontrado (donde la semilla y el factor se limitaron a 4 dígitos o menos) fue: seed = 1009 , factor = 9176 , con una tasa de colisión de 0.1131%. En las áreas de 5 y 6 dígitos, existen mejores opciones. Pero seleccioné el intérprete superior de 4 dígitos por brevedad, y funciona bastante bien en todos los escenarios comunes de hash int y char . También parece funcionar bien con números enteros de magnitudes mucho mayores.

Vale la pena señalar que "ser primordial" no parecía ser un requisito previo general para un buen desempeño como una semilla y / o factor, aunque es probable que ayude. 1009 señalado anteriormente es de hecho primo, pero 9176 no lo es. Expliqué explícitamente las variaciones en este punto donde cambié el factor a varios números primos cerca de 9176 (dejando seed = 1009 ) y todos funcionaron peor que la solución anterior.

Por último, también comparé con la familia de función de recomendación ReSharper genérica de hash = (hash * factor) ^ i; y el CustomHash() original CustomHash() como se señaló anteriormente lo supera en gran medida. El estilo ReSharper XOR parece tener tasas de colisión en el rango de 20-30% para supuestos comunes de casos de uso y no debe usarse en mi opinión.