¿Cómo debo optimizar una tabla hash para una población determinada?

Question

Supongamos que tengo una población de pares clave-valor que planeo almacenar en una tabla hash. La población es fija y nunca cambiará. ¿Qué optimizaciones tengo disponibles para hacer la tabla hash lo más rápido posible? ¿En qué optimizaciones debería concentrarme? Esto es asumiendo que tengo mucho espacio. Habrá un número razonable de pares (digamos no más de 100,000).

EDIT: Quiero optimizar la búsqueda. No me importa cuánto tiempo lleve construir.

Answer 1

Me aseguraría de que el valor hash de su clave tenga valores únicos. Esto asegurará que cada búsqueda sea constante y, por lo tanto, lo más rápido posible.

Como nunca puede tener más de 100.000 claves, es posible tener 100 000 valores hash.

Además, asegúrese de utilizar el constructor que toma un int para especificar la capacidad inicial (configúrelo en 100.000) y un flotante para establecer el factor de carga. (Use 1) Además, hacer esto requiere que tenga una función hash perfecta para sus teclas. Pero esto dará como resultado la búsqueda más rápida posible, en la menor cantidad de memoria.

Answer 2

Asegúrese de que no haya colisiones. Si no hay colisiones, se le garantiza O (1) tiempo de búsqueda constante. La próxima optimización sería la búsqueda.

Utilice un perfilador para optimizar pieza por pieza. Es difícil sin eso.

Answer 3

La optimización se debe realizar en el método hashCode de la clave class. Lo que hay que tener en cuenta es implementar este método para evitar colisiones.

Answer 4

En general, para optimizar una tabla hash, desea minimizar las colisiones en la determinación de su hash, por lo que sus cubos no contendrán más de un elemento y la búsqueda hash volverá inmediatamente.

La mayoría de las veces, eso significa que debe medir la salida de su función hash en el espacio problemático. Así que supongo que recomendaría investigar eso

Answer 5

Si es posible hacer una tabla hash grande de modo que no haya colisiones en absoluto, será ideal. Dado que sus inserciones y búsquedas se realizarán en tiempo constante.

Pero si eso no es posible, intente elegir una función hash para que sus claves se distribuyan uniformemente en la tabla hash.

Answer 6

Perfect hashing algorithms frente al problema, pero no puede escalar a 100k objetos. Encontré un Java MPH package, pero no lo he probado.

Answer 7

Si se conoce la población en tiempo de compilación, la solución óptima es utilizar una función hash perfecta mínima (MPH). El Wikipedia page sobre este tema enlaza con varias herramientas Java que pueden generar estos.

Answer 8

Obtener el algoritmo hash perfecto para dar valores totalmente únicos a los objetos 100K es probable que sea casi imposible. Considera la paradoja del cumpleaños. La fecha en que nacen las personas se puede considerar un algoritmo de hash perfecto, sin embargo, si tienes más de 23 personas, es más que probable que tengas una colisión, y eso está en una tabla de 365 fechas.

¿Qué tamaño de mesa necesitará para evitar colisiones en 100K?

Si sus claves son cadenas, su estrategia óptima es un árbol, no binario, sino una rama en cada carácter. Si las teclas están en minúsculas, es más fácil ya que solo necesita 26 cada vez que crea una rama.

Comenzamos con 26 teclas. Siga el primer carácter, digamos f f puede tener un valor asociado. Y puede tener subárboles. Busque un subárbol de o. Esto lleva a más subárboles y luego busca el siguiente o. (¡Sabías a dónde conducía eso!). Si esto no tiene un valor asociado, o golpeamos un subárbol nulo en el camino, sabemos que no se encuentra el valor.

Puede optimizar el espacio en el árbol donde alcanza un punto de singularidad. Digamos que tiene una clave de enero y se convierte en único en el cuarto personaje. En este punto donde asigna el valor, también almacena la cadena real asociada con él. En nuestro ejemplo, puede haber un valor asociado con foo pero la clave con la que se relaciona puede ser comida, no foo.

Creo que los motores de búsqueda de Google utilizan una técnica similar a esta.

Answer 9

La pregunta clave es cuál es su clave. (Sin juego de palabras.) Como han señalado otros, el objetivo es minimizar el número de colisiones hash. Si puede obtener el número de colisiones hash a cero, es decir, su función hash genera un valor único para cada clave que realmente le pase, tendrá un hash perfecto.

Tenga en cuenta que en Java, una función hash realmente tiene dos pasos: Primero la clave se ejecuta a través de la función hashCode para su clase. Luego calculamos un valor de índice en la tabla hash tomando este módulo de valor del tamaño de la tabla hash.

Creo que las personas que debaten sobre la función hash perfecta tienden a olvidar ese segundo paso. Incluso si escribiera una función hashCode que generara un valor único para cada clave que se le pasara, aún podría obtener un hash absolutamente terrible si este módulo de valor, el tamaño de la tabla hash, no es exclusivo. Por ejemplo, digamos que tiene 100 claves y su función hashCode devuelve los valores 1, 1001, 2001, 3001, 4001, 5001, ... 99001. Si su tabla hash tiene 100,000 ranuras, este sería un hash perfecto. Cada tecla tiene su propia ranura. Pero si tiene 1000 máquinas tragamonedas, todas se desplazan a la misma ranura. Sería el peor hash posible.

Considere la posibilidad de construir una buena función hash. Tome los casos extremos. Supongamos que tu clave es una cita. Usted sabe que las fechas serán todas en enero del mismo año. Luego, use el día del mes ya que el valor hash debe ser tan bueno como lo que va a obtener: todo se reducirá a un entero único en un rango pequeño. Por otro lado, si sus fechas fueron todas el primero del mes durante muchos años y muchos meses, tomar el día del mes sería un hash terrible, ya que cada tecla real se correlacionaría con "1".

Mi punto es que si realmente quiere optimizar su hash, necesita conocer la naturaleza de sus datos. ¿Cuál es el rango real de valores que obtendrá?