¿Cuál es la mejor manera de usar un HashMap en C ++?

Sé que STL tiene una API HashMap, pero no puedo encontrar ninguna documentación buena y exhaustiva con buenos ejemplos al respecto.

Cualquier buen ejemplo será apreciado.

La biblioteca estándar incluye los contenedores de mapas ( std::mapy std::unordered_map) ordenados y no ordenados . En un mapa ordenado, los elementos se ordenan por clave, inserción y acceso está en O (log n) . Por lo general, la biblioteca estándar utiliza internamente árboles rojos y negros para los mapas ordenados. Pero esto es solo un detalle de implementación. En un mapa desordenado, inserte y acceda en O (1). Es solo otro nombre para una tabla hash.

Un ejemplo con (ordenado) std::map:

#include <map>
#include <iostream>
#include <cassert>

int main(int argc, char **argv)
{
  std::map<std::string, int> m;
  m["hello"] = 23;
  // check if key is present
  if (m.find("world") != m.end())
    std::cout << "map contains key world!\n";
  // retrieve
  std::cout << m["hello"] << '\n';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << '\n';
  return 0;
}

Salida:

23
Clave: hola Valor: 23

Si necesita ordenar en su contenedor y está bien con el tiempo de ejecución de O (log n), simplemente utilícelo std::map.

De lo contrario, si realmente necesita una tabla hash (O (1) de inserción / acceso), echa un vistazo std::unordered_map, que tiene una similar a la std::mapAPI (por ejemplo, en el ejemplo anterior sólo tiene que buscar y reemplazar mapcon unordered_map).

El unordered_mapcontenedor se introdujo con la revisión estándar de C ++ 11 . Por lo tanto, dependiendo de su compilador, debe habilitar las funciones de C ++ 11 (por ejemplo, cuando usa GCC 4.8 debe agregar -std=c++11a CXXFLAGS).

Incluso antes del lanzamiento de C ++ 11, GCC era compatible unordered_map, en el espacio de nombres std::tr1. Por lo tanto, para los compiladores GCC antiguos, puede intentar usarlo así:

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

También es parte del impulso, es decir, puede usar el correspondiente encabezado de impulso para una mejor portabilidad.

A hash_mapes una versión anterior no estandarizada de lo que para fines de estandarización se llama unordered_map(originalmente en TR1, e incluido en el estándar desde C ++ 11). Como su nombre lo indica, es diferente de std::mapestar desordenado principalmente: si, por ejemplo, itera a través de un mapa de begin()a end(), obtiene los elementos en orden por la tecla ¹ , pero si itera a través de un unordered_mapde begin()a end(), obtiene elementos en un orden más o menos arbitrario.

unordered_mapNormalmente se espera que An tenga una complejidad constante. Es decir, una inserción, búsqueda, etc., generalmente toma una cantidad de tiempo fija, independientemente de cuántos elementos haya en la tabla. Una std::maptiene una complejidad logarítmica en la cantidad de elementos que se almacenan, lo que significa que el tiempo para insertar o recuperar un elemento aumenta, pero muy lentamente , a medida que el mapa crece. Por ejemplo, si se necesita 1 microsegundo para buscar uno de 1 millón de elementos, entonces puede esperar que tome alrededor de 2 microsegundos para buscar uno de 2 millones de elementos, 3 microsegundos para uno de 4 millones de elementos, 4 microsegundos para uno de 8 millones artículos, etc.

Desde un punto de vista práctico, esa no es realmente toda la historia. Por naturaleza, una tabla hash simple tiene un tamaño fijo. Adaptarlo a los requisitos de tamaño variable para un contenedor de propósito general es algo no trivial. Como resultado, las operaciones que (potencialmente) hacen crecer la tabla (por ejemplo, la inserción) son potencialmente relativamente lentas (es decir, la mayoría son bastante rápidas, pero periódicamente una será mucho más lenta). Las búsquedas, que no pueden cambiar el tamaño de la tabla, generalmente son mucho más rápidas. Como resultado, la mayoría de las tablas basadas en hash tienden a ser mejores cuando se realizan muchas búsquedas en comparación con la cantidad de inserciones. Para situaciones en las que inserta una gran cantidad de datos, luego recorra la tabla una vez para recuperar los resultados (por ejemplo, contar el número de palabras únicas en un archivo) es probable questd::map será igual de rápido y posiblemente incluso más rápido (pero, una vez más, la complejidad computacional es diferente, por lo que también puede depender de la cantidad de palabras únicas en el archivo).

^{1 Cuando el orden se define mediante el tercer parámetro de plantilla cuando crea el mapa, std::less<T>de forma predeterminada.}

Aquí hay un ejemplo más completo y flexible que no omite los pasos necesarios para generar errores de compilación:

#include <iostream>
#include <unordered_map>

class Hashtable {
    std::unordered_map<const void *, const void *> htmap;

public:
    void put(const void *key, const void *value) {
            htmap[key] = value;
    }

    const void *get(const void *key) {
            return htmap[key];
    }

};

int main() {
    Hashtable ht;
    ht.put("Bob", "Dylan");
    int one = 1;
    ht.put("one", &one);
    std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one");
}

Todavía no es particularmente útil para las claves, a menos que estén predefinidas como punteros, ¡porque un valor coincidente no funcionará! (Sin embargo, como normalmente uso cadenas para las claves, la sustitución de "cadena" por "const void *" en la declaración de la clave debería resolver este problema).

Evidencia que std::unordered_mapusa un mapa hash en GCC stdlibc ++ 6.4

Esto se mencionó en: https://stackoverflow.com/a/3578247/895245 pero en la siguiente respuesta: ¿Qué estructura de datos está dentro de std :: map en C ++? He dado más evidencia de ello para la implementación de GCC stdlibc ++ 6.4 al:

• Paso GDB depuración en la clase
• análisis de características de rendimiento

Aquí hay una vista previa del gráfico de características de rendimiento descrito en esa respuesta:

Cómo usar una clase personalizada y una función hash con unordered_map

Esta respuesta lo define: C ++ unordered_map usando un tipo de clase personalizado como clave

Extracto: igualdad:

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

Función hash:

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}

Para aquellos de nosotros que intentamos descubrir cómo hacer hash nuestras propias clases mientras todavía usamos la plantilla estándar, hay una solución simple:

1. En su clase, debe definir una sobrecarga del operador de igualdad ==. Si no sabe cómo hacer esto, GeeksforGeeks tiene un excelente tutorial https://www.geeksforgeeks.org/operator-overloading-c/

2. Bajo el espacio de nombres estándar, declare una estructura de plantilla llamada hash con su nombre de clase como tipo (ver más abajo). Encontré una gran publicación de blog que también muestra un ejemplo de cálculo de hashes usando XOR y desplazamiento de bits, pero eso está fuera del alcance de esta pregunta, pero también incluye instrucciones detalladas sobre cómo lograr usar funciones hash también https://prateekvjoshi.com/ 2014/06/05 / using-hash-function-in-c-for-user-defined-classes /

namespace std {

  template<>
  struct hash<my_type> {
    size_t operator()(const my_type& k) {
      // Do your hash function here
      ...
    }
  };

}

3. Entonces, para implementar una tabla hash usando su nueva función hash, solo tiene que crear una std::mapo std::unordered_maptal como lo haría normalmente y usarla my_typecomo clave, la biblioteca estándar usará automáticamente la función hash que definió antes (en el paso 2) para hacer hash tus llaves.

#include <unordered_map>

int main() {
  std::unordered_map<my_type, other_type> my_map;
}