example - Java: ¿un número "principal" o un "poder de dos" como tamaño HashMap?

hashmap vs hashtable java

Question

Muchos libros y tutoriales dicen que el tamaño de una tabla hash debe ser primordial para distribuir uniformemente las claves en todos los segmentos. Pero el HashMap de Java siempre usa un tamaño que es una potencia de dos. ¿No debería estar usando un primo? ¿Qué es mejor, un "primo" o un "poder de dos" como el tamaño de la tabla hash?

Answer 1

Desde el punto de vista del rendimiento / tiempo de cálculo, los tamaños de potencia de dos pueden calcularse con solo un enmascaramiento de bits que es más rápido que la división de enteros, que de otro modo sería necesario.

Answer 2

La única manera de saber qué es mejor entre el primer nivel y el poder de dos es compararlo.

Hace muchos años, al escribir un ensamblador cuyo rendimiento dependía en gran medida de la búsqueda de símbolos talbe, probé esto utilizando un gran bloque de identificadores generados. Incluso con un mapeo ingenuo, encontré que el poder-de-dos, como se esperaba, tenía una distribución menos pareja y cadenas más largas que un número primo de cubos de tamaño similar. Todavía funcionaba más rápido, debido a la velocidad de selección del cubo mediante enmascaramiento de bits.

Sospecho fuertemente que los desarrolladores de java.util no habrían recurrido al hash extra y al power-of-two sin compararlo con el uso de un número primo de cubos. Es una cosa realmente obvia que hacer cuando se diseña una estructura de datos hash.

Por esa razón, estoy seguro de que el tamaño de Rehash y Power-of-Two ofrece un mejor rendimiento para los típicos mapas hash de Java que un número primo de cubos.

Answer 3

La implementación estándar de HashMap tiene un método hash que reafirma el código hash su objeto para evitar esa trampa. El comentario antes del método hash() dice:

/**
 * Retrieve object hash code and applies a supplemental hash function to the
 * result hash, which defends against poor quality hash functions.  This is
 * critical because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */

Answer 4

Probablemente deberías usar tablas hash de primer tamaño si usas una prueba cuadrática para la resolución de colisiones. Si tiene una tabla de tamaño principal, la prueba cuadrática llegará a la mitad de las entradas, menos si no es un primo. Por lo tanto, es posible que no encuentre un lugar adecuado para almacenar su entrada, incluso si su tabla hash está medio llena. Como los mapas hash de Java no usan sondeos cuadráticos, no es necesario usar primos como tamaño.

Answer 5

Usar una potencia de dos enmascara eficazmente los bits superiores del código hash. Por lo tanto, una función hash de mala calidad podría funcionar particularmente mal en este escenario.

El HashMap de Java mitiga esto desconfiando de la hashCode() de hashCode() del objeto y aplicando un segundo nivel de hashing a su resultado :

Aplica una función hash suplementaria a un hashCode dado, que defiende contra las funciones hash de baja calidad. Esto es crítico porque HashMap usa tablas hash de potencia de dos, que de lo contrario encontrarán colisiones para hashCodes que no difieren en bits inferiores.

Si tiene una buena función hash, o hace algo similar a lo que hace HashMap , no importa si usa números primos, etc. como el tamaño de la tabla.

Si, por otro lado, la función hash es de calidad desconocida o de baja calidad, entonces usar un número primo sería una apuesta más segura. Sin embargo, hará que las tablas de tamaño dinámico sean más complejas de implementar, ya que, de repente, es necesario poder producir números primos en lugar de solo multiplicar el tamaño por un factor constante.