mapa vs hash_map en C ++

117

Tengo una pregunta con hash_mapy mapen C ++. Entiendo que mapestá en STL, pero hash_mapno es un estándar. ¿Cuál es la diferencia entre los dos?

Skydoor
fuente

Respuestas:

133

Se implementan de formas muy diferentes.

hash_map( unordered_mapen TR1 y Boost; utilícelos en su lugar) use una tabla hash donde la clave está codificada en un espacio en la tabla y el valor se almacena en una lista vinculada a esa clave.

map se implementa como un árbol de búsqueda binario balanceado (generalmente un árbol rojo / negro).

An unordered_mapdebería ofrecer un rendimiento ligeramente mejor para acceder a elementos conocidos de la colección, pero maptendrá características útiles adicionales (por ejemplo, se almacena en orden ordenado, lo que permite recorrerlos de principio a fin). unordered_mapserá más rápido al insertar y eliminar que a map.

Joe
fuente
7
No estoy completamente de acuerdo contigo con respecto a la actuación. El rendimiento está influenciado por una serie de parámetros y regañaría a cualquier programador que use un mapa_desordenado para tan solo 10 entradas porque "Es más rápido". Preocúpese primero por la interfaz / funcionalidad, después por el rendimiento.
Matthieu M.
24
Bueno, sí, ayuda si comprende su problema. Hasta ciertos órdenes de magnitud, probablemente sea un lavado en cuanto al rendimiento, pero es importante comprender las características de rendimiento de ambos contenedores, ya que se desvían de diferentes formas a medida que aumentan los volúmenes de datos.
Joe
7
Curiosamente, acabo de intercambiar un std :: map con un boost :: unordered_map en una aplicación en la que hago muchas búsquedas aleatorias, pero también repito todas las claves en el mapa. Ahorré una gran cantidad de tiempo en la búsqueda, pero lo recuperé a través de las iteraciones, así que cambié de nuevo al mapa y busco otras formas de mejorar el rendimiento de la aplicación.
Erik Garrison
4
@ErikGarrison Si usa el acceso aleatorio y la iteración mucho más de lo que inserta y elimina elementos, podría tener sus objetos tanto en un árbol como en un hash_map (almacenando un puntero, o mejor aún, un shared_ptr, a los mismos objetos en ambos en caso de que estuviera utilizando instancias reales). A continuación, tendrá O (1) tiempo de acceso a través del hash_map y O (n) tiempo de iteración a través del mapa. Por supuesto, debe recordar agregar y eliminar los punteros de ambos cada vez. Podrías escribir fácilmente una clase de contenedor personalizada que (probablemente la plantilla también) que encapsule este comportamiento por ti.
sprite
2
@ErikGarrison Por supuesto, si prueba este método, pagaría con un espacio adicional menor. Sin embargo, dado que usarías punteros, eso no debería ser demasiado. Si realmente lo desea, puede exagerar y escribir su propia implementación de un AVL y usar el puntero de nodo como su tipo de datos en el hash_map, esto le dará O (1) tiempo de acceso a un nodo en el árbol desde el cual podrá iterar linealmente a donde lo necesite. Por supuesto, esto implicaría bastante codificación y no estoy seguro de que valga la pena a menos que necesite iterar mucho desde y hacia ubicaciones de acceso aleatorio.
sprite
35

hash_mapera una extensión común proporcionada por muchas implementaciones de bibliotecas. Esa es exactamente la razón por la que se renombró unordered_mapcuando se agregó al estándar C ++ como parte de TR1. map generalmente se implementa con un árbol binario balanceado como un árbol rojo-negro (las implementaciones varían, por supuesto). hash_mapy unordered_mapgeneralmente se implementan con tablas hash. Por tanto, el orden no se mantiene. unordered_mapinsertar / eliminar / consulta será O (1) (tiempo constante) donde mapa será O (log n) donde n es el número de elementos en la estructura de datos. Entonces unordered_mapes más rápido, y si no le importa el orden de los artículos, debe preferirlo map. A veces se desea mantener el orden (ordenado por clave) y para eso mapsería la elección.

Janglin
fuente
9
Me gustaría señalar que hashmap tiene un acceso de O (N) en el peor de los casos cuando es probable que haya colisiones (fcn de hash incorrecto, factor de carga demasiado alto, etc.)
KitsuneYMG
Un buen mapa de hash tiene un costo esperado de O (1), no se garantiza que sea así. Los hashmaps incorrectos pueden tener un costo esperado que no sea O (1).
Más claro
14

Algunas de las diferencias clave están en los requisitos de complejidad.

  • A maprequiere O(log(N))tiempo para las operaciones de inserción y búsqueda, ya que se implementa como una estructura de datos de árbol rojo-negro .

  • An unordered_maprequiere un tiempo 'promedio' de O(1)para inserciones y búsquedas, pero se le permite tener un tiempo en el peor de los casos de O(N). Esto se debe a que se implementa utilizando la estructura de datos de la tabla hash .

Entonces, por lo general, unordered_mapserá más rápido, pero dependiendo de las claves y la función hash que almacene, puede empeorar mucho.

R Samuel Klatchko
fuente
4

La especificación de C ++ no dice exactamente qué algoritmo debe usar para los contenedores STL. Sin embargo, impone ciertas restricciones a su rendimiento, lo que excluye el uso de tablas hash mapy otros contenedores asociativos. (Se implementan más comúnmente con árboles rojo / negro). Estas restricciones requieren un mejor rendimiento en el peor de los casos para estos contenedores que el que pueden ofrecer las tablas hash.

