algorithm - son - tipos de funciones hash
¿Cómo probar una función hash? (4)
¿Hay alguna manera de probar la calidad de una función hash? Quiero tener una buena propagación cuando se usa en la tabla hash, y sería genial si esto se puede verificar en una prueba unitaria.
EDITAR : para aclarar, mi problema es que he utilizado valores long en Java de tal manera que los primeros 32 bits codificaron una ID y los segundos 32 bits codificaron otra ID. Desafortunadamente, el hash de valores largos de Java simplemente XORs los primeros 32 bits con los segundos 32 bits, lo que en mi caso condujo a un rendimiento muy pobre cuando se utiliza en un HashMap . Así que necesito un hash diferente, y me gustaría tener una prueba unitaria para que este problema no se pueda arrastrar más.
Si usas una tabla hash de encadenamiento, lo que realmente te importa es el número de colisiones. Esto sería trivial para implementar como un simple contador en su tabla hash. Cada vez que se inserta un artículo y la tabla tiene que encadenarse, incremente el contador de la cadena. Un mejor algoritmo hash dará como resultado un menor número de colisiones. Una buena función de hashing de tabla de propósito general para verificar es: djb2
Tienes que probar tu función hash usando datos extraídos de la misma distribución (o similar) en la que esperas que funcione. Cuando se buscan funciones hash en longitudes de 64 bits, la función hash predeterminada de Java es excelente si los valores de entrada se dibujan uniformemente de todos los valores largos posibles.
Sin embargo, mencionó que su aplicación usa el tiempo para almacenar esencialmente dos valores independientes de 32 bits. Intenta generar una muestra de valores similares a los que esperas usar realmente y luego prueba con eso.
Para la prueba en sí, tome sus valores de entrada de muestra, haga picadillo cada uno y coloque los resultados en un conjunto. Cuente el tamaño del conjunto resultante y compárelo con el tamaño del conjunto de entrada, y esto le indicará el número de colisiones que está generando su función hash.
Para su aplicación particular, en lugar de simplemente XORing juntos, intente combinar los valores de 32 bits de forma que una buena función de hash típica combine dos entradas de indepenet. Es decir, multiplicar por un primo y agregar.
En base a su aclaración:
He utilizado valores largos en Java de tal manera que los primeros 32 bits codificaron una ID y los segundos 32 bits codificaron otra ID. Desafortunadamente, el hash de valores largos de Java simplemente XORs los primeros 32 bits con los segundos 32 bits, lo que en mi caso condujo a un rendimiento muy pobre cuando se utiliza en un HashMap.
parece que tiene algunas "resonancias" infelices entre la forma en que asigna los dos valores de ID y los tamaños de las instancias de HashMap.
¿Estás dimensionando explícitamente tus mapas o usando los valores predeterminados? Una comprobación de QAD parece indicar que un HashMap<Long,String> comienza con una estructura de 16 segmentos y se duplica al desbordamiento. Eso significaría que solo los bits de bajo orden de los valores de ID están realmente participando en la selección del cubo de hash. Podría intentar usar uno de los constructores que toma un parámetro de tamaño inicial y crear sus mapas con un tamaño inicial principal.
Alternativamente, la sugerencia de Dave L de definir su propio hash de claves largas le permitiría evitar el problema de dependencia de poco bit.
Otra forma de ver esto es que está utilizando un tipo primitivo (largo) como una forma de evitar definir una clase real. Sugiero que analice los beneficios que podría lograr definiendo las clases de negocios y luego implementando codificación hash, igualdad y otros métodos según corresponda en sus propias clases para manejar este problema.
Primero, creo que debes definir lo que quieres decir con una buena propagación para ti mismo. ¿Quiere decir una buena propagación para todas las entradas posibles, o simplemente una buena propagación para la entrada probable?
Por ejemplo, si está mezclando cadenas que representan los nombres propios completos (primeros y últimos), probablemente no le importe cómo se combinan las cosas con los caracteres numéricos ASCII.
En cuanto a las pruebas, la mejor opción es obtener un conjunto de datos de entrada enorme o aleatorio que esperas, y pasarlo a través de la función hash y ver cómo termina el spread. No es probable que haya un programa mágico que pueda decir "Sí, esta es una buena función hash para su caso de uso". Sin embargo, si puede generar programáticamente los datos de entrada, debe ser capaz de crear fácilmente una prueba de unidad que genere una cantidad significativa de ella y luego verificar que la dispersión se encuentre dentro de su definición de buena.
Editar: En su caso, con un bit de 64 bits, ¿existe realmente alguna razón para usar un mapa hash? ¿Por qué no simplemente usar un árbol equilibrado directamente, y utilizar el largo como la clave directamente en lugar de volver a generar el mismo? Usted paga una pequeña penalización en el tamaño total del nodo (2 veces el tamaño del valor clave), pero puede terminar guardándolo en rendimiento.