Se non ci sono collisioni e ignoriamo il costo della CPU per l'hashing della chiave e non memorizziamo nessuno dei codici hash, l'hashtable consumerebbe la stessa quantità di spazio.
Tuttavia, in pratica, abbiamo collisioni, quindi abbiamo bisogno di un sistema per affrontarlo, che richiede più spazio. La maggior parte delle tabelle hash per la gestione della collisione dell'elenco collegato utilizza indici interi in array, anziché puntatori, per ridurre lo spazio e aumentare la località di memoria. Avrai bisogno di almeno un altro array, per il pool di strutture di elenchi collegati. Esistono molti algoritmi di gestione delle collisioni, ma richiedono tutti ulteriore spazio di archiviazione.
Se gli hash sono costosi da calcolare e le chiavi non memorizzano gli hash stessi, è necessario disporre di memoria aggiuntiva per memorizzare i codici hash.
Infine, devi occuparti di distribuzioni scadenti e funzioni di hash potenzialmente scadenti, se non hai il controllo sulle funzioni di hash. Le funzioni di hash in .net tendono ad essere particolarmente povere, e immagino che siano anche in Java, dal momento che le persone che scrivono la struttura chiave tipicamente devono scrivere la funzione hash e Internet abbonda di scarsi consigli in quest'area. Pertanto, puoi guardare avanti a distribuzioni scadenti, che comportano un numero elevato di collisioni e spazio aggiuntivo necessario per ridurre tali collisioni.