algorithm - utilizacion - ¿Por qué las expansiones de la tabla hash generalmente se hacen duplicando el tamaño?

utilizacion de tablas hash (6)

Duplicar la memoria al expandir cualquier tipo de colección es una estrategia utilizada a menudo para evitar la fragmentación de la memoria y no tener que reasignar con demasiada frecuencia. Como usted señala, puede haber razones para tener un número primo de elementos. Al conocer su aplicación y sus datos, también puede predecir el crecimiento de la cantidad de elementos y así elegir otro factor de crecimiento (más grande o más pequeño) que duplicar.

Las implementaciones generales que se encuentran en las bibliotecas son exactamente eso: implementaciones generales. Deben enfocarse en ser una opción razonable en una variedad de situaciones diferentes. Al conocer el contexto, casi siempre es posible escribir una implementación más especializada y más eficiente.

He investigado un poco sobre tablas hash, y sigo corriendo la regla general de que cuando hay un cierto número de entradas (ya sea como máximo o por un factor de carga como 75%), la tabla hash debe expandirse.

Casi siempre, la recomendación es duplicar (o duplicar más 1, es decir, 2n + 1) el tamaño de la tabla hash. Sin embargo, no he podido encontrar una buena razón para esto.

¿Por qué doblar el tamaño, en lugar de, digamos, aumentarlo un 25% o aumentarlo al tamaño del siguiente número primo o los próximos k números primos (por ejemplo, tres)?

Ya sé que a menudo es una buena idea elegir un tamaño de tabla hash inicial que sea un número primo, al menos si su función hash usa un módulo como hashing universal. Y sé que es por eso que generalmente se recomienda hacer 2n + 1 en lugar de 2n (por ejemplo, http://www.concentric.net/~Ttwang/tech/hashsize.htm )

Sin embargo, como dije, no he visto ninguna explicación real de por qué doblar o doblar más uno es en realidad una buena opción en lugar de algún otro método para elegir un tamaño para la nueva tabla hash.

(Y sí, he leído el artículo de Wikipedia sobre tablas hash :) http://en.wikipedia.org/wiki/Hash_table

El mismo razonamiento se aplica para duplicar el tamaño en cuanto a las implementaciones vector / ArrayList, vea esta respuesta .

Había leído una discusión muy interesante sobre la estrategia de crecimiento en este mismo sitio ... simplemente no puedo encontrarlo de nuevo.

Mientras que 2 se usa comúnmente, se ha demostrado que no era el mejor valor. Un problema que se cita a menudo es que no encaja bien con los esquemas de asignación (que a menudo asignan potencia de dos bloques) ya que siempre requeriría una reasignación mientras que un número más pequeño podría ser reasignado en el mismo bloque (simulando crecimiento en el lugar) y así ser más rápido.

Así, por ejemplo, la Biblioteca Estándar de VC++ usa un factor de crecimiento de 1.5 (idealmente debería ser el número de oro si se usa una estrategia de asignación de memoria de primer ajuste) después de una amplia discusión en la lista de correo. El razonamiento se explica here :

Me interesaría si cualquier otra implementación de vectores usa un factor de crecimiento distinto de 2, y también me gustaría saber si VC7 usa 1.5 o 2 (ya que no tengo ese compilador aquí).
Existe una razón técnica para preferir 1.5 a 2, más específicamente, para preferir valores menores a 1+sqrt(5)/2 .
Supongamos que está utilizando un asignador de memoria de primer ajuste y se está agregando progresivamente a un vector. Luego, cada vez que reasignas, asignas nueva memoria, copias los elementos y luego liberas la memoria anterior. Eso deja un espacio, y sería bueno poder usar esa memoria eventualmente. Si el vector crece demasiado rápido, siempre será demasiado grande para la memoria disponible.
Resulta que si el factor de crecimiento es >= 1+sqrt(5)/2 , la nueva memoria siempre será demasiado grande para el agujero que se ha dejado sofar; si es < 1+sqrt(5)/2 , la nueva memoria eventualmente encajará. Entonces 1.5 es lo suficientemente pequeño como para permitir que la memoria sea reciclada.
Sin duda, si el factor de crecimiento es >= 2 la nueva memoria siempre será demasiado grande para el agujero que se ha dejado hasta ahora; si es < 2 , la nueva memoria eventualmente encajará. Presumiblemente, la razón de (1+sqrt(5))/2 es ...
La asignación inicial es s .
El primer cambio de tamaño es k*s .
El segundo cambio de tamaño es k*k*s , que se ajustará al agujero iff k*k*s <= k*s+s , es decir, iff k <= (1+sqrt(5))/2
... el agujero se puede reciclar lo antes posible.
Podría, al almacenar su tamaño anterior, crecer fibonaccily.

Por supuesto, debe adaptarse a la estrategia de asignación de memoria.

Si no sabe cuántos objetos va a terminar usando (digamos N),
al duplicar el espacio, deberás registrar reasignaciones de ₂ N como máximo.

Supongo que si eliges una "n" inicial adecuada , aumentas las probabilidades
que 2 * n + 1 producirá números primos en subsecuentes reasignaciones.

Una razón para duplicar el tamaño que es específico de los contenedores hash es que si la capacidad del contenedor es siempre una potencia de dos, en lugar de usar un módulo de propósito general para convertir un hash a un offset, se puede lograr el mismo resultado con el cambio de bit. Modulo es una operación lenta por las mismas razones que la división entera es lenta. (Si la división de enteros es "lenta" en el contexto de cualquier otra cosa que esté sucediendo en un programa, por supuesto, depende de cada caso, pero es ciertamente más lenta que otras aritméticas enteras básicas).

Hash-tables no podría reclamar "inserción de tiempo constante amortizada" si, por ejemplo, el cambio de tamaño se realizó por un incremento constante. En ese caso, el costo de cambiar el tamaño (que crece con el tamaño de la tabla hash) haría que el costo de una inserción sea lineal en el número total de elementos que se insertarán. Debido a que el cambio de tamaño se vuelve cada vez más costoso con el tamaño de la tabla, tiene que suceder "cada vez menos" para mantener el costo amortizado de la inserción constante.

La mayoría de las implementaciones permiten que la ocupación de cubeta promedio crezca hasta un límite fijo por adelantado antes de cambiar el tamaño (en cualquier lugar entre 0,5 y 3, que son todos valores aceptables). Con esta convención, justo después del redimensionamiento, la ocupación promedio de cubos se convierte en la mitad de ese límite. El cambio de tamaño al duplicar mantiene la ocupación promedio del cucharón en una banda de ancho * 2.

Sub-nota: debido a la agrupación estadística, debe tomar una ocupación promedio de segmento tan bajo como 0.5 si desea que muchos segmentos tengan como máximo un elemento (velocidad máxima para encontrar ignorando los efectos complejos del tamaño de la memoria caché), o tan alto como 3 si quiere un número mínimo de cubos vacíos (que corresponden al espacio desperdiciado).