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

174

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.

usuario855
fuente
¿Está preguntando sobre el hash_map de C ++ 1x, o sobre el std :: map?
frágil
2
Quiero algo como un java.util.HashMap en C ++ y la forma estandarizada de hacerlo si hay uno. De lo contrario, la mejor biblioteca no estándar. ¿Qué usan comúnmente los desarrolladores de C ++ cuando necesitan un HashMap?
user855

Respuestas:

238

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.

maxschlepzig
fuente
1
Si bien la biblioteca estándar no tiene un contenedor basado en tablas hash, casi todas las implementaciones incluyen hash_mapdesde el SGI STL de una forma u otra.
James McNellis el
@JamesMcNellis, que se recomienda unordered_map o hash_map para la implementación de HashMap
Shameel Mohamed
2
@ShameelMohamed, 2017, es decir, 6 años después de C ++ 11, debería ser difícil encontrar un STL que no proporcione unordered_map. Por lo tanto, no hay razón para considerar lo no estándar hash_map.
maxschlepzig
30

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 1 , 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.

Jerry Coffin
fuente
1
Me doy cuenta de que voy a venir 9 años después de la publicación de la respuesta, pero ... ¿tiene un enlace a un documento que menciona el hecho de que un mapa desordenado puede reducir su tamaño? Por lo general, las colecciones estándar solo crecen. Además, si inserta muchos datos pero sabe de antemano más o menos cuántas claves insertará, puede especificar el tamaño del mapa en la creación, lo que básicamente anula el costo de cambio de tamaño (porque no habrá ninguno) .
Zonko
@ Zonko: Lo siento, no me di cuenta de esto cuando se me preguntó. Hasta donde yo sé, un mapa desordenado no se contrae, excepto en respuesta a una llamada rehash. Cuando llama rehash, especifica un tamaño para la mesa. Ese tamaño se usará a menos que hacerlo exceda el factor de carga máximo especificado para la tabla (en cuyo caso, el tamaño se aumentará automáticamente para mantener el factor de carga dentro de los límites).
Jerry Coffin
22

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).

Jerry Miller
fuente
44
Tengo que decir que este ejemplo es una muy mala práctica en C ++. Está utilizando un lenguaje fuertemente tipado y lo está destruyendo al usarlo void*. Para empezar, no hay razón para envolverlo, unordered_mapya que es parte del estándar y reduce la capacidad de mantenimiento del código. Luego, si insiste en envolverlo, úselo templates. Para eso son exactamente.
guyarad
Fuertemente escrito? Probablemente quieras decir estáticamente escrito. El hecho de que él puede pasar de const char ptr a vacío silenciosamente hace que C ++ esté tipado estáticamente, pero no fuertemente. Hay tipos, pero el compilador no dirá nada a menos que habilites algún indicador oscuro que probablemente no exista.
Sahsahae
6

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:

ingrese la descripción de la imagen aquí

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);
    }
  };

}
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
fuente
0

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
      ...
    }
  };

}
  1. 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;
}
iggy12345
fuente