Looking for an array (vs linked list) hashtable implementation in C

Question

hi,

I'm looking for a hashtable implementation in C that stores its objects in (twodimensional) arrays rather than linked lists. i.e. if a collision happens, the object that is causing the collision will be stored in the next free row index rather than pushed to the head and first element of a linked list.

plus, the objects themselves must be copied to the hashtable, rather than referenced by pointers. (the objects do not live for the whole lifetime of the program but the table does).

I know that such an implementation might have serious efficiency drawbacks and is not the "standard way of hashing" but as I work on a very special system-architecture i need those characteristics.

thanks

Answer 1

My guess is your system does not allow for dynamic memory allocation. Therefore you will need to define up front array bounds that are reasonable for your data (number of total objects and maximum expected collisions) and additionally a custom hash function for your objects so it might be best to implement your own hash table.

Answer 2

It's not in C but in C++, but take a look at Google Sparse Hash - might give you some ideas. The key requirement is that the object being stored has a way to be null.

Answer 3

A super simple implementation:

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];

Don't forget to check against MAX_MEMORY.