cuándo cambiar el tamaño de una tabla hash?

Question

En varias implementaciones de tablas hash, he visto "números mágicos" para cuando una tabla hash mutable debe cambiar de tamaño (crecer). Por lo general, este número está entre el 65% y el 80% de los valores agregados por ranuras asignadas. Estoy asumiendo que la compensación es que un número más alto dará la posibilidad de más colisiones y un número más bajo menos a expensas de usar más memoria.

Mi pregunta es ¿cómo se llega a este número?

¿Es arbitrario? basado en las pruebas? basado en alguna otra lógica?

Answer 1

En una conjetura, la mayoría de la gente al menos de inicio de los números en un libro (por ejemplo, Knuth, Volumen 3), que se produjeron mediante pruebas. Dependiendo de la situación, algunos pueden realizar pruebas posteriormente y hacer ajustes en consecuencia, pero por lo que he visto, probablemente sean una minoría.

Como describí en un previous answer, el número "correcto" también depende en gran medida de cómo resuelva las colisiones. Para bien o para mal, este hecho parece ser ampliamente ignorado: las personas con frecuencia no eligen los números que son particularmente apropiados para la resolución de colisión que utilizan.

OTOH, el otro punto que encontré en mi prueba es que rara vez hace una gran diferencia. Puede elegir números en un rango bastante amplio y obtener una velocidad general bastante similar. Lo principal es tener cuidado de evitar presionar el número demasiado alto, especialmente si está utilizando algo así como un sondeo lineal para la resolución de colisión.

Answer 2

Que yo sepa, el número es una heurística basada en pruebas empíricas.

Con una distribución razonablemente buena de los valores hash, parece que el factor de carga mágica es, como usted dice, generalmente alrededor del 70%. Un factor de carga más pequeño significa que está desperdiciando espacio sin ningún beneficio real; un factor de carga mayor significa que usará menos espacio, pero pasará más tiempo lidiando con colisiones hash.

(Por supuesto, si usted sabe que sus valores hash están perfectamente distribuidos entonces su factor de carga puede ser de 100% y todavía tendrá ningún espacio perdido y no hay colisiones hash.)

Answer 3

Eso depende de las teclas . Si sabe que su función hash es perfecta para todas las teclas posibles (por ejemplo, usando gperf), entonces sabrá que tendrá pocas colisiones, por lo que el número es mayor.

Pero la mayoría de las veces, usted no sabe mucho sobre las claves, excepto que son texto. En este caso, debes adivinar ya que ni siquiera tienes datos de prueba para descubrir de antemano cómo se comporta tu función hash.

Así que espera lo mejor. Si la función hash es muy mala para las teclas, entonces tendrás muchas colisiones y nunca alcanzarás el punto de crecimiento. En este caso, la cifra elegida es irrelevante.

Si su función hash es adecuada, entonces debería crear solo algunas colisiones (menos del 50%), por lo que un número entre 65% y 80% parece razonable.

Dicho esto: a menos que su tabla hash sea perfecta (= gran tamaño o muchos accesos), no se moleste. Si tiene, por ejemplo, diez elementos, considerar estos problemas es una pérdida de tiempo.

Answer 4

Las colisiones dependen en gran medida de los datos y utilizan la función hash.

La mayoría de los números se basan en la heurística o en suposiciones sobre la distribución normal de los valores hash. (valores que yo sepa cerca de 70% son típicos para las tablas hash extensibles, pero siempre se puede construir tal flujo de datos, que se obtiene mucho más menos colisiones /)

Answer 5

Creo que no quiere considerar "cuán completa" es la tabla (cuántos "cubos" del total de cubos tienen valores) sino el número de colisiones que podría llevar encontrar un lugar para un nuevo artículo .

Leí hace algunos años un libro de compilación (no puedo recordar el título o autores) que sugería el uso de listas vinculadas hasta que tuviera más de 10 a 12 elementos. Eso parece soportar más de 10 colisiones, significa tiempo para cambiar el tamaño.

The Design and Implementation of Dynamic. Hashing for Sets and Tables in Icon sugiere que una longitud de cadena de hash promedio de 5 (en ese algoritmo, el número promedio de colisiones) es suficiente para desencadenar una repetición. Parece respaldado por las pruebas, pero no estoy seguro de leer el documento correctamente.

Parece que la condición de cambio de tamaño es principalmente el resultado de las pruebas.