C++ - complessità unordered_map

Question

Devo creare una funzione di ricerca in cui una coppia (X, Y) corrisponde a un valore Z specifico. Uno dei requisiti principali è che ho bisogno di farlo nel modo più vicino possibile alla complessità di O (1). Il mio piano è di usare una mappa non ordinata.

Generalmente non uso una tabella hash per la ricerca, poiché il tempo di ricerca non è mai stato importante per me. Ho ragione nel ritenere che finché ho costruito la mappa non ordinata senza collisioni, il mio tempo di ricerca sarà O (1)?

La mia preoccupazione è quindi ciò che diventa la complessità se la chiave non è presente nella mappa non ordinata. Se per esempio utilizzo unordered_map :: find() :, per determinare se una chiave è presente nella mia tabella hash, come farò a darmi una risposta? In realtà esegue iterazioni su tutte le chiavi?

Apprezzo molto l'aiuto.

Answer 1

Lo standard più o meno richiede usando secchi per la risoluzione collisione , il che significa che l'attuale ricercare volta sarà probabilmente lineare rispetto al numero di elementi nel secchio , indipendentemente dal fatto che l'elemento è presente o non. È possibile renderlo O (lg N), ma di solito non lo è, perché il numero di elementi nel bucket deve essere piccolo, se la tabella hash viene utilizzata correttamente.

Per garantire che il numero di elementi in un bucket sia ridotto, è necessario che assicuri che la funzione di hashing sia effettiva. I mezzi efficaci dipendono dai tipi e dai valori sottoposti a hash. (L'implementazione MS utilizza FNV, che è uno dei migliori hash generici in giro, ma se si dispone di una conoscenza speciale dei dati effettivi che si vedranno, si potrebbe essere in grado di fare meglio.) Un'altra cosa che può ridurre il numero di elementi per il bucket è forzare più bucket o utilizzare un fattore di carico più piccolo. Per il primo, è possibile passare il numero iniziale minimo di bucket come argomento al costruttore. Se conosci il numero totale di elementi che saranno nella mappa, puoi controllare il fattore di carico in questo modo. È anche possibile prevedere un numero minimo di bucket una volta che il tavolo è stato riempito, chiamando rehash. Altrimenti, c'è una funzione std::unordered_map<>::max_load_factor che puoi usare. È non è garantito per fare nulla, ma in qualsiasi ragionevole implementazione, lo farà. Si noti che se lo si utilizza su uno già riempito, probabilmente sarà necessario chiamare unordered_map<>::rehash in seguito.

(Ci sono diverse cose che non capisco sullo standard unordered_map: il motivo per cui il fattore di carico è un float, invece di double, perché non è necessario per avere un effetto, e il motivo per cui non lo fa automaticamente chiamare rehash per voi)

Answer 2

Come per ogni tabella di hash, caso peggiore è sempre la complessità lineare (Edit: se hai costruito la mappa senza collisioni, come lei ha dichiarato nel post originale, quindi non vedrai mai questo caso):

http://www.cplusplus.com/reference/unordered_map/unordered_map/find/

Complessità caso medio: costante. Caso peggiore: lineare nella dimensione del contenitore.

Valore restituito Un iteratore all'elemento, se viene trovato il valore della chiave specificata, o unordered_map :: fine se la chiave specificata non si trova nel contenitore.

Tuttavia, perché un unordered_map può contenere solo chiavi univoche, si vedrà la complessità media di tempo costante (container primi controlli indice hash, e quindi itera sui valori in tale indice).

penso che la documentazione per unordered_map::count funzione è più informativo:

Ricerche contenitore per gli elementi la cui chiave è k e restituisce il numero di elementi trovati . Poiché i contenitori unordered_map non consentono di consentire chiavi duplicate, ciò significa che la funzione in realtà restituisce 1 se un elemento con quella chiave esiste nel contenitore e lo zero altrimenti.

Answer 3

Per non avere collisioni in una struttura di dati con hash è incredibilmente difficile (se non impossibile per una determinata funzione di hash e qualsiasi tipo di dati). Richiederebbe anche una dimensione della tabella esattamente uguale al numero di chiavi. No, non ha bisogno di essere così severo. Finché la funzione hash distribuisce i valori in modo relativamente uniforme, avrai una complessità di ricerca pari a O(1).

Le tabelle di hash sono in genere solo array con elenchi concatenati che si occupano delle collisioni (questo è il metodo di concatenamento - ci sono altri metodi, ma questo è probabilmente il modo più utilizzato per gestire le collisioni). Quindi, per scoprire se un valore è contenuto in un bucket, dovrà (potenzialmente) iterare su tutti i valori in quel bucket. Quindi, se la funzione di hash ti offre una distribuzione uniforme e ci sono i bucket N e un totale di valori M, dovrebbero esserci (in media) valori di M/N per bucket.Finché questo valore non è troppo grande, ciò consente la ricerca di O(1).

Così, come un po 'una risposta a lungo senza fiato alla tua domanda, fino a quando la funzione di hashing è ragionevole, si otterrà O(1) ricerca, con esso dover iterare (in media) O(M/N) tasti per dare una " negativo "risultato.