15-line hash table in C • Hacker News Board

Re: 15-line hash table in C

#91

Post by foota » Fri, Dec 12, 2014, 5:49 PM UTC

taeric wrote: post #87

nine_k wrote: post #75

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 inve…

There is something funny about stating that most "literally" implements the idea of the algorithm, when the main "idea" of the algorithm is to be quick. :) 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. Essen…

Just because it's one instruction doesn't make it faster

Re: 15-line hash table in C

#92

Post by stormbrew » Fri, Dec 12, 2014, 5:56 PM UTC

nowne wrote: post #73

stormbrew wrote: post #16

Earlier quoted context omitted.

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…

I do know how linear probing works, thanks. ;)

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.

Re: 15-line hash table in C

#93

Post by im2w1l » Fri, Dec 12, 2014, 5:59 PM UTC

nowne wrote: post #10

deweerdt wrote: post #6

A 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 uses quadratic probing. Notice how both h and t increase.

Re: 15-line hash table in C

#94

Post by im2w1l » Fri, Dec 12, 2014, 6:25 PM UTC

It took me some serious thinking to figure out why you could take t, despite t being NULL.

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.

Re: 15-line hash table in C

#95

Post by camgunz » Fri, Dec 12, 2014, 6:27 PM UTC

pwr22 wrote: post #54

hawski wrote: post #50

Earlier quoted context omitted.

>Due to C there is no way to declare both an int and that in the loop preamble so you'd need at least one more line In C99 it's allowed to declare in the loop preamble. True for ANSI-C.

Not differing types

If you really want to, I think you might be able to declare a struct in there. A curse on your house though....

Re: 15-line hash table in C

#96

Post by to3m » Fri, Dec 12, 2014, 7:00 PM UTC

foota wrote: post #91

taeric wrote: post #87

Earlier quoted context omitted.

There is something funny about stating that most "literally" implements the idea of the algorithm, when the main "idea" of the algorithm is to be quick. :) 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. Essen…

Just because it's one instruction doesn't make it faster

In the case of a reciprocal square root estimate it probably is, particularly compared to the code given. A fast reciprocal square root estimate function usually takes less than 5 cycles - and is less than 1/4096th out, so the accuracy is better too.

Re: 15-line hash table in C

#97

Post by dllthomas » Fri, Dec 12, 2014, 7:36 PM UTC

I'd call this 16 lines - multiple statements on one line is cheating; if we're going that route this could be 3 lines.

Re: 15-line hash table in C

#98

Post by amazingrando » Fri, Dec 12, 2014, 8:37 PM UTC

youngthugger wrote: post #35

Is learning how to create a hash table necessary for a software engineer?

Learning what it is and how it works is necessary. From there, any remotely competent programmer should be able to quickly and easily create one.

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.

Re: 15-line hash table in C

#99

Post by pmelendez » Fri, Dec 12, 2014, 9:37 PM UTC

Is this even a hash table? It looks more like a regular associative array. It seems like look ups are linear in time which is ditching one of the biggest advantages with hash tables.

Also since keys are integers, how this would be useful? Isn't the same that a regular array?

Re: 15-line hash table in C

#100

Post by lgeek » Fri, Dec 12, 2014, 10:23 PM UTC

bnegreve wrote: post #81

linuxlizard wrote: post #80

(Insert my usual rant about not checking malloc()/calloc() for failure.)

Note that on many systems (e.g. Linux), malloc/calloc won't always return NULL when you're out of memory because of lazy memory allocation policies. It will only crash when you start reading / writing. That makes it arguably less useful to test the return value. edit: clarity.

However, mmap and the functions which rely on it will return MAP_FAILED/NULL if no gap large enough is found in the virtual address space or if you've used MAP_FIXED and the area isn't free. If you don't check for errors, the application could potentially end up trying to dereference a NULL pointer.