java - tablas - ¿Por qué la tabla hash se redimensiona duplicándola?

tablas hash ejemplos

Question

Comprobando en java y buscando en línea en línea los ejemplos de código hashtable, parece que el cambio de tamaño de la tabla se realiza duplicándolo.
Pero la mayoría de los libros de texto dicen que el mejor tamaño para la mesa es un número primo.
Entonces mi pregunta es:
Es el enfoque de duplicar porque:

1. Es fácil de implementar, o
2. Encontrar un número primo es demasiado ineficiente (pero creo que encontrar el próximo primo yendo por n+=2 y probando primalidad usando módulo es O (loglogN) que es barato)
3. ¿O este es mi malentendido y solo ciertas variantes de tabla hash solo requieren el tamaño de tabla principal?

Actualizar:
La forma presentada en los libros de texto que usan un número primo es necesaria para que funcionen ciertas propiedades (por ejemplo, el sondeo cuadrático necesita una tabla de tamaño principal para demostrar que, por ejemplo, si una tabla no está llena, se insertará el elemento X).
El enlace publicado como duplicado generalmente pregunta acerca de aumentar en cualquier número, por ejemplo, 25% o el próximo primo y la respuesta aceptada establece que duplicamos para mantener la operación de cambio de tamaño "rara", por lo que podemos garantizar el tiempo amortizado.
Esto no responde a la pregunta de tener un tamaño de tabla que sea primo y usar un primo para cambiar el tamaño, que es incluso mayor que el doble. Entonces la idea es mantener las propiedades del tamaño principal teniendo en cuenta la sobrecarga de redimensionamiento

Answer 1

Java HashMap ( java.util.HashMap ) encadena las colisiones entre contenedores en una lista vinculada (o [a partir del árbol JDK8] según el tamaño y el sobrellenado de los contenedores).

En consecuencia, las teorías sobre las funciones de exploración secundarias no se aplican. Parece que el mensaje ''use primes sizes for hash tables'' se ha desprendido de las circunstancias que se aplica a lo largo de los años ...

Usar potencias de dos tiene la ventaja (como se señala en otras respuestas) de reducir el valor de hash a una entrada de tabla mediante una máscara de bits. La división de enteros es relativamente costosa y en situaciones de alto rendimiento esto puede ayudar.

Voy a observar que "la redistribución de las cadenas de colisión cuando se repite es muy fácil para las tablas que tienen una potencia de dos para una potencia de dos".

Tenga en cuenta que al usar potencias de dos repeticiones al doble del tamaño ''divide'' cada casilla entre dos cubos basándose en el ''siguiente'' bit del código hash. Es decir, si la tabla hash tenía 256 cubos, utilizar los 8 bits más bajos del valor hash para dividir cada cadena de colisión según el noveno bit y permanecer en el mismo contenedor B (el 9º bit es 0) o ir a cubo B + 256 (9º bit es 1). Tal división puede preservar / aprovechar el enfoque de manejo de cubo. Por ejemplo, java.util.HashMap mantiene ordenadas las cubetas pequeñas en orden inverso a la inserción y luego las divide en dos subestructuras que obedecen ese orden. Mantiene grandes cubos en un árbol binario ordenados por código hash y de manera similar divide el árbol para preservar ese orden.

NB: Estos trucos no se implementaron hasta JDK8.

(Estoy bastante seguro) Java.util.HashMap solo aumenta (nunca baja). Pero hay eficiencias similares para reducir a la mitad una tabla hash y duplicarla.

Una ''desventaja'' de esta estrategia es que los ejecutores de Object no son explícitamente necesarios para asegurarse de que los bits de orden baja de los códigos hash estén bien distribuidos. Un código hash perfectamente válido podría estar bien distribuido en general, pero mal distribuido en sus bits de orden baja. Por lo tanto, un objeto que hashCode() contrato general de hashCode() aún podría tanque cuando realmente se utiliza en un HashMap . Java.util.HashMap mitiga esto aplicando un hash ''spread'' adicional en la implementación hashCode() provista. Ese ''spread'' es realmente rápido crudo (xors los 16 bits altos con el bajo).

Los implementadores de objetos deben tener en cuenta (si no ya) que el sesgo en su código hash (o la falta de ellos) puede tener un efecto significativo en el rendimiento de las estructuras de datos que utilizan hashes.

