Menu
what is a good hashtable implementation for C? I need to use it with mpicc compiler. Delete function is not necessary.
507
A fast hash map/hash table (whatever you want to call it) for the C programming language. It can associate a key with a pointer or integer value in O(1) time.
Hash tables are used to implement map and set data structures in most common programming languages. In C++ and Java they are part of the standard libraries, while Python and Go have builtin dictionaries and maps. A hash table is an unordered collection of key-value pairs, where each key is unique.
What is Hash Function? The hash function is a function that uses the constant-time operation to store and retrieve the value from the hash table, which is applied on the keys as integers and this is used as the address for values in the hash table.
Hash table is a data structure that can map keys to values. A hash table uses a hash function to compute a key into an integer (hash value), which indicates the index of the buckets (aka array). From the key, the correct value can be stored and found.
The one in glib is very nice. Not sure if it's too large and/or possible to isolate from the rest of glib, though.
Failing that, Pearson hashing seems to be a good starting point for implementing your own (it's a hash function optimized for machines with 8-bit registers).
197
If the keys are all known in advance, you may use a perfect hash generator avoid the space overhead that is implicit in hash tables.
If, on the other hand, you really need a full hash table, I would suggest a variation of Cuckoo Hashing (e.g. the d-ary version).
I've used with satisfaction a simplified version of the Hopscotch Hashing that works rather well even at higher load factors.
40
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