Sin embargo, muchas personas realmente quieren tablas hash, por lo que los contenedores asociativos STL basados ​​en hash han sido una extensión común durante años. En consecuencia, agregaron unordered_mapy demás a versiones posteriores del estándar C ++.

Warren Young
fuente
En realidad, se agregó en TR1 (std :: tr1 :: unordered_map), no en C ++ 0x
Terry Mahaffey
Pensé que la razón mapes que generalmente un árbol b balanceado se debe al uso operator<()como medio para determinar la ubicación.
KitsuneYMG
@kts: ¿Alguna implementación de STL realmente usa un árbol B?
bk1e
Técnicamente, todos los árboles de búsqueda binaria son árboles b (un árbol 1-2). Dicho esto, no conozco ningún STL que use algo más que rojo / negro
KitsuneYMG
@ bk1e Los árboles B "adecuados" son excepcionalmente útiles en las bases de datos, donde desea que los nodos de árbol "gordos" se alineen bien con las páginas del disco. OTOH, esto no es tan útil en el modelo de memoria "plano" usado en programas "normales" - todas las implementaciones STL que conozco usan árboles rojo-negro.
Branko Dimitrijevic
3

mapse implementa desde balanced binary search tree(generalmente a rb_tree), ya que todos los miembros de balanced binary search treeestán ordenados, por lo tanto, map;

hash_mapse implementa desde. hashtableDado que todos los miembros de hashtableno están ordenados, los miembros de hash_map(unordered_map)no están ordenados.

hash_mapno es una biblioteca estándar de c ++, pero ahora se le cambió el nombre a unordered_map(puede pensar en que se le cambió el nombre) y se convierte en una biblioteca estándar de c ++ desde c ++ 11 ver esta pregunta ¿ Diferencia entre hash_map y unordered_map? para más detalles.

A continuación, daré una interfaz básica del código fuente de cómo se implementa el mapa de dos tipos.

mapa:

El siguiente código es solo para mostrar que, map es solo un envoltorio de balanced binary search tree, casi toda su función es simplemente invocar la balanced binary search treefunción.

template <typename Key, typename Value, class Compare = std::less<Key>>
class map{
    // used for rb_tree to sort
    typedef Key    key_type;

    // rb_tree node value
    typedef std::pair<key_type, value_type> value_type;

    typedef Compare key_compare;

    // as to map, Key is used for sort, Value used for store value
    typedef rb_tree<key_type, value_type, key_compare> rep_type;

    // the only member value of map (it's  rb_tree)
    rep_type t;
};

// one construct function
template<typename InputIterator>
map(InputIterator first, InputIterator last):t(Compare()){
        // use rb_tree to insert value(just insert unique value)
        t.insert_unique(first, last);
}

// insert function, just use tb_tree insert_unique function
//and only insert unique value
//rb_tree insertion time is : log(n)+rebalance
// so map's  insertion time is also : log(n)+rebalance 
typedef typename rep_type::const_iterator iterator;
std::pair<iterator, bool> insert(const value_type& v){
    return t.insert_unique(v);
};

hash_map:

hash_mapse implementa a partir de hashtablecuya estructura es algo así:

ingrese la descripción de la imagen aquí

En el siguiente código, daré la parte principal de hashtabley luego daré hash_map.

// used for node list
template<typename T>
struct __hashtable_node{
    T val;
    __hashtable_node* next;
};

template<typename Key, typename Value, typename HashFun>
class hashtable{
    public:
        typedef size_t   size_type;
        typedef HashFun  hasher;
        typedef Value    value_type;
        typedef Key      key_type;
    public:
        typedef __hashtable_node<value_type> node;

        // member data is buckets array(node* array)
        std::vector<node*> buckets;
        size_type num_elements;

        public:
            // insert only unique value
            std::pair<iterator, bool> insert_unique(const value_type& obj);

};

Como map'ses rb_treeel hash_map'súnico miembro , el único miembro es hashtable. Es el código principal de la siguiente manera:

template<typename Key, typename Value, class HashFun = std::hash<Key>>
class hash_map{
    private:
        typedef hashtable<Key, Value, HashFun> ht;

        // member data is hash_table
        ht rep;

    public:
        // 100 buckets by default
        // it may not be 100(in this just for simplify)
        hash_map():rep(100){};

        // like the above map's insert function just invoke rb_tree unique function
        // hash_map, insert function just invoke hashtable's unique insert function
        std::pair<iterator, bool> insert(const Value& v){
                return t.insert_unique(v);
        };

};

La imagen de abajo muestra cuando un hash_map tiene 53 cubos e inserta algunos valores, su estructura interna.

ingrese la descripción de la imagen aquí

La siguiente imagen muestra alguna diferencia entre mapa y hash_map (unordered_map), la imagen proviene de ¿Cómo elegir entre mapa y unordered_map? :

ingrese la descripción de la imagen aquí

Jayhello
fuente
1

No sé qué da, pero hash_map tarda más de 20 segundos en borrar () 150K claves enteras sin firmar y valores flotantes. Solo estoy ejecutando y leyendo el código de otra persona.

Así es como incluye hash_map.

#include "StdAfx.h"
#include <hash_map>

Leí esto aquí https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap

diciendo que clear () es el orden de O (N). Eso para mí es muy extraño, pero así es.

BoBoDev
fuente