Usar HashMap en C++

1. Usar HashMap con std::map en C++
2. Usar HashMap con std::unordered_map en C++
3. Diferencias clave y cuándo usar cada mapa en C++

El HashMap es una estructura de datos vital que contiene pares clave-valor donde se puede recuperar un valor usando la clave relevante. Cada clave se asigna a un valor particular en un HashMap.

Usando claves durante las iteraciones, podemos acceder a los valores correspondientes mucho más rápido. Por lo tanto, HashMap se considera una estructura de datos eficiente y esencial al recuperar valores, con clave y valor de cualquier tipo.

Antes de C++ 11, una tabla hash definida por el estándar no estaba presente en la biblioteca estándar de C++, pero los implementadores algo diferentes tenían variantes no estándar de la tabla hash, a menudo llamadas HashMap. Junto con C++ 11, se agregó una implementación estándar de la tabla hash a la biblioteca estándar.

Aún así, debido a que tiene varias variaciones de la tabla hash como HashMap de diferentes bibliotecas, se decidió usar un nombre separado para llamar a la nueva implementación para evitar confusiones.

Por lo tanto, en C++, std::unordered_map es el nombre alternativo para HashMap, pero otro mapa usa el concepto de par clave-valor, el std::map.

Existen diferencias clave entre std::unordered_map y std::map. Como sugiere el nombre, los elementos dentro de std::unordered_map están desordenados mientras que los elementos en std::map están ordenados.

Usar HashMap con std::map en C++

std::map pertenece a la categoría de contenedores asociativos donde los elementos se almacenan en pares clave-valor mapeados. En std::map y std::unordered_map, la clave siempre debe ser única, pero puede haber varias claves únicas donde el valor asignado es similar.

El std::map se implementa utilizando Árbol de búsqueda binaria de autoequilibrio (árbol AVL/árbol rojo-negro). La característica principal de BST (Árbol de búsqueda binaria autoequilibrado) es que la altura siempre se mantiene automáticamente al mínimo cuando se insertan y eliminan elementos.

En std::map, la complejidad de tiempo promedio depende logarítmicamente de la cantidad de elementos que se almacenan; por lo tanto, lleva un tiempo O(log n) en promedio para que ocurra una operación. En O(log n), O se refiere a la notación Big O, y n se refiere al número de elementos almacenados.

Por lo tanto, los BST son útiles para crear y mantener listas ordenadas.

Ejemplo:

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
  map<int, string> Players;

  Players.insert(std::pair<int, string>(2, "Lin Dan"));
  Players.insert(std::pair<int, string>(1, "Chen Long"));

  cout << "Number of Players " << Players.size() << endl;
  for (map<int, string>::iterator it = Players.begin(); it != Players.end();
       ++it) {
    cout << (*it).first << ": " << (*it).second << endl;
  }
}

Producción :

Number of Players 2
1: Chen Long
2: Lin Dan

Usar HashMap con std::unordered_map en C++

std::unordered_map se implementa utilizando la tabla hash en C++. Las tablas hash también pertenecen a contenedores asociativos. Los valores asignados se almacenan en una tabla hash en una matriz de cubos o espacios, de los cuales se pueden recuperar los valores necesarios.

Esta indexación se realiza mediante la función hash, código hash. La complejidad de tiempo promedio para la búsqueda, inserción y eliminación de un std::unordered_map es O(1), donde O es la notación Big O, esta es la razón principal por la que std::unordered_map es muy eficiente.

Ejemplo:

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
  unordered_map<string, int> info;

  info["Age"] = 18;
  info["Year"] = 2022;
  info["Number of Players"] = 15;

  for (auto x : info) cout << x.first << " " << x.second << endl;
}

Producción :

Number of Players 15
Year 2022
Age 18

Diferencias clave y cuándo usar cada mapa en C++

Cuando se comparan std::unordered_map y std::map, la diferencia de eficiencia entre los dos es enorme.

std::unordered_map claramente tiene una ventaja de rendimiento considerable sobre std::map. Esto se debe principalmente a que std::unordered_map puede abordar directamente el valor a medida que se colocan en las ranuras y, por lo tanto, no tiene un orden que deba conservarse.

Por otro lado, un std::map tiene un orden que necesita ser preservado; por lo tanto, consume más tiempo. Es posible que esta eficiencia no sea visible para conjuntos de datos pequeños, pero esta diferencia es enorme para conjuntos de datos grandes.

std::unordered_map se puede usar cuando se accede a un solo elemento de un conjunto de datos o se lleva un conteo de elementos cuando no se requiere un orden.

std::map también tiene algunas ventajas sobre std::unordered_map. En general, los BST se pueden implementar más rápidamente que una tabla hash, y podemos hacerlo de la manera que prefieramos, pero para el hash, debemos depender en gran medida de las bibliotecas.

Por lo tanto, std::map se puede implementar fácilmente en comparación con std::unordered_map. Además, cuando se trata de ordenar, es mucho más fácil ordenar claves en std::map que en std::unordered_map porque inorder traversing no es una operación natural para las tablas hash, pero lo es para BST.

std::map se puede usar en situaciones como la impresión de datos en orden ordenado, donde los datos deben ordenarse para consultas de búsqueda, estadísticas de pedidos, etc.

Tanto std::map como std::unordered_map tienen ciertas similitudes y diferencias que pueden manipularse según la necesidad de ese momento.