hset doesn't allow you to overwrite old entries. But you can do it manually with hget.
15-line hash table in C
21–30 of 104 posts
Re: 15-line hash table in C
#22People understand that the compiler/executable doesn't run any faster the less newlines there are, right? This is cute, but as others have pointed out it, it isn't really a correct implementation of a hash table. Also, it wouldn't pass a code review anywhere I've ever worked.
>People understand that the compiler/executable doesn't run any faster the less newlines there are, right?
As much as others understand that it's not like this is some obsfuscated thing with some bizarro code that eats newlines for breakfast.
Merely avoids 4-5 newlines anybody can easily add, only affecting 1 or 2 statements each. With newlines expanded it would still as small as it is.
Re: 15-line hash table in C
#23Re: 15-line hash table in C
#24Won’t hget() easily run off the end of the array if it has a few collisions? The function doesn’t save off the original value of t and then does an unbounded number of (t += h) operations.
edit: someone else pointed this out already. How did this make it to the front page of HN?
Re: 15-line hash table in C
#25There's no bounds testing in hget(): some valid sequences of operations will cause buffer overflows. For example, this should segfault: int (**table)[2] = hnew(); for (int j=0; j The problem is, the probing function doesn't wrap (the "t += h" part), so if you have have several colliding keys, it will probe for them past the end of the table.
Yeah... it’s easy to write small code that doesn’t work.
Re: 15-line hash table in C
#26will need the clockwise spiral rule to parse this: http://c-faq.com/decl/spiral.anderson.html
The author helpfully explains the code by way of un-optimizing it to something readable: http://pastes.archbsd.net/graphitemaster/hashtable_explinati...
see why couldn't the code be written this way by default! then they would've been understandable from the beginning!
Re: 15-line hash table in C
#27If you rewrote this exact logic in Python it would be longer, because then the code would actually be readable.
However, fortunately it's just two chars: {}
Re: 15-line hash table in C
#28Earlier quoted context omitted.
The problem with that method is that it doesn't have data access locality, while linear probing does. Linear probing ends up being more efficient because it is easy on the cache.
It seems to me this would only be true if the keys that collide are related to each other, or you have a vastly oversized table that you collide a lot in, at which point you're just accidentally synthesizing a smaller table. What am I missing here? [edit] I guess the other situation would be if the keys are largely sequential, but then a hash table seems like an odd choice of data structure.
Let's say you get a collision. Would you rather:
a) Find your correct key within the same cache-line. But, you have to check 4 more values to get there;
b) Find your correct key in the next try...But, you have to jump to another part of the array.
Once you've indexed into the array, you want to read forward from there. You don't want to jump around.
http://preshing.com/20130107/this-hash-table-is-faster-than-...
Re: 15-line hash table in C
#29Earlier quoted context omitted.
The problem with that method is that it doesn't have data access locality, while linear probing does. Linear probing ends up being more efficient because it is easy on the cache.
It seems to me this would only be true if the keys that collide are related to each other, or you have a vastly oversized table that you collide a lot in, at which point you're just accidentally synthesizing a smaller table. What am I missing here? [edit] I guess the other situation would be if the keys are largely sequential, but then a hash table seems like an odd choice of data structure.
[deleted]
Re: 15-line hash table in C
#30just think how amazing and readable it could be in 100 lines