c++ - example - ¿Cómo elegir entre map y unordered_map?

hashmap c++

Question

Supongamos que quisiera mapear datos con una cadena como la clave. ¿Qué contenedor debería haber elegido, map o unordered_map ? unordered_map ocupa más memoria así que supongamos que la memoria no es un problema, y ​​la preocupación es la velocidad.

unordered_map generalmente debería dar una complejidad promedio de O (1) con el peor caso de O (n). ¿En qué casos llegaría a O (n)? ¿Cuándo se vuelve más eficiente el tiempo un map que unordered_map ? ¿Sucede cuando n es pequeño?

Suponiendo que usaría STL unordered_map con el haser predeterminado Vs. mapa. cadena es la clave.

Si voy a iterar sobre los elementos en lugar de acceder a un elemento individual cada vez, ¿debería preferir el map ?

Answer 1

¿En qué casos llegaría a O (n)?

si tiene una función hash tan mala que produce el mismo valor hash para todas las agitaciones de entrada (es decir, produce colisiones) ...

¿Qué contenedor debería haber elegido, mapa o unordered_map?

Siempre son las preguntas de los requisitos y la clase / cantidad de datos que tiene.

¿Cuándo se vuelve más eficiente el tiempo un mapa que unordered_map?

Es solo estructuras diferentes. Será mejor que haga una elección para usar uno de ellos dependiendo de sus casos de uso típicos (teniendo en cuenta qué tipo de datos tiene y su cantidad)

¿Hppaen cuando n es pequeño?

En el caso de una pequeña cantidad de datos, todo depende de la implementación particular de STL ... De modo que a veces incluso un vector / matriz simple podría ser más rápido que los contenedores asociativos ...

Answer 2

¿Qué contenedor debería haber elegido, mapa o unordered_map? unordered_map ocupa más memoria así que supongamos que la memoria no es un problema, y ​​la preocupación es la velocidad.

Perfil y luego decidir. unordered_map es generalmente más rápido, pero varía por caso.

¿En qué casos llegaría a O (n)?

Cuando el hashing no es bueno y se le asignan un grupo de elementos a los mismos bins.

¿Cuándo se vuelve más eficiente el tiempo un mapa que unordered_map? ¿Aparece cuando n es pequeño?

Probablemente no, pero perfila si realmente te importa. Tener un contenedor con un tamaño pequeño es el cuello de botella de su programa que parece extremadamente improbable. De todos modos, un vector simple con búsqueda lineal puede ser más rápido para tales casos.

Lo más importante a la hora de decidir son los requisitos de ordenamiento y la falta de invalidación de iterador. Si lo necesita, casi tiene que usar el map . De lo contrario, unordered_map .

Answer 3

En la práctica, si la memoria no es un problema, unordered_map siempre es más rápido si desea acceder a un único elemento.

El peor de los casos es teórico y está vinculado a una contabilidad de hash única para todos los elementos. Esto no es de relevancia práctica. El unordered_map vuelve más lento tan pronto como tiene al menos log N elementos que pertenecen al mismo hash. Esto tampoco es de relevancia práctica. En algunos escenarios especiales, puede usar un algoritmo hash específico que garantice una distribución más uniforme. Para las cadenas ordinarias que no comparten un patrón específico, las funciones hash genéricas que vienen con unordered_map son igual de buenas.

Si desea recorrer el mapa (utilizando iteradores) de forma ordenada, no puede usar unordered_map . Por el contrario, el map no solo permite eso, sino que también puede proporcionarle el siguiente elemento en un mapa basado en una aproximación de la clave (consulte los métodos lower_bound y upper_bound ).

Answer 4

                       | map              | unordered_map
---------------------------------------------------------
element ordering       | strict weak      | n/a 
                       |                  |
common implementation  | balanced tree    | hash table
                       | or red-black tree|  
                       |                  |
search time            | log(n)           | O(1) if there are no hash collisions
                       |                  | Up to O(n) if there are hash collisions 
                       |                  | O(n) when hash is the same for any key
                       |                  |     
Insertion time         | log(n)+rebalance | Same as search
                       |                  | 
Deletion time          | log(n)+rebalance | Same as search
                       |                  | 
needs comparators      | only operator <  | only operator ==
                       |                  |
needs hash function    | no               | yes
                       |                  |
common use case        | when good hash is| In most other cases. 
                       | not possible or  | 
                       | too slow. Or when|
                       | order is required|