So solo che la differenza tra hashmap e map è che hashmap è implementato con la funzione hash ma la mappa è implementata con tree. Qualcuno potrebbe aggiungere qualcosa di più?C'è qualche cosa che l'hashmap può fare, ma la mappa non può?
In base a ciò, c'è qualche cosa che hashmap può fare, ma la mappa non può?
Le mappe di hash hanno prestazioni medie migliori per l'accesso (O (1)), ma prestazioni peggiori peggiori (O (n)). Le mappe sono sempre O (lg (n)).
Le mappe sono ordinate tramite la loro chiave, le hashmap non lo sono.
Le mappe di hash utilizzano generalmente più memoria delle mappe.
Le mappe consentono in genere una iterazione più rapida.
Le buone funzioni di hash sono più difficili da scrivere rispetto alle funzioni di ordinamento (e più difficili da analizzare).
Non credo che ci sia qualcosa che una mappa di hash può fare che una mappa non può.
Le mappe di hash utilizzano generalmente anche più memoria. – GManNickG
IMO la richiesta O (1) per le tabelle hash è un po 'un trucco. C'è un limite fisso al numero di chiavi riconosciute come distinte senza la gestione delle collisioni e una volta che si verificano collisioni, le prestazioni peggiorano a quelle della gestione della collisione (spesso O (n)). OK, l'hash ha tradizionalmente supportato il numero di chiavi univoche che è possibile memorizzare in memoria in ogni caso, ma mi chiedo quante persone abbiano trascurato di aggiornare i calcoli di hash personalizzati da 32 bit a 64 bit e otterrà la degredation delle prestazioni con tabelle hash molto grandi. La tabella hash di dimensioni non risolve quella se l'hash stesso è troppo stretto. – Steve314
@Steve - Ho detto che O (1) era nel caso medio e O (n) era il caso peggiore. @GMan - Grazie, lo aggiungo. –
Una mappa richiede che la chiave abbia un severo ordinamento debole, che forse potrebbe non esistere. Una hashmap ha solo bisogno di una funzione hash. Quindi in questo modo si può usare una hashmap con chiavi che non hanno un severo ordine debole.
Per essere onesti, alberi e hashmap hanno uguali problemi qui. È un problema che ho dovuto affrontare di recente con l'utilizzo di strumenti automatici finiti come chiavi. Non si può semplicemente fare un hash (o confronto) della rappresentazione in memoria perché gli automi equivalenti possono avere rappresentazioni differenti. La soluzione è derivare una forma canonica. Una volta che hai una forma canonica, puoi lavorare ugualmente bene con le rappresentazioni in memoria, che tu stia confrontando o eseguendo operazioni di hashing, e questo vale per qualsiasi tipo di dati. Se riesci ad eseguire l'hash, puoi facilmente definire un ordinamento arbitrario ma coerente. – Steve314
Un vantaggio che le hashmap hanno sugli alberi è che, in un ambiente multi-threading, non è necessario bloccare l'intero contenitore per aggiungere o rimuovere una singola chiave - il blocco della singola voce rilevante nella tabella hash è (quasi) abbastanza.
Quasi perché potrebbero esserci dei metadati (numero di elementi nella tabella hash, ad esempio) da aggiornare. E probabilmente hai bisogno di bloccare l'intero tavolo per ingrandirlo o restringerlo, ovviamente.
Un po 'simile, forse non un dupe però: http://stackoverflow.com/questions/2196995/is-there-any-advantage-of-using-map-over-unordered-map-in-case-of- -trivial-keys/ – GManNickG
Sii un po 'attento con la terminologia. In alcune cerchie, una "mappa" si riferisce solo a un oggetto che svolge funzioni di archiviazione e ricerca di chiavi/valori e una "mappa di hash" è un'implementazione di una mappa. (Dove una mappa ad albero potrebbe essere un'altra.). IOW, "map" è un'interfaccia e "map hash" è un'implementazione concreta. (Questo è il motivo per cui la tua domanda non è contrassegnata come o si riferisce a una particolare libreria.) –
@ Ben: In C++ 'map' si riferisce quasi inequivocabilmente a' std :: map', un albero. – GManNickG