Complessità del tempo hashmap e c ++

“La complessità del tempo è il tempo di esecuzione relativo di qualche codifica. Prima di discutere la complessità del tempo di un hashmap, il lettore deve conoscere il ruolo di una funzione hash in una mappa hash.

In teoria, una funzione hash convertirebbe i dati di qualsiasi dimensione (qualsiasi testo di grandi dimensioni) in un numero intero maggiore o uguale a zero. Diversi testi grandi vengono convertiti in numeri diversi. L'interesse per questo articolo non è quello di convertire il testo di grandi dimensioni in un numero intero. L'interesse per questo articolo è mappare i dati di qualsiasi dimensione a un numero intero. Ciò include la possibilità di mappare (convertitura) un singolo numero in un altro singolo numero.

I dati (a sinistra) da mappare sono chiamati tasti. Quindi ogni chiave viene convertita in un numero intero uguale o maggiore di zero. Immagina che ci siano cinque chiavi che sono state convertite in numeri: 0, 1, 2, 3 e 4. Se queste chiavi sono gli indici di un array che detiene cinque valori dello stesso tipo, questi tasti sono stati mappati a cinque valori diversi.

E così, cos'è un hashmap (hash mappa)? Un hashmap è una struttura di dati costituita da coppie chiave/valore, in cui ogni chiave è stata mappata su un valore. In realtà, ogni chiave è stata hash in un numero di un array e la cella di array corrispondente è quella di contenere un valore. Nell'argomento HashMap, la posizione per la cella di ciascun indice di array è chiamata secchio."

Problema e risoluzione di collisione

In pratica, le chiavi diverse possono essere mappate su più di un valore. Considera il caso di dieci chiavi per un array di lunghezza 5, con 5 secchi. In questo caso, sarebbe stata costruita una struttura come una serie di array. Ogni secchio sarebbe effettivamente un array di lunghezza 2. Due chiavi condividono lo stesso secchio. In questa condivisione, la prima chiave mappare al primo elemento array per il secchio e la seconda chiave mappare al secondo elemento dell'array per lo stesso secchio. Questo schema risolve il problema delle collisioni e dieci chiavi sono state mappate a 10 valori, come previsto.

Per il resto di questo articolo, immagina un hashmap con il problema di collisione risolto. Lo scopo di questo articolo è fornire la complessità temporale della codifica per l'inserimento in un hashmap, la codifica per la cancellazione in un hashmap e la codifica per la ricerca in un hashmap. La complessità temporale per hashmap è descritta con queste tre caratteristiche. La mappatura hash per C ++ è anche affrontata in questo articolo.

Coppie chiave/valore e valori_type

Immagina un hashmap di nomi di persone contro i numeri di telefono per un elenco telefonico. I nomi degli utenti del telefono sono di tipo dati, testo (stringa). I valori dei numeri di telefono sono di tipo e testo, supponendo che spazi e/o trattini siano consentiti in un numero di telefono. I nomi utente sono le chiavi e i numeri di telefono sono i valori. Non dimenticare che, internamente, le chiavi vengono effettivamente convertite in indici di array nella struttura dei dati. Quindi, il tipo chiave è il testo e il tipo di valore è ancora testo.

Tipo di valore indica la coppia chiave/valore come elemento. In C ++, ogni elemento (coppia) è indicato da un iteratore. Quindi, in C ++, c'è anche una mappatura iteratrice/coppia. Una coppia (chiave e il suo valore) viene definita un tipo di valore.

Complessità temporale per l'inserimento di hashmap

La complessità del tempo per un hashmap non si riferisce al tempo impiegato per creare l'hashmap. Si riferisce al tempo impiegato per inserire, eliminare o cercare un valore basato su una determinata chiave. La complessità del tempo viene normalmente scritta usando la notazione Big-O. La notazione Big-O è costituita da O in maiuscolo, seguita da parentesi. Nelle parentesi ci sono variabili e numeri, che danno il tempo di esecuzione relativo per un pezzo di codice e non necessariamente l'intero programma. Con l'hashmap, k indica il numero di chiavi e n indica il numero di secchi. Ricorda che con alcune hashmaps, un secchio può avere più di un valore per chiavi corrispondenti. In questo caso, più di una chiave viene hash nello stesso indice del secchio. Una buona hashmap risolve questa collisione.

Inserimento

Data una nuova chiave, la complessità del tempo medio per avere la chiave e il valore corrispondente inserito in una struttura di dati hashmap è:

O (1 + N/K)

