Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

15-line hash table in C

pastes.archbsd.net

Post reply on HN
Print view View original

71–80 of 104 posts

Re: 15-line hash table in C

#71

Post by balakc »

throwaway_yy2Di wrote: post #7

There'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.

Every time a lookup is performed, isn't it linearly looking through the table to find that key... That doesn't sound like a hash! Maybe am missing something here.

Re: 15-line hash table in C

#73

Post by nowne »

stormbrew wrote: post #16
nowne wrote: post #10

Earlier 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.

Linear probing works by initially hashing the value, call it h(x), then if there is a collision, it checks h(x)+1, h(x)+2, ..., h(x) + k, until it finds a open slot. Lookup works in the same way, and deletion is a bit more complicated.

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.

Re: 15-line hash table in C

#74

Post by jfoutz »

balakc wrote: post #71
throwaway_yy2Di wrote: post #7

There'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.

Every time a lookup is performed, isn't it linearly looking through the table to find that key... That doesn't sound like a hash! Maybe am missing something here.

Instead of a linked list to store hash collisions, it's using linear probing, which just uses the next open spot in the table. (Maybe I'm misunderstanding the question, it looks like they're indexing into the table correctly to me)

Re: 15-line hash table in C

#75

Post by nine_k »

I can see two legitimate cases for writing very short, very dense code.

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 = p ]
2: Implement an algorithm in a super-efficient, while non-obvious, way. An example is the inverse square root calculation made by famous by John Carmack (http://www.codemaestro.com/reviews/9).

The linked hashtable implementation, to my mind, is neither very elegant nor fiendishly clever, nor even reasonably correct.

Re: 15-line hash table in C

#76

Post by andyidsinga »

shaftoe wrote: post #2

This code reminds me why clever is the enemy of good.

exactly ...i made a similar comment about making more readable while increasing the lines to 100 and got down voted. folks, any dev can read 100 lines of code...

maybe the downvote is ok - im not grokking the essence of it - but similar bits of code written in perl are notorious jokes.

Re: 15-line hash table in C

#77

Post by vonmoltke »

So, I have been looking at this implementation for several minutes. Ignoring what others have already posted about the code being way too dense for no benefit, how is this a hash table? It looks like a bog-standard associative array.

Re: 15-line hash table in C

#78

Post by cel »

jakobegger wrote: post #46

For those of us who actually ship code, I'd like to suggest khash[1], which is a pretty nice implementation of a hash table in C. It uses lot's of macros, so if you're looking for a brain teaser you will be satisfied as well :) [1]: http://attractivechaos.github.io/klib/#Khash%3A%20generic%20...

See also clibs/hash[1], which provides a friendly API on top of khash.

[1]: https://github.com/clibs/hash

Re: 15-line hash table in C

#79

Post by jayvanguard »

vonmoltke wrote: post #77

So, I have been looking at this implementation for several minutes. Ignoring what others have already posted about the code being way too dense for no benefit, how is this a hash table? It looks like a bog-standard associative array.

No doubt, I prefer to have actual hashing going on in my hash tables.
Post reply on HN