Solo sé que la diferencia entre el hashmap y el mapa es que hashmap se implementa con la función hash pero el mapa se implementa con el árbol. ¿Podría cualquier cuerpo agregar algo más?¿Hay algo que hashmap puede hacer pero el mapa no puede?
Basado en esto, ¿hay algo que hashmap puede hacer pero el mapa no?
HashMaps tienen un rendimiento promedio de los casos mejor para el acceso (O (1)), pero peor caso peor desempeño (O (n)). Los mapas son siempre O (lg (n)).
Los mapas están ordenados por su clave, los hashmaps no lo son.
Los Hashmaps generalmente usan más memoria que los mapas.
Los mapas suelen permitir una iteración más rápida.
Las buenas funciones hash son más difíciles de escribir que las buenas funciones de pedido (y más difíciles de analizar).
No creo que haya nada que un hashmap pueda hacer que un mapa no pueda.
Los Hashmaps generalmente usan más memoria también. – GManNickG
IMO el reclamo O (1) para tablas hash es un poco engañoso. Hay un límite fijo para la cantidad de claves reconocidas como distintas sin manejo de colisiones, y una vez que se producen colisiones, el rendimiento se deteriora al de la manipulación de colisiones (a menudo O (n)). De acuerdo, tradicionalmente el hash ha admitido tantas claves únicas como puede almacenar en la memoria, pero me pregunto cuántas personas han olvidado actualizar los cálculos de hash personalizados de 32 bits a 64 bits, y obtendrán una degradación de rendimiento con tablas hash muy grandes. Ninguna tabla hash de tamaño lo resolverá si el hash en sí es demasiado estrecho. – Steve314
@Steve - Mencioné que O (1) era el caso promedio y O (n) era el peor de los casos. @GMan - Gracias, agregaré eso. –
Un mapa requiere que la clave tenga un orden débil estricto, que quizás no exista. Un hashmap solo necesita una función hash. De esta forma, un hashmap se puede usar con claves que no tienen un orden estricto y débil.
Para ser honesto, los árboles y los hashmaps tienen los mismos problemas aquí. Es un problema que he tenido que abordar recientemente con el uso de autómatas finitos como claves. No se puede hacer un hash (o comparación) de la representación en memoria porque los autómatas equivalentes pueden tener diferentes representaciones. La solución es derivar una forma canónica. Una vez que tiene una forma canónica, puede trabajar igualmente bien desde las representaciones en memoria, ya sea que esté comparando o haciendo hash, y eso se aplica a casi cualquier clase de datos. Si puede hash, puede definir fácilmente un orden arbitrario pero consistente. – Steve314
Una ventaja que hasmaps tiene sobre los árboles es que, en un entorno de subprocesos múltiples, no tiene que bloquear todo el contenedor para agregar o eliminar una sola clave; bloquear la única entrada relevante en la tabla hash es (casi) suficiente.
Casi porque puede haber metadatos (cantidad de elementos en la tabla hash, por ejemplo) para actualizar. Y probablemente necesite bloquear toda la mesa para crecer o reducirla, por supuesto.
Algo similar, tal vez no es una tontería: http://stackoverflow.com/questions/2196995/is-there-any-advantage-of-using-map-over-unordered-map-in-case-of -trivial-keys/ – GManNickG
Ten un poco de cuidado con la terminología. En algunos círculos, un "mapa" simplemente se refiere a un objeto que hace almacenamiento y búsqueda de clave/valor, y un "hashmap" es una implementación de un mapa. (Donde un mapa de árbol podría ser otro). IOW, "map" es una interfaz, y "hash map" es una implementación concreta. (Estoy notando esto porque su pregunta no está etiquetada o se refiere a una biblioteca en particular.) –
@Ben: en C++ 'map' se refiere casi sin ambigüedad a' std :: map', un árbol. – GManNickG