map vs. hash_map in C++

map vs. hash_map in C++

Sono implementati in modi molto diversi.

hash_map (unordered_map in TR1 e Boost; usa quelli invece) usa una tabella hash in cui la chiave viene sottoposta a hash in uno slot nella tabella e il valore viene archiviato in un elenco legato a quella chiave.

map è implementato come un albero di ricerca binario bilanciato (solitamente un albero rosso/nero).

Un unordered_map dovrebbe fornire prestazioni leggermente migliori per l'accesso a elementi noti della raccolta, ma un map avrà caratteristiche utili aggiuntive (ad esempio è memorizzato in ordine, che consente l'attraversamento dall'inizio alla fine). unordered_map sarà più veloce da inserire ed eliminare rispetto a un map .


hash_map era un'estensione comune fornita da molte implementazioni di librerie. Questo è esattamente il motivo per cui è stato rinominato in unordered_map quando è stato aggiunto allo standard C++ come parte di TR1. map è generalmente implementato con un albero binario bilanciato come un albero rosso-nero (le implementazioni variano ovviamente). hash_map e unordered_map sono generalmente implementati con tabelle hash. Pertanto l'ordine non viene mantenuto. unordered_map inserimento/cancellazione/interrogazione sarà O(1) (tempo costante) dove mappa sarà O(log n) dove n è il numero di elementi nella struttura dati. Quindi unordered_map è più veloce e se non ti interessa l'ordine degli articoli dovrebbe essere preferito a map . A volte vuoi mantenere l'ordine (ordinato dalla chiave) e per quel map sarebbe la scelta.


Alcune delle differenze principali risiedono nei requisiti di complessità.

  • Un map richiede O(log(N)) tempo per le operazioni di inserimento e ricerca, poiché è implementato come un albero rosso-nero struttura dei dati.

  • Un unordered_map richiede un tempo "medio" di O(1) per inserimenti e reperti, ma può avere un tempo peggiore di O(N) . Questo perché è implementato utilizzando Tabella hash struttura dei dati.

Quindi, di solito, unordered_map sarà più veloce, ma a seconda delle chiavi e della funzione hash che memorizzi, può peggiorare molto.