mapa vs. hash_map en C++

hashmap

Question

Tengo una pregunta con hash_map y map en C ++. Entiendo que el map está en STL, pero hash_map no es un estándar. ¿Cuál es la diferencia entre los dos?

Answer 1

Algunas de las diferencias clave están en los requisitos de complejidad.

Un mapa requiere O (log (N)) tiempo para inserciones y hallazgos.

Un mapa no ordenado requiere un tiempo "promedio" de O (1) para inserciones y hallazgos, pero se le permite tener un tiempo de caso más desfavorable de O (N).

Por lo tanto, generalmente, unordered_map será más rápido, pero dependiendo de las teclas y la función de hash que almacene, puede empeorar.

Answer 2

La especificación C ++ no dice exactamente qué algoritmo debe usar para los contenedores STL. Sin embargo, pone ciertas restricciones en su rendimiento, lo que descarta el uso de tablas hash para map y otros contenedores asociativos. (Generalmente se implementan con árboles rojos / negros.) Estas restricciones requieren un mejor rendimiento en el peor de los casos para las tablas hash.

Muchas personas realmente quieren tablas hash, sin embargo, los contenedores asociativos STL basados ​​en hash han sido una extensión común durante años. En consecuencia, agregaron unordered_map y tal como versiones posteriores del estándar de C ++.

Answer 3

No sé lo que ofrece, pero hash_map tarda más de 20 segundos en borrar () 150K claves enteros sin signo y valores flotantes. Solo estoy corriendo y leyendo el código de otra persona.

Así es como incluye hash_map.

#include "StdAfx.h"
#include <hash_map>

Leo esto aquí https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap

diciendo que clear () es el orden de O (N). Eso para mí, es muy extraño, pero, así es como es.

Answer 4

Se implementan de maneras muy diferentes.

hash_map ( hash_map en TR1 y Boost; utilícelos en su lugar) usa una tabla hash donde la clave se asigna a una ranura en la tabla y el valor se almacena en una lista vinculada a esa clave.

map se implementa como un árbol de búsqueda binaria equilibrado (generalmente un árbol rojo / negro).

Un map unordered_map debería proporcionar un rendimiento ligeramente mejor para acceder a elementos conocidos de la colección, pero un map tendrá características útiles adicionales (por ejemplo, se almacena en orden ordenado, lo que permite el cruce de principio a fin). unordered_map será más rápido en insertar y eliminar que en un map .

Answer 5

hash_map era una extensión común proporcionada por muchas implementaciones de bibliotecas. Es exactamente por eso que se renombró a unordered_map cuando se agregó al estándar de C ++ como parte de TR1. el mapa generalmente se implementa con un árbol binario equilibrado como un árbol rojo-negro (las implementaciones varían por supuesto). hash_map y hash_map generalmente se implementan con tablas hash. Por lo tanto, el orden no se mantiene. unordered_map insert / delete / query será O (1) (tiempo constante) donde el mapa será O (log n) donde n es el número de elementos en la estructura de datos. Por lo tanto, unordered_map es más rápido, y si no le importa el orden de los elementos, debe preferirse sobre el map . Algunas veces quiere mantener el orden (ordenado por la clave) y para ese map sería la opción.