This code reminds me why clever is the enemy of good.
[deleted]
15-line hash table in C
11–20 of 104 posts
Re: 15-line hash table in C
#12C++ wins again.
Re: 15-line hash table in C
#13Is this some common style?
int (**hnew())
int **hnew()Re: 15-line hash table in C
#14Is this some common style? int (**hnew()) I've never seen parens used like that. Usually it's: int **hnew()
Might be to fix some -pedantic issue.
Re: 15-line hash table in C
#15People 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.
Re: 15-line hash table in C
#16A small improvement could be to hash the key using a prime multiplier and successive multiplications, instead of using the key and increments of one. It'd reduce the collisions at the expense of a more computationally expensive hash function.
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.
Re: 15-line hash table in C
#17Is this some common style? int (**hnew()) I've never seen parens used like that. Usually it's: int **hnew()
parens are used since the [2] is on the end. Otherwise, it would think its a pointer to a pointer of an int [2] -> (hnew()[2]).
Re: 15-line hash table in C
#18Is this some common style? int (**hnew()) I've never seen parens used like that. Usually it's: int **hnew()
[deleted]
Re: 15-line hash table in C
#19Is this some common style? int (**hnew()) I've never seen parens used like that. Usually it's: int **hnew()
[deleted]
Re: 15-line hash table in C
#20This doesn't seem to use the hash in the first access. So the first hset, seems to always go to the first row of the table.
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;
}