Ricerca di un'implementazione di hashtable di array (vs elenco collegato) in C

Question

Sto cercando un'implementazione di hashtable in C che memorizza i suoi oggetti in array (bidimensionali) anziché in elenchi collegati. Ad esempio, se si verifica una collisione, l'oggetto che sta causando la collisione verrà memorizzato nel successivo indice di riga libera anziché spinto alla testa e al primo elemento di una lista collegata.

In più, gli oggetti stessi devono essere copiati nella tabella hashtable, anziché fare riferimento ai puntatori. (gli oggetti non vivono per l'intera vita del programma ma la tabella lo fa).

So che un'implementazione di questo tipo potrebbe avere seri problemi di efficienza e non è il "metodo standard di hashing", ma poiché lavoro su un'architettura di sistema molto speciale ho bisogno di quelle caratteristiche.

grazie

Answer 1

Un super semplice implementazione:

char hashtable[MAX_KEY][MAX_MEMORY]; 
int counts[MAX_KEY] = {0}; 

/* Inserting something into the table */ 
SomeStruct* some_struct; 
int hashcode = compute_code(some_struct); 
int size = sizeof(SomeStruct); 
memcpy(hashtable[hashcode] + counts[hashcode] * size, some_struct, size); 
++counts[hashcode]; 

Non dimenticare di controllare contro MAX_MEMORY.

Answer 2

La mia ipotesi è che il sistema non consenta l'allocazione dinamica della memoria. Pertanto, sarà necessario definire limiti di array frontali ragionevoli per i dati (numero di oggetti totali e collisioni massime previste) e inoltre una funzione di hash personalizzata per i propri oggetti, quindi potrebbe essere meglio implementare la propria tabella hash.

Answer 3

Non è in C ma in C++, ma date un'occhiata a Google Sparse Hash - potrebbe darvi qualche idea. Il requisito fondamentale è che l'oggetto da memorizzare abbia un modo di essere null.