create - map java example

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 utilizados con frecuencia 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 e ints respectivamente.

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

¿Debo establecer la capacidad igual al número de elementos que tendrá y la capacidad de carga a 1.0? Me gustaría el mejor rendimiento absoluto sin utilizar demasiada memoria. Sin embargo, me temo que la mesa no se llenaría de manera óptima. Con una tabla del tamaño exacto que se necesita, ¿no habrá una colisión de claves, 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 teclas de enteros, ¿no significaría eso que las teclas 5, 10, 15 golpearían el mismo grupo y luego provocarían una búsqueda para llenar los grupos al lado de ¿ellos? ¿Una capacidad inicial mayor aumentaría el rendimiento?

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

Answer 1

Suponiendo (y esto es un estiramiento) que la función hash es un simple mod 5 de las teclas enteras

No 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);
}

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

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

Answer 2

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

Hotspot hace un gran trabajo de hacer optimizaciones para usted.

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

Rutinariamente almacenamos mapas con 10000s de elementos y si tiene una buena implementación de hashcode y hashcode (¡y las cadenas y los enteros sí!) Esto será mejor que cualquier cambio de carga que pueda hacer.

Answer 3

En ausencia de una función hash perfecta para sus datos, y asumiendo que esto realmente no es una microoptimización de algo que realmente no importa, intentaría lo siguiente:

Suponga que la capacidad de carga predeterminada (.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 basándose en su propio conocimiento de cuántos elementos retendrá: configúrelo de modo que la capacidad inicial 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 usar algún tipo de trie lugar de un mapa hash. Para cadenas largas, en mapas grandes, puede ahorrar espacio y algo de tiempo utilizando una estructura de datos más orientada a las cadenas, como un trie.

Answer 4

Las entradas se asignan a grupos de forma aleatoria. Así que incluso si tiene tantos cubos como entradas, algunos de ellos tendrán colisiones.

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

Como siempre, es probable que valga la pena hacer un perfil antes de quedar atrapado por el microtuning de estas cosas.

Answer 5

Suponiendo que su función de hash sea "buena", lo mejor es establecer el tamaño inicial en el número esperado 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 recalcular los valores de hash para cada clave 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 principal. 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 informática ". 3: Clasificación y búsqueda (2ª ed.). Addison-Wesley. pp. 513–558. ISBN 0-201-89685-0.