c++ - example - cuál es la diferencia entre mapa y hashmap en STL
set c++ (4)
La principal diferencia es el tiempo de búsqueda.
para pocos datos es mejor mapa
para muchos datos, es mejor hashmap
de todos modos las respuestas técnicas dadas previamente son correctas.
Esta pregunta ya tiene una respuesta aquí:
- map vs. hash_map en C ++ 5 respuestas
en C ++ STL, hay dos mapas, mapas y hashmap. Alguien sabe la diferencia principal de ellos?
hash_map usa una tabla hash. Este es un tiempo "constante" en teoría. La mayoría de las implementaciones usan una tabla hash de "colisión". Lo que sucede en la realidad es:
- Crea una gran mesa
- Usted tiene una función "hash" para su objeto que le genera un lugar aleatorio en la tabla (de aspecto aleatorio, pero la función hash siempre devolverá el mismo valor para su objeto) y generalmente esta es la modificación del valor real de 32 bits (o 64 bits) valor hash con el tamaño de la tabla.
- La tabla mira para ver si el espacio está disponible. Si es así, coloca el elemento en la tabla. Si no, verifica si el elemento que está tratando de insertar es el que está intentando insertar. Si es así, es un duplicado así que no inserte. Si no, esto se denomina "colisión" y usa alguna fórmula para buscar otra celda y esto continúa hasta que encuentra una celda duplicada o vacía.
- Cuando la mesa se llena demasiado, cambia de tamaño. Una implementación eficiente (en el tiempo) almacenará todos los valores de hash originales junto con los elementos para que no tenga que volver a calcular los hash cuando lo haga. Además, la comparación de los hashes suele ser más rápida que la comparación de los elementos, por lo que puede hacer esto mientras se busca eliminar la mayoría de las colisiones como un paso previo.
- Si nunca borras nada, es simple. Sin embargo, eliminar elementos agrega una complejidad extra. Una celda que tiene un elemento que se ha eliminado se encuentra en un estado diferente de uno que estuvo vacío todo el tiempo, ya que puede haber colisiones y si solo lo vacía, esos elementos no se encontrarán. Entonces, usualmente hay alguna "marca". Por supuesto, ahora cuando queremos reutilizar la célula, todavía tenemos que volver a recurrir en caso de que haya un duplicado más abajo (en cuyo caso no podemos insertar en esta celda), y luego recuerde reutilizar la celda eliminada.
- La restricción habitual es que sus objetos deben implementarse para verificar la igualdad, pero Dinkumware (o SGI) implementó los suyos con el operador <que puede ser más lento pero tiene la ventaja de desacoplar sus elementos y el tipo de contenedor asociado que pueden almacenarse en, aunque todavía necesita una función de hash para almacenar en un hash.
La teoría es que si tienes una tabla lo suficientemente grande, las operaciones son a tiempo constante, es decir, no depende de la cantidad de elementos reales que tengas. En la práctica, por supuesto, cuantos más elementos tenga, más colisiones ocurrirá.
std :: map usa un árbol binario. No es necesario definir una función hash para un objeto, solo una comparación estrictamente ordenada. Al insertar, busca el punto de inserción (y si hay duplicados) y agrega el nodo, y es posible que necesite volver a equilibrar el árbol para que la profundidad de las hojas no sea más de 1 aparte. El tiempo de reequilibrio también es relativo a la profundidad del árbol, por lo que todas estas operaciones son O (log N) donde N es el número de elementos.
Las ventajas del hash es la complejidad Las ventajas del árbol son:
- Totalmente escalable Solo usa lo que necesita, no necesita una mesa enorme ni se adelanta al tamaño de la mesa, aunque el hash puede requerir menos "equipaje" por elemento que un árbol.
- No es necesario hacer hash primero, lo que para una buena función puede llevar más tiempo que las comparaciones si el conjunto de datos no es grande.
Otro problema con std::map es que usa una única función de comparación estrictamente ordenada, mientras que una función de "comparación" que devuelve -1, 0 o 1 sería mucho más eficiente, particularmente con el tipo de clave más comúnmente utilizado, std :: string, que ya tiene esta función implementada (es char_traits::compare ). (Esta ineficacia se basa en la premisa de que para verificar que x==y , compruebe x<y y<x para hacer dos comparaciones. Lo haría solo una vez por búsqueda).
map es un árbol rojo-negro, el tiempo de acceso O(log(n)) . hash_map (que no es estándar, sin embargo unordered_map se convertirá en estándar) usa (conceptualmente) un hash de la clave como un índice en una matriz de listas enlazadas, y por lo tanto tiene un mejor tiempo de acceso de O(1) y el peor de los casos de O(n) .
el mapa usa un árbol rojo-negro como la estructura de datos, por lo que los elementos que ingresas están ordenados, e insertar / eliminar es O (log (n)). Los elementos necesitan implementar al menos operator< .
hashmap utiliza un hash, por lo que los elementos no están clasificados, insert / delete es O (1). Los elementos necesitan implementar al menos operator== y necesita una función hash.