Para el registro, he basado este análisis en esta copia de la fuente:

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java

Answer 2

P: Pero la mayoría de los libros de texto dicen que el mejor tamaño para la mesa es un número primo.

En cuanto a la primalidad del tamaño:

Lo que viene a la primalidad de tamaño, depende del algoritmo de resolución de colisión que elija. Algunos algoritmos requieren un tamaño de tabla principal (doble hashing, hashing cuadrático), otros no, y podrían beneficiarse del tamaño de tabla de potencia de 2, ya que permite operaciones de módulo muy baratas. Sin embargo, cuando los "tamaños de tabla disponibles" más cercanos difieren en 2 veces, el uso de la memoria de la tabla hash puede no ser confiable. Por lo tanto, incluso utilizando hashing lineal o encadenamiento separado, puede elegir no power of 2 size. En este caso, a su vez, vale la pena elegir el tamaño principal particular, porque:

Si elige el tamaño de tabla principal (ya sea porque el algoritmo lo requiere o porque no está satisfecho con la falta de fiabilidad de uso de memoria implícita en el tamaño de potencia 2), el cálculo de ranura de tabla (módulo por tamaño de tabla) podría combinarse con hash. Vea esta respuesta para más.

El punto de que el tamaño de la tabla de potencia de 2 es indeseable cuando la distribución de la función hash es mala (de la respuesta de Neil Coffey) no es práctico, porque incluso si tiene mala función hash, avalanzarla y seguir usando el poder de 2 sería más rápido que el cambio al tamaño de tabla principal, porque una sola división integral es aún más lenta en las CPU modernas que varias de las implicaciones múltiples y operaciones de cambio, requeridas por las buenas funciones de avalancha, por ejemplo, de MurmurHash3.

P: También para ser honesto, me perdí un poco si realmente recomienda los números primos o no. Parece que depende de la variante de la tabla hash y de la calidad de la función hash?

1. La calidad de la función hash no importa, siempre se puede "mejorar" la función hash mediante el avalancing MurMur3, que es más barato que cambiar el tamaño de la tabla principal por el tamaño de la tabla power-of-2, ver arriba.

2. Recomiendo elegir el tamaño principal, con QHash o el algoritmo hash cuadrático ( no son iguales ), solo cuando se necesita un control preciso sobre el factor de carga de la tabla hash y las cargas reales predeciblemente elevadas . Con el tamaño de la tabla de potencia de 2, el factor de ajuste de tamaño mínimo es 2 y, en general, no podemos garantizar que la tabla de dispersión tenga un factor de carga real superior a 0,5. Vea esta respuesta.
   
   De lo contrario, recomiendo ir con la tabla de hash de potencia de 2 con sondeo lineal.

P: ¿Es el enfoque de duplicar porque:
Es fácil de implementar, o

Básicamente, en muchos casos, sí. Vea esta gran respuesta con respecto a los factores de carga :

El factor de carga no es una parte esencial de la estructura de datos de la tabla hash; es la forma de definir reglas de comportamiento para el sistema dinámico (la tabla hash creciente / contracción es un sistema dinámico).

Además, en mi opinión, en el 95% de los casos modernos de tablas hash, esto se simplifica, los sistemas dinámicos se comportan de manera subóptima.

¿Qué está doblando ? Es solo la estrategia de cambio de tamaño más simple. La estrategia podría ser arbitrariamente compleja, y funcionar de manera óptima en sus casos de uso. Podría considerar el tamaño actual de la tabla hash, la intensidad del crecimiento (cuántas operaciones de obtención se realizaron desde el cambio de tamaño anterior), etc. Nadie le prohíbe implementar dicha lógica personalizada de cambio de tamaño.

P: ¿Es demasiado ineficiente encontrar un número primo (pero creo que encontrar el siguiente primo pasando n + = 2 y probar primalidad usando módulo es O (loglogN) que es barato)

Es una buena práctica precomputar algunos subconjuntos de tamaños de tablas hash principales, para elegir entre ellos mediante la búsqueda binaria en tiempo de ejecución. Consulte la lista de capacidades y explicación de doble hash , capacidades de QHash . O, incluso usando la búsqueda directa , eso es muy rápido.

P: ¿ O este es mi malentendido y solo ciertas variantes de tabla hash solo requieren el tamaño de tabla principal?

Sí, solo ciertos tipos requieren, vea arriba.