Perché abbiamo bisogno di strutture dati diverse da HashMap

1. La mappa hash ha un tempo costante per la maggior parte delle operazioni, in media. La complessità del caso peggiore è molto più alta. Un elenco o un albero può garantire tempi rapidi (anche se non costanti) in ogni caso (anche per input maliziosamente elaborati).
2. La ricerca di elementi in un array è solitamente una singola istruzione della CPU. La mappa hash aggiunge un sovraccarico su questo, anche se entrambi hanno una complessità media costante.
3. Non mantiene alcun ordine di elementi. L'inserimento di elementi in una particolare posizione richiede la ricostruzione di una intera mappa di hash. L'iterazione degli elementi in un ordine particolare richiede la conversione in una struttura dati diversa.
4. La mappa hash ha un ingombro di memoria molto più elevato rispetto a un array compatto o una lista concatenata accuratamente progettata. Di solito ha una localizzazione cache molto peggiore.
5. Non tutti i tipi di dati sono facilmente lavabili.

Ad esempio, array e hashmap hanno entrambi un tempo di accesso costante (in media). Tuttavia, per un array la costante è molto, molto più piccola. E per un array, l'utilizzo della memoria è molto più piccolo, perché una mappa di hash memorizzerebbe anche gli indici, e ha molti slot inutilizzati (perché l'hashing rallenta la percentuale di slot usati diventa troppo alta).

E poi ci sono le istruzioni vettoriali. Un moderno processore Intel può leggere 8 valori float o 32 valori byte da una matrice in una singola istruzione. Quei valori a 32 byte dovrebbero passare attraverso il codice di hashing (a tempo costante ma lento) 32 volte. Direi che ti darebbe facilmente un fattore 1000 per il rallentamento totale.