Come std :: unordered_map è implementato

Question

c++ unordered_map collision handling , resize and rehash

Questa è una domanda precedente aperti da me e ho visto che sto avendo un sacco di confusione su come unordered_map è implementato. Sono sicuro che molte altre persone condividono questa confusione con me. Sulla base delle informazioni che ho sapere senza leggere lo standard:

ogni implementazione unordered_map memorizza una lista concatenata per esterni nodi nella matrice di benne ... No, non è affatto il modo più efficiente per implementare una mappa hash per gli usi più comuni. Sfortunatamente, una piccola "supervisione" nelle specifiche di unordered_map richiede tutti questo comportamento. Il comportamento richiesto è che iteratori ad elementi devono rimanere valide durante l'inserimento o l'eliminazione di altri elementi

Speravo che qualcuno potrebbe spiegare l'attuazione e come esso corrisponde al C++ definizione standard (in termini di requisiti di prestazione) e se davvero non è il modo più efficiente per implementare una struttura dati della mappa hash come può essere migliorata?

Answer 1

Lo standard invia in modo efficace le implementazioni std::unordered_set e std::unordered_map che utilizzano l'hashing aperto, ovvero una serie di bucket, ognuno dei quali contiene la testa di un elenco logico (e tipicamente attuale). Questa esigenza è sottile: è una conseguenza del fatto che il fattore di carico massimo predefinito è 1.0 e la garanzia che la tabella non venga rehashed a meno che cresca oltre tale fattore di carico: sarebbe poco pratico senza concatenare, poiché le collisioni con hashing chiuso diventano schiaccianti fattore di carico tende a 1:

23.2.5/15: I insert e emplace membri non pregiudica la validità di iteratori se (N+n) < z * B, dove N è il numero di elementi nel contenitore prima l'operazione di inserimento, è n il numero di elementi inseriti, B è il numero di bucket del contenitore e z è il fattore di carico massimo del contenitore.

tra i Effetti del costruttore in 23.5.4.2/1: max_load_factor() rendimenti 1.0.

(Per consentire iterazione ottimale senza passare sopra i bucket vuoti, implementazione di GCC riempie i secchi con iteratori in un unico lista semplicemente legata tengono tutti i valori: iteratori indicano all'elemento immediatamente prima elementi di benna così, il prossimo puntatore non ci può essere riavvolto se cancellando ultimo valore della benna)

per quanto riguarda il testo si cita:.

No, non è affatto il modo più efficace per realizzare una mappa hash per più comuni utilizza. Sfortunatamente, una piccola "supervisione" nelle specifiche di unordered_map richiede tutto questo. Il comportamento richiesto è che gli iteratori agli elementi devono rimanere validi quando si inseriscono o eliminano altri elementi

Non c'è "supervisione" ... ciò che è stato fatto è stato molto deliberato e fatto con piena consapevolezza.È vero che altri compromessi avrebbero potuto essere raggiunti, ma l'approccio open hashing/concatenamento è un ragionevole compromesso per uso generale, che risponde in modo abbastanza elegante con collisioni da mediocri funzioni di hash, non è troppo dispendioso con tipi di chiavi/valori piccoli o grandi, e gestisce arbitrariamente molte coppie insert/erase senza degradare gradualmente le prestazioni come fanno molte implementazioni di hashing chiuse.

A testimonianza della consapevolezza, da Matthew Austern's proposal here:

Io non sono a conoscenza di alcun soddisfacente attuazione di indirizzamento aperto in un quadro generico. L'indirizzamento aperto presenta una serie di problemi:

• È necessario distinguere tra una posizione libera e una occupata.

• È necessario limitare la tabella hash ai tipi con un costruttore predefinito e costruire prima tutti gli elementi dell'array, oppure mantenere un array, alcuni dei quali sono oggetti e altri di memoria grezza.

• L'indirizzamento aperto rende difficile la gestione delle collisioni: se si inserisce un elemento il cui codice hash è mappato su una posizione già occupata, è necessario un criterio che indichi dove provare successivamente. Questo è un problema risolto, ma le soluzioni più note sono complicate.

• La gestione delle collisioni è particolarmente complicata quando è consentito cancellare elementi. (Vedi Knuth per una discussione.) Una classe contenitore per la libreria standard dovrebbe consentire la cancellazione.

• Gli schemi di gestione delle collisioni per l'indirizzamento aperto tendono ad assumere una matrice di dimensioni fisse che può contenere fino a N elementi. Una classe contenitore per la libreria standard dovrebbe essere in grado di crescere come necessario quando vengono inseriti nuovi elementi, fino al limite della memoria disponibile.

Risolvere questi problemi potrebbe essere un progetto di ricerca interessante, ma, in assenza di esperienza di implementazione nel contesto di C++, sarebbe inappropriato standardizzare una classe di contenitore di indirizzamento aperto.

In particolare per le tabelle di inserimento-solo con i dati abbastanza piccoli per memorizzare direttamente nei secchi, un valore sentinella conveniente per secchi non utilizzati, e una buona funzione di hash, un approccio hashing chiuso può essere più o meno un ordine di grandezza più veloce e usa molta meno memoria, ma questo non è uno scopo generale.

Un confronto completo e l'elaborazione di opzioni di progettazione tabella hash e le loro implicazioni è fuori tema per S.O. in quanto è troppo ampio per affrontare correttamente qui.