Perché la mappa dovrebbe essere molto più veloce di unordered_map?

Perché la mappa dovrebbe essere molto più veloce di unordered_map?

La velocità di unordered_map è direttamente proporzionale alla velocità della tua funzione di hashing. Non è mai una relazione diretta. Caso in questione, se utilizzi la funzione di hashing più semplice:

std::size_t myHash(MyObjectType _object){ return 1; }

quindi ciò che ti ritroverai è una raccolta che si comporta come un elenco anziché come un contenitore con hash. Tutti gli elementi verranno mappati su un singolo secchio e dovrai attraversare l'intero secchio fino a raggiungere l'elemento desiderato (cosa che potrebbe richiedere del tempo O(N).)

Quello che devi fare è guardare due cose:

  1. Quale funzione di hashing stai utilizzando? Costa una quantità di tempo ridicola per l'elaborazione?
  2. Quante collisioni sta producendo? Cioè, quanti elementi univoci vengono mappati allo stesso valore hash?

Ognuno di questi da soli può e ucciderà la performance.


std::unordered_map è comunemente lento per un numero limitato di elementi a causa della funzione hash. Ci vuole una quantità di tempo fissa (-ish), ma forse una quantità di tempo significativa comunque.

std::map d'altra parte è più semplice di std::unordered_map . Il tempo necessario per accedere a un elemento lì dipende dal conteggio degli elementi, ma sempre meno all'aumentare del numero di elementi. E il fattore big-oh c per uno std::map è comunemente anche molto piccolo, rispetto a std::unordered_map .

In generale, preferisci usare std::map oltre std::unordered_map , a meno che tu non abbia un motivo specifico per utilizzare std::unordered_map . Ciò vale in particolare se non si dispone di un numero elevato di elementi.


unordered_map usa una tabella hash sotto il cofano, quindi il motivo più ovvio per cui l'hash funziona male è perché hai troppe collisioni. Potresti prendere in considerazione l'utilizzo di una funzione hash diversa, non predefinita, che darà risultati migliori per il tuo tipo di chiavi.