15-line hash table in C • Hacker News Board

Re: 15-line hash table in C

#41

Post by rgbrenner » Fri, Dec 12, 2014, 7:05 AM UTC

youngthugger wrote: post #35

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

In C.. Yes.. it's a basic data type you'll probably find yourself using quite a bit. If you program in some other language that already provides hashtable functions/types, then maybe you can get by with just knowing how it works so you can figure out when to use it.

Re: 15-line hash table in C

#42

Post by seyfulislam » Fri, Dec 12, 2014, 7:07 AM UTC

everything is 15-line when you have semicolon.

Re: 15-line hash table in C

#43

Post by fsloth » Fri, Dec 12, 2014, 7:23 AM UTC

youngthugger wrote: post #35

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

Yes. Hash table, linked list and a graph of some sort are those fundamental datastructures that everyone should have implemented at least once by themselves. IMO, the core to excellent software engineering his having a lucid intuition about fundamental things such as those.

Mainly because they are simple, and lot of problems are solvable by using them without resorting to Someone Elses Gigantic Platform Framework.

Re: 15-line hash table in C

#44

Post by pwr22 » Fri, Dec 12, 2014, 7:27 AM UTC

userbinator wrote: post #31

valleyer wrote: post #25

Earlier quoted context omitted.

Yeah... it’s easy to write small code that doesn’t work.

It's not hard to fix, however - one extra modulus, as far as I can see.

Technically there is bounds checking

  ... & (SIZE - 1)

but it looks broken because t does the C-ish mutating accumulator thing rather than acting as a base and using h as an offset

You need a temporary variable of

  int (**)[2]

to avoid doing two additions per iter, though maybe the compiler can pick that up and do it for you. Anyway, this no longer crashes but it now runs forever if the hash fills

https://gist.github.com/pwr22/a08597e475d1aa44cd96

It will still fail looking up a non-existent key, which I don't understand

Re: 15-line hash table in C

#45

Post by crpatino » Fri, Dec 12, 2014, 7:43 AM UTC

youngthugger wrote: post #35

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

In my experience, there's strong correlation between programmers that don't know how to implement basic data structures and programmers that make poor decisions when picking up one from a collections library. The ones that know that they don't know at least stick to fixed sized arrays and pay the performance price.

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.

Re: 15-line hash table in C

#46

Post by jakobegger » Fri, Dec 12, 2014, 8:22 AM UTC

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

Re: 15-line hash table in C

#47

Post by mathetic » Fri, Dec 12, 2014, 8:33 AM UTC

I love how a comment thread about a fun little program turned into HN showing off their wisdom in software engineering coupled with occasional boasting about tight code reviews.

I will not understand how and why people's egos get threatened by things like this.

Re: 15-line hash table in C

#48

Post by AntiRush » Fri, Dec 12, 2014, 8:43 AM UTC

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

uthash[1] is another good solution. It's pretty bulletproof and has lots of options. Also implemented with macros, if that's a plus :-).

[1]: http://troydhanson.github.io/uthash/

Re: 15-line hash table in C

#49

Post by jakobegger » Fri, Dec 12, 2014, 8:47 AM UTC

mathetic wrote: post #47

I love how a comment thread about a fun little program turned into HN showing off their wisdom in software engineering coupled with occasional boasting about tight code reviews. I will not understand how and why people's egos get threatened by things like this.

I actually enjoyed reading this thread. Yes, there are some snarky comments about missing newlines, but there are also a lot of constructive comments here!

Re: 15-line hash table in C

#50

Post by hawski » Fri, Dec 12, 2014, 9:01 AM UTC

pwr22 wrote: post #44

userbinator wrote: post #31

Earlier quoted context omitted.

It's not hard to fix, however - one extra modulus, as far as I can see.

Technically there is bounds checking ... & (SIZE - 1) but it looks broken because t does the C-ish mutating accumulator thing rather than acting as a base and using h as an offset You need a temporary variable of int (**)[2] to avoid doing two additions per iter, though maybe the compiler can pick that up and do it for you. Anyway, this no longer crashes but it now runs forever if the hash fills https://gist.github.c…

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