3 ms·
For an ultra simple hash table, you just need a few things (the following is from my head). First is a 'reasonable' hash function (although with a few more lin
by bArray 4y ago
For an ultra simple hash table, you just need a few things (the following is from my head).
First is a 'reasonable' hash function (although with a few more lines you can do better [1]):
unsigned int H(char* s){ int h; for(h = 0; *s; s++) h = ((h << 5) + h) + *s; return h; }
And then to build your hash table:
int L = <table length>; // Large enough to reduce collisions
char** t = (char**)malloc(L * sizeof(char*));
memset(t, 0, L * sizeof(char*)); // Set it all to empty by default
Then to use it:
/* Put example */
t[H("key string") % L] = "value string";
/* Get example */
char* v = t[H("some key") % L];
if(v) printf("value -> %s\n", v);
/* Remove example */
t[H("another key") % L] = NULL;
For them most part you can get pretty far with just this in C.
[1] https://coffeespace.org.uk/projects/hash-functions-part-2.html https://coffeespace.org.uk/projects/hash-functions-part-2.ht...
- anonymoushn 4y agoThis insert routine can destroy an unrelated key, so I'm not sure it's appropriate to call it a hash table.
- bArray 4y agoYou would of course check whether there is a collision if you care. You would size it such that a collision is low probability though.
- pca006132 4y agoGood luck when key collision happens and wrong value comes out causing errors in other part of your code...
- bArray 4y agoKey collisions are of course a problem. This is a quick and dirty implementation. If you care about checking for collisions, you could instead have: typedef struct{ char* k; char* v; } KV; int L = <table length>; // Large enough to reduce collisions KV* t = (KV*)malloc(L * sizeof(KV)); memset(t, 0, L * sizeof(KV)); // Set it all to empty by default Then: /* Put example (detect collisions) */ char* k; if(t[H(k) % L] == NULL || strcmp(t[H(k) % L].k, k) == 0) t[H(k) % L] = "value string"; else printf("Collision\n"); // Handle as you like Of course this can get more and more advanced. The point wasn't to make a zero-collision table, it was just something that could be used quickly.
- anonymoushn 4y agoThe point of the replies to your original comment is that it can't be used for most purposes, and writing all the code to make it usable results in something similar to the implementation in the article.
- bArray 4y agoHence why I wrote "For an ultra simple hash table". I think that for C that doesn't natively have such a data structure, a couple of lines to introduce such a structure really isn't too bad.
- zbird 4y agoIt's not clear what 'ultra simple' means. Could have just said that it doesn't handle collisions. And I think for most cases, you do want to handle collisions.