Uso eficiente de Hashmap

Question

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

a) Utilizar múltiples HashMaps más pequeños, o

B tienda) todos los objetos en un mapa hash gigante?

(Suponga que el algoritmo de hash de las claves es bastante eficiente, resultando en pocos colisiones)

CLARIFICACIÓN: Opción B implica la segregación por clave principal - es decir, sin búsqueda adicional es necesario determinar que hashmap real a utilizar . (Por ejemplo, si las teclas de búsqueda son alfanuméricas, Hashmap 1 almacena A's, Hashmap 2 almacena B's, 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 hasmaps 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 el mapa más grande habría tenido, aumentará el número total de comparaciones por un factor de aproximadamente N/2.

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

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

Answer 2

¿Se utilizan estos mapas? en lugares lógicamente distintos? Por ejemplo, no tengo un mapa que contenga usuarios, resultados de consultas en caché, registradores, etc., solo porque usted sabe que las claves no entrarán en conflicto. Sin embargo, tampoco dividiría un solo mapa en múltiples mapas.

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

Answer 3

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

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

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

Si la aplicación es de subprocesos múltiples, el uso de tablas separadas puede reducir la contención de bloqueos y puede (para algunas arquitecturas de procesadores) aumentar las proporciones de aciertos de la memoria caché de la memoria del procesador.