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

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. — Daniel Bingham
– Daniel Bingham, Commented Apr 28, 2010 at 16:01

Andreas Brinck · Accepted Answer · 2010-04-28 16:09:44Z

6

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.

answered Apr 28, 2010 at 16:09

Andreas Brinck

52.9k15 gold badges87 silver badges114 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

mjh2007 · Accepted Answer · 2010-04-28 16:05:54Z

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.

answered Apr 28, 2010 at 16:05

mjh2007

7761 gold badge8 silver badges17 bronze badges

2 Comments

kingusiu Over a year ago

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!

caf Over a year ago

@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.

Nikolai Fetissov · Accepted Answer · 2010-04-28 16:07:33Z

0

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.

answered Apr 28, 2010 at 16:07

Nikolai Fetissov

84.6k13 gold badges118 silver badges175 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related