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

Question

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

Dutra

Since you have such unusual and specific requirements for its implementation, I would wager your best shot would be to write such an implementation yourself. – Cosmopolitan

+1, an interesting question nonetheless. – Torrietorrin

Answer 1

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.

Lamar

Answer 2

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.

Cromer

dynamic memory allocation is allowed, but the system is a multicore-architecture that works best if the shared data is stored in contiguous memory, that's why I want to use arrays. to calculate the maximum expected collisions is a good hint, thanks! – Dutra

@kingusiu: A normal linked list chaining hash might work for you if you put it together with a pool allocator, so that all the objects are being allocated out of one contiguous pool. The forward and back links wouldn't even have to be pointers - they could just be pool indexes. – Cheju

Answer 3

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.

Lancashire