Dove n è il numero di secchi e k è il numero di chiavi. Ad esempio, n forse 10 e k forse 5. In questa particolare situazione, alcuni secchi sono vuoti (non hanno valore). Quindi, il numero di operazioni sarebbe, 1 + 10/5 = 1 + 2 = 3. Cioè, ci sarebbero 3 operazioni di codifica per inserire un elemento di coppia chiave/valore (data la chiave). Data una nuova chiave e valore, la complessità del tempo peggiore per avere la chiave e il suo valore corrispondente inserito in una struttura di dati hashmap è:

SU)

Dove n è il numero di secchi per n operazioni, se l'hashmap assume più di un valore per secchio per più di una chiave, allora qualsiasi tempo extra per inserire un ulteriore valore nello stesso secchio è trascurabile e trascurato.

Cancellazione

Dato una chiave già nella struttura dei dati hashmap, la cancellazione elimina l'elemento coppia chiave/valore. La complessità del tempo medio per la cancellazione è:

O (1 + N/K)

Dove n è il numero di secchi e k è il numero di chiavi. Ad esempio, n forse 10 e k forse 5. In questa particolare situazione, alcuni secchi sono vuoti (non hanno valore). Quindi, il numero di operazioni per il codice di eliminazione, sarebbe, 1 + 10/5 = 1 + 2 = 3. Quindi qui, ci sarebbero 3 operazioni di codifica per eliminare un elemento di coppia chiave/valore, data la chiave.

La complessità del tempo peggiore per la cancellazione, data una chiave, è:

SU)

Dove n è il numero di secchi, quindi, se ci sono n secchi per la struttura dei dati hashmap, al limite, ci vorrebbero 10 operazioni per eliminare un elemento di coppia chiave/valore nell'hashmap.

Ricerca

Ricerca significa trovare l'elemento della coppia chiave/valore che ha la chiave data, che dovrebbe già essere nell'hashmap. La complessità del tempo medio per questo è:

O (1 + N/K)

Con gli argomenti che hanno gli stessi significati di cui sopra. La complessità del tempo peggiore per questo è:

SU)

Con l'argomento che ha lo stesso significato di sopra.

C ++ 20

C ++ 20 ha una classe di hashmap? - Bene, sì, ma non con il nome, hashmap. C ++ 20 ha quattro contenitori associativi non ordinati, che sono diverse forme di classi di hashmap. I contenitori sono: UNORDERD_MAP, UNORDERD_MULTIMAP, UNORDED_SET e UNORDERD_MULISET. Questi contenitori associativi sono nella libreria standard C ++ 20. Il contenitore associativo da considerare in questo articolo è non ordinato_map. UNOrdined_Map utilizza una funzione hash predefinita fornita dalla libreria standard C ++.

Per includere l'intestazione non ordered_map in un programma, utilizzare la direttiva,

#includere

Non utilizzare #include, che includerà l'ordinamento_map. C ++ non prende #include . L'intestazione di UnOrderD_MAP porta la classe UNORDERD_MAP nel programma C ++.

Inserire con c++

Il seguente segmento di codice nella funzione principale C ++ inserirà un elemento di coppia chiave/valore (nome e numero di telefono) nell'oggetto UNORDERD_MAP, UMP:

#includere
UNORDERD_MAP UMP;
UMP.insert ("John Rambo", "555-5555");

Elimina con c++

La sintassi per eliminare un elemento di coppia chiave/valore da un oggetto non ordinato_map, data la chiave, k, è:

UN.Cancella (K)

Dove "a" è l'oggetto non ordinato_map (come l'ump sopra) e cancella () è la funzione membro non ordered_map.

Ricerca

La sintassi per cercare un elemento di coppia chiave/valore in un oggetto non ordinato_map, dato il tasto k, che dovrebbe essere già in un orderd_map, è:

B.Trova (k)

Dove b è l'oggetto non ordered_map (come l'ump sopra) e find () è la funzione membro non ordered_map.

Conclusione

Complessità temporale significa tempo di esecuzione relativo per un po 'di codice. Sebbene la complessità temporale per la creazione di un hashmap possa essere determinata, quando si tratta di hashmap, la complessità del tempo è per l'inserimento, l'eliminazione e la ricerca di attività. Le complessità di tempo medio e peggiore per un inserto hashmap ben definito sono:

O (1 + N/K)
SU)

Le complessità del tempo medio e peggiore per un'elimina hashmap ben definita sono:

O (1 + N/K)
SU)

Le complessità di tempo medio e peggiore per una ricerca di hashmap ben definita sono:

O (1 + N/K)
SU)