Uso eficiente de Hashmap

Question

¿Cuál es el enfoque más eficiente para usar hashmaps?

A) Use múltiples hashmaps más pequeños, o

B) ¿almacenar todos los objetos en un hashmap gigante?

(Suponga que el algoritmo de hash para las claves es bastante eficiente, lo que resulta en pocas colisiones)

CLARIFICACIÓN: la opción B implica segregación por clave primaria, es decir, no es necesaria una búsqueda adicional para determinar qué hashmap real usar. (Por ejemplo, si las claves de búsqueda son alfanuméricas, Hashmap 1 almacena las A, Hashmap 2 almacena las B, etc.)

Answer 1

Definitivamente B. La ventaja de las tablas hash es que el número promedio de comparaciones por búsqueda es independiente del tamaño.

Si divide su mapa en N hashmaps más pequeños, tendrá que buscar la mitad de ellos en promedio para cada búsqueda. Si los hashmaps más pequeños tienen el mismo factor de carga que habría tenido el mapa más grande, aumentará el número total de comparaciones en un factor de aproximadamente N / 2.

Y si los hashmaps más pequeños tienen un factor de carga menor, está desperdiciando memoria.

Todo lo que se supone es que distribuye las claves al azar entre los hashmaps más pequeños. Si los distribuye de acuerdo con alguna función de la clave (por ejemplo, un prefijo de cadena), entonces lo que ha creado es un trie , que es eficiente para algunas aplicaciones (por ejemplo, autocompletar en formularios web)

Answer 2

¿Se usan estos mapas en lugares lógicamente distintos? Por ejemplo, no tendría un mapa que contenga usuarios, resultados de consultas en caché, registradores, etc., solo porque sabe que las claves no chocarán. Sin embargo, tampoco dividiría un solo mapa en varios mapas.

Mantenga un hashmap para cada asignación lógica de clave a valor.

Answer 3

Además de la respuesta de @ Jon, puede haber razones prácticas por las que desea mantener tablas hash separadas.

Si tiene tablas separadas para asignaciones diferentes, puede 'borrar' cada una de las asignaciones de forma independiente; p.ej. llamando a 'clear' o deshaciéndose de la referencia a la tabla correspondiente.

Si las tablas separadas contienen asignaciones para entradas almacenadas en caché, puede usar diferentes estrategias para 'envejecer' las entradas respectivas.

Si la aplicación es multiproceso, el uso de tablas separadas puede reducir la contención de bloqueo y puede (para algunas arquitecturas de procesador) aumentar las proporciones de aciertos de memoria caché del procesador.