15-line hash table in C
pastes.archbsd.net
pastes.archbsd.net
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.
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.
Well that's the whole point, right? This is clearly written for fun, it's not production code, it's not supposed to pass a code review. It's just supposed to be cool and interesting, and a challenge for the author.
[0] - http://lelandbatey.com/posts/2014/09/binary-tree-printer/
int (**table)[2] = hnew();
for (int j=0; j<40; ++j) {
hset(table, (10 + j*SIZE), 0);
}
... & (SIZE - 1)
You need a temporary variable of
int (**)[2]
https://gist.github.com/pwr22/a08597e475d1aa44cd96
It will still fail looking up a non-existent key, which I don't understand
In C99 it's allowed to declare in the loop preamble. True for ANSI-C.
It wouldn't be C if that wasn't the case.
h = k & (SIZE - 1)I will not understand how and why people's egos get threatened by things like this.
In my experience more lines == reduced readability, more difficult to move around, more difficult to fix single parts (any change requires to modify many files) and so on. More lines of code is often against the simplicity.
I have seen code that was very difficult to understand. Rewriting it to make it simple never needed to increase the number of lines.
Whenever someone brings up the "cleverness" argument I always like to mention this counterpoint: http://www.linusakesson.net/programming/kernighans-lever/
Disagree. There's a sweet spot. Code that is too dense (golfing code) is unreadable but so is code that's too long. Long code can be readable if the substructure is evident, but it's usually not.
There are two issues that come to mind on this. One is that concise code usually requires strong familiarity with the language. For example, Haskell allows dense and readable code-- if you know Haskell. Same with Clojure (Lisp). I hate Java, but one thing I'll say for it and its sprawling code is that it's relatively easy to (superficially?) understand (with an IDE to jump around, because modest programs can be thousands of lines) with a mediocre knowledge of the language.
I'd say the same of research-level mathematics. If you're intimately familiar with linear algebra notation and terminology because you use it every day, it's concise and readable. If not, then "(X^TX)^(-1)Xy" looks like line noise.
The second issue is that what tends to make large codebases unreadable is a failure of factoring. It's not that it's 500 lines* that is the problem, because the intrinsic complexity of the problem may be at a level where 400-500 lines is appropriate. It's when you have 500 lines in one class (ultimately, "class" and "object" are poorly-defined and that's why so much OOP code is trash) or, worse yet, one function/method (method is just a code-name for "locally interpreted stateful function") that you get hell code. This happens a lot in large imperative codebases (typically not becoming intractable until you have two or more programmers on the same code) because, in imperative code where an action (as opposed to stateless function) is the fundamental unit, things appear to compose better than they actually do.
In other words, it's complicated. In general, there seems to be a density level that accurately represents the intrinsic complexity of the problem. Go denser and you're forcing people to think in a specific (and poorly communicated) way to understand the implicit structure and policies that informed the code construction. On the other hand, typical sprawling Java code is great for testing your IDE's scrolling feature but the amount that can fit on a single page is low, and if this is coupled with long methods and huge classes, you get OOP (here, meaning "business OOP", not "Alan Kay's vision of OOP") spaghetti code.
maybe the downvote is ok - im not grokking the essence of it - but similar bits of code written in perl are notorious jokes.
// corrected overflow hget
for (int k2=k,o=0; t[k&(SIZE-1)] && **t[k&(SIZE-1)] != k2 && o<SIZE; ++k,++o);
return t+(k&(SIZE-1));
for (int (**a)[2] = hget(t, k); a && (*a || (*a=malloc(sizeof(**t)))); (**a)[0]=k,(**a)[1]=v,a=0);1: Implement an algorithm in a very concise and straightforward, even if not very efficient, way. An example is the classic quicksort in Haskell, which most literally implements the idea of the algorithm:
qsort [] = []
qsort (p:xs) = qsort [ y | y <- xs, y < p ] ++ [p] ++
qsort [ y | y <- xs, y >= p ]
The linked hashtable implementation, to my mind, is neither very elegant nor fiendishly clever, nor even reasonably correct.
Also, even in examples of super efficient ways, be wary. The inverse square root you are referring to is actually slower than what many CPUs can do with a single instruction nowdays.
Also, I think you are missing out on the main reason this code was written. Essentially a puzzle to see if it can be done.
[1]: http://attractivechaos.github.io/klib/#Khash%3A%20generic%20...
http://webcache.googleusercontent.com/search?q=cache:V51nbJE...
(Cache link since original post is 500.)
Why is this better than an array of structs ? How much longer can that be ?
However, fortunately it's just two chars: {}
int (**hnew())
int **hnew() typedef int arr2int[2];
typedef arr2int** ptr_arr2int;
#define SIZE 1024
static ptr_arr2int hnew() {
return calloc(sizeof(int**), SIZE);
}Perhaps this is what is desired (fixing roll over issue as well):
static int (**hget(int (**t)[2], int k))[2] {
int (**t_old)[2] = t;
int h = k & (SIZE - 1);
for (t = t + h; **t && ***t != k;
h = ((h + 1) & (SIZE - 1)), t += h, t = t_old + ((t - t_old) & (SIZE - 1)));
return t;
}edit: someone else pointed this out already. How did this make it to the front page of HN?
Also since keys are integers, how this would be useful? Isn't the same that a regular array?
If I managed to understand it correctly, it is because t is an array, and arrays are special.
t is a pointer to an array, i.e. it points to the first element of the array. t is an array, which means it behaves like a pointer to the first element.
The remarkable consequence of this is that t and t have the same numerical value, but different types. t==t evaluates to true.
Also, sizeof(int star-star) in hnew should be sizeof( int (star)[2] ).
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.
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-...
This model plays nicely with the cache, although its downside is there tend to be more "runs" of contiguous filled slots in the hash table. This method still provably takes an expected insert/lookup time of O(1) with a 5-wise independent hash function and a load factor smaller than 1.
But now I see where the confusion lies. I was taking your post to be replying more to the hash function part of the GP, but you were talking specifically about the skip distance. Yes, now I see what you mean, and I'm not actually sure how I misinterpreted so badly in the first place.
edit: clarity.
That's what I wanted to point, and I agree that it remains useful to detect other types of errors such as the ones you mentioned.
target_row_number = table_height % int_value_of_key
If table height keeps changing then this formula would be inconsistent. This code isn't using % but kind of doing the same using &
Replace (int)[2] with table_row :)
Mainly because they are simple, and lot of problems are solvable by using them without resorting to Someone Elses Gigantic Platform Framework.
So, no... and yes. You can call yourself a software engineer without knowing any of this stuff, but you will be a better one if you do.
Programming isn't about learning how to create specific things. But learning how to create specific things can help you gain the intuition necessary to create other things.
Consider "<Foo> in <bar> lines" type articles to be performance pieces - the point is to make it short, not readable or user friendly.