Salterò con una risposta prevenuta dove in realtà preferisco il concatenamento separato con elenchi collegati singolarmente e lo trovo più semplice per ottenere prestazioni con loro (io sono non dicendo che sono ottimali, solo più facili per i miei casi d'uso), in quanto contraddittorio come sembra.
Ovviamente l'optimum teorico è ancora una tabella hash senza collisioni di sorta o una tecnica di sondaggio con clustering minimo. Tuttavia, la soluzione di concatenazione separata non deve necessariamente affrontare problemi di clustering.
Detto questo, la rappresentazione dei dati che utilizzo non richiama un'allocazione di memoria separata per nodo. Eccolo in C:
struct Bucket
{
int head;
};
struct BucketNode
{
int next;
int element;
};
struct HashTable
{
// Array of buckets, pre-allocated in advance.
struct Bucket* buckets;
// Array of nodes, pre-allocated assuming the client knows
// how many nodes he's going to insert in advance. Otherwise
// realloc using a similar strategy as std::vector in C++.
struct BucketNode* nodes;
// Number of bucket heads.
int num_buckets;
// Number of nodes inserted so far.
int num_nodes;
};
I bucket sono solo indici a 32 bit (non utilizzo nemmeno una struct in realtà) ei nodi sono solo due indici a 32 bit. Spesso non ho nemmeno bisogno dell'indice element perché i nodi sono spesso memorizzati in parallelo con la matrice di elementi da inserire nella tabella, riducendo il sovraccarico della tabella hash a 32-bit per bucket e 32-bit per elemento inserito. La versione reale che uso più spesso assomiglia a questa:
struct HashTable
{
// Array of head indices. The indices point to entries in the
// second array below.
int* buckets;
// Array of next indices parallel to the elements to insert.
int* next_indices;
// Number of bucket heads.
int num_buckets;
};
Anche se la località spaziale si degrada, posso facilmente eseguire un passaggio di post-elaborazione in cui costruisco una nuova tabella hash in cui ciascun nodo del bucket è contiguo all'altro (funzione di copia banale che esegue semplicemente un passaggio lineare attraverso la tabella hash e i costrutti uno nuovo - a causa della natura in cui attraversa la tabella hash, la copia finisce con tutti i nodi vicini in un secchio contiguo tra loro).
Come per le tecniche di sondaggio, viene fornito con i vantaggi che la località spaziale è già lì dall'inizio senza pool di memoria o un backing array come io uso, e inoltre non hanno l'overhead a 32 bit per bucket e node , ma poi potresti dover affrontare problemi di clustering che possono iniziare ad accumularsi in modo vizioso con molte collisioni.
Trovo che la natura stessa del clustering sia un mal di testa che richiede molte analisi in caso di molte collisioni. Il vantaggio di questa soluzione è che posso ottenere spesso un risultato decente la prima volta senza analisi e test così approfonditi. Anche se la tabella si ridimensiona da sola in modo implicito, mi sono imbattuto in casi in cui tali progetti hanno finito per far esplodere l'utilizzo della memoria in modi che superano di gran lunga ciò che questa soluzione base che richiede un 32 bit per bucket e 32 bit per nodo anche nello scenario peggiore. È una soluzione che evita di diventare troppo male anche se ci sono un certo numero di collisioni.
La maggior parte della mia base di codice ruota intorno a strutture di dati che memorizzano indici e spesso memorizzano indici in parallelo con la matrice di elementi da inserire. Questo riduce le dimensioni della memoria, evita copie superflue e profonde degli elementi da inserire e rende molto facile ragionare sull'utilizzo della memoria. A parte questo, nel mio caso tendo a trarre beneficio dalle prestazioni prevedibili come prestazioni ottimali. Un algoritmo che è ottimale in molti scenari di casi comuni ma può funzionare in modo orribile negli scenari del caso peggiore è spesso meno preferibile per me rispetto a uno che funziona abbastanza bene tutto il tempo e non causa il rallentamento dei frame rate in momenti imprevedibili, e quindi tendono a favorire questo tipo di soluzioni.