One of the things which I miss while writing programs in C is a dictionary data structure. What's the most convenient way to implement one in C? I am not looking for performance, but ease of coding it from scratch. I don't want it to be generic either — something like char*
→int
will do. But I do want it to be able to store an arbitrary number of items.
This is intended more as an exercise. I know that there are 3rd party libraries available which one can use. But consider for a moment, that they don't exist. In such a situation what's the quickest way you can implement a dictionary satisfying the above requirements.
Best Answer
Section 6.6 of The C Programming Language presents a simple dictionary (hashtable) data structure. I don't think a useful dictionary implementation could get any simpler than this. For your convenience, I reproduce the code here.
Note that if the hashes of two strings collide, it may lead to an
O(n)
lookup time. You can reduce the likelihood of collisions by increasing the value ofHASHSIZE
. For a complete discussion of the data structure, please consult the book.