cuál es la diferencia entre mapa y hashmap en STL

Question

en C++ STL, hay dos mapas, mapa y hashmap. Alguien sabe la diferencia principal de ellos?

Answer 1

mapa utiliza un árbol rojo-negro como la estructura de datos, por lo que los elementos que ponen allí se ordenan, e insertar/eliminar es O (log (n)). Los elementos deben implementar al menos operator<.

hashmap utiliza un hash, por lo que los elementos no están clasificados, insertar/eliminar es O (1). Los elementos necesitan implementar al menos operator== y necesita una función hash.

Answer 2

map es un árbol rojo-negro, O(log(n)) tiempo de acceso. hash_map (que no es estándar, sin embargo unordered_map se convertirá en estándar) utiliza (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 caso de O(n).

Ver http://en.wikipedia.org/wiki/Red-black_tree

Answer 3

La principal diferencia es el tiempo de búsqueda.

de pocos datos es mejor mapa

para la gran cantidad de datos es mejor HashMap

todos modos las respuestas dadas anteriormente tecnicos son correctas.

Answer 4

hash_map utiliza 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 ocurre en realidad es:

• Se crea una gran mesa
• Usted tiene una función de "control" para el objeto que genera un lugar al azar en la tabla (aleatorio buscando, pero la función hash será siempre devuelva el mismo valor para su objeto) y generalmente este es el mod del valor de hash real de 32 bits (o 64 bits) 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 el 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 podría ser más lento pero tiene la ventaja de desacoplar sus elementos y el tipo de contenedor asociado que puede almacenarse en, aunque todavía necesita una función 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 utiliza 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 de hash es la complejidad Las ventajas del árbol es:

• 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 hay necesidad de hash primero, que para una buena función puede tomar más tiempo que las comparaciones si el conjunto de datos no es grande.

Otro problema con std::map es que utiliza una única función de comparación ordenado estrictamente, mientras que una función "comparar" que devuelve -1, 0 o 1 sería mucho más eficiente, sobre todo con la clave más utilizada type, std :: string, que ya tiene esta función implementada (es char_traits::compare). (Esta ineficiencia se basa en la premisa de que para verificar x==y, marque x<y y y<x para hacer dos comparaciones. Lo haría solo una vez por búsqueda).