Rendimiento de HashMap con diferente capacidad inicial y factor de carga

Question

Aquí está mi situación. Estoy usando dos java.util.HashMap para almacenar algunos datos usados ​​frecuentemente en una aplicación web Java que se ejecuta en Tomcat. Sé el número exacto de entradas en cada Hashmap. Las claves serán cadenas, y enter respectivamente.

Mi pregunta es, ¿cuál es la mejor manera de establecer la capacidad inicial y el factor de carga?

¿Debo establecer la capacidad igual a la cantidad de elementos que tendrá y la capacidad de carga a 1.0? Me gustaría el mejor rendimiento absoluto sin usar demasiada memoria. Sin embargo, me temo que la mesa no se llenaría de manera óptima. Con una tabla del tamaño exacto necesario, ¿no habrá una colisión clave, lo que provocará que un escaneo (generalmente corto) encuentre el elemento correcto?

Suponiendo (y esto es un estiramiento) que la función hash es un simple mod 5 de las claves enteras, ¿no significaría que las teclas 5, 10, 15 tocarían el mismo cubo y luego causarían una búsqueda para llenar los cubos al lado de ellos? ¿Una capacidad inicial más grande aumentaría el rendimiento?

Además, si hay una mejor estructura de datos que un hashmap para esto, estoy completamente abierto a eso también.

Answer 1

En ausencia de una función hash perfecta para sus datos, y suponiendo que esto no es realmente un micro-optimización de algo que realmente no importa, me gustaría probar el siguiente:

asumir la carga por defecto la capacidad (.75) utilizada por HashMap es un buen valor en la mayoría de las situaciones. Siendo ese el caso, puede usarlo y establecer la capacidad inicial de su HashMap en función de su propio conocimiento de cuántos elementos contendrá: configúrelo de modo que la capacidad inicial sea x .75 = número de elementos (redondee hacia arriba).

Si fuera un mapa más grande, en una situación en la que la búsqueda a alta velocidad era realmente crítica, sugeriría utilizar algún tipo de trie en lugar de un mapa hash. Para cadenas largas, en mapas grandes, puede ahorrar espacio, y algo de tiempo, mediante el uso de una estructura de datos más orientada a cadenas, como un trie.

Answer 2

Las entradas se asignan a los depósitos de forma aleatoria. Entonces, incluso si tiene tantas cubetas como entradas, algunos de los cubos tendrán colisiones.

Si tiene más cubos, tendrá menos colisiones. Sin embargo, más cubos significa extenderse en la memoria y, por lo tanto, más lento. En general, un factor de carga en el rango 0.7-0.8 es aproximadamente óptimo, por lo que probablemente no valga la pena cambiarlo.

Como siempre, es probable que valga la pena perfilar antes de que te cuelguen el microtuning estas cosas.

Answer 3

Suponiendo que (y esto es un tramo) que la función hash es un mod sencillo 5 de las claves enteras

no lo es. De HashMap.java:

static int hash(int h) { 
    // This function ensures that hashCodes that differ only by 
    // constant multiples at each bit position have a bounded 
    // number of collisions (approximately 8 at default load factor). 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

Yo ni siquiera voy a fingir que entiendo, pero parece que está diseñado para manejar solo esa situación.

Tenga en cuenta también que el número de cubos también es siempre una potencia de 2, sin importar el tamaño que solicite.

Answer 4

Encuentro que es mejor no juguetear con la configuración predeterminada a menos que realmente lo necesite.

Hotspot hace un gran trabajo haciendo las optimizaciones para usted.

En cualquier caso; Yo usaría un generador de perfiles (Say Netbeans Profiler) para medir el problema primero.

Almacenamos rutinariamente mapas con 10000s de elementos y si tiene una buena implementación de igual y código hash (¡y cadenas y enteros lo hacen!) Esto será mejor que cualquier cambio de carga que pueda realizar.

Answer 5

Suponiendo que su función de almohadilla es "buena", lo mejor que puede hacer es establecer el tamaño inicial de la cantidad esperada de elementos, suponiendo que puede obtener una buena estimación a bajo costo. Es una buena idea hacer esto porque cuando un HashMap cambia de tamaño tiene que volver a calcular los valores hash para cada tecla en la tabla.

Deje el factor de carga en 0.75. El valor de 0.75 se ha elegido empíricamente como un buen compromiso entre el rendimiento de búsqueda de hash y el uso de espacio para la matriz de hash primaria. A medida que aumenta el factor de carga, el tiempo promedio de búsqueda aumentará significativamente.

Si desea profundizar en las matemáticas del comportamiento de la tabla hash: Donald Knuth (1998). El arte de la programación de computadoras '. 3: Clasificación y búsqueda (2da ed). Addison-Wesley. pp. 513-558. ISBN 0-201-89685-0.