mapa vs hash mapa en C++

hash_map fue una extensión común proporcionada por muchas implementaciones de bibliotecas. Es exactamente por eso que se renombró a unordered_map cuando 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_map y unordered_map se implementan generalmente con tablas hash. Por lo tanto, el orden no se mantiene. unordered_map insert / delete / query será O (1) (tiempo constante) donde map será O (log n) donde n es el número de elementos en la estructura de datos. Así que unordered_map es más rápido, y si no le importa el orden de los elementos debe preferirse a map. A veces desea mantener el orden (ordenado por la clave) y para eso map sería la elección.

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

Un mapa requiere O(log(N)) tiempo para inserciones y hallazgos.

Un unordered_map requiere un tiempo 'promedio' de O(1) para inserciones y hallazgos, pero se le permite tener un tiempo en el peor de los casos de O(N).

Así que, por lo general, unordered_map será más rápido, pero dependiendo de las claves y la función hash que almacene, puede llegar a ser mucho peor.

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

Muchas personas realmente quieren tablas hash, sin embargo, por lo asociativo STL basado en hash los contenedores han sido una extensión común durante años. En consecuencia, agregaron unordered_map y tal a versiones posteriores del estándar C++.

No se lo que da, pero, hash_map toma más de 20 segundos para borrar() 150K claves enteras sin signo y valores flotantes. Estoy corriendo y leyendo el código de otra persona.

Así es como se incluye hash_map.

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

He leído 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í son las cosas.

map se implementa desde balanced binary search tree (generalmente un rb_tree), ya que todo el miembro en balanced binary search tree está ordenado así como map;

hash_map se implementa desde hashtable.Dado que todo el miembro de hashtable no está ordenado, los miembros de hash_map(unordered_map) no están ordenados.

hash_map no es una biblioteca estándar de c++, pero ahora se renombró a unordered_map (se puede pensar que se renombró) y se convierte en 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 central 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 una envoltura de un balanced binary search tree, casi toda su función es invocar la función balanced binary search tree.

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_map se implementa desde hashtable cuya estructura es algo así:

En el siguiente código, voy a dar la parte principal de hashtable, y luego da 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's solo el miembro es rb_tree, el hash_map's solo el 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 siguiente imagen muestra cuando un hash_map tiene 53 buckets, e inserta algunos valores, su estructura interna.

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