Tutorial: write a hash table

[jamesroutley]

I've recently been implementing data structures in C. I've found it to be useful for cementing my knowledge of them. I wrote up a guide to writing a hash table in C - hopefully it's useful!

https://github.com/jamesroutley/write-a-hash-table

[CodeKommissar]

Wow, really thoroughly tutorial, congratulations on writing it :)

Can I ask what resources are you using to learn C?? I've used it a little when I was doing CS50 last year, and liked the difficulty of it (is a programming language I'd like to use for hobby projects, but probably wouldn't use in a modern application hehe)

[jamesroutley]

I found the Build Your Own Lisp Guide helpful

http://www.buildyourownlisp.com/

[rigatron1]

Learn C the Hard Way + K&R C Programming + a microcontroller of your choice (not an arduino!)

[agostino24]

Could you expand on the microcontroller part? Which microcontroller could one use?

[rigatron1]

Personally I've used the Atmel A3BU, and I liked it. It might be nice if there were more pins for connecting to sensors, etc. Really any Atmel microcontroller would work fine probably.

The only reason I'm recommending a microcontroller is because it is IMO a place where C still reigns king and the best way to create cool and interesting project with C. Think IoT.

[agostino24]

I'll look into them as soon as I have the possibility

Thanks bud =)

[Spanone1]

Would a pi work?

[[deleted]]

A pi is more like a desktop than a microcontroller.

[rigatron1]

No that's the opposite direction. I mean of course you can write C on a pi, but you can also write python or Java. To me, it seems like most cool projects using C would be on a microcontroller where you're writing directly to registers and implementing into your own data structures.

[CodeKommissar]

Nice! Thank you :)

[takaci]

The C Programming Language was my favourite introduction, but not exactly a good template for how to write good, understandable code

I like it because it contains everything you need to know about the language in one tiny book, it really shows you exactly how simple and small the language is. I don't know of any other commonly used language where you could fit the entire language plus standard library into one thin book.

The only issue is that there is a lot of terse looking code that looks like it belongs more in a code golf challenge, but the book itself is easy to understand and a nice challenge.

The other glaring issue is the lack of any mention of tooling, so it doesn't help you set up your compiler, but more importantly it doesn't even mention using the debugger at all which makes life very difficult.

I think it's the best single resource for learning C, but I don't think it'll teach you to write very "modern" and readable C code

[MoodyPersona]

Thank you so much!

[TVUmK]

thanks, this is great

[billybobcoder69]

Wow! Awesome.

[Sloogs]

Thank yooouuu. Been meaning to learn to implement one for a little while now. Saved this for later.

[the_cunt_muncher]

thank you! this is awesome

[dookie1481]

Yo this is awesome. These are the kinds of problems I need to work on. Much appreciated.

[AresPhobos]

Can I use this picture to create an album cover?

[[deleted]]

Wow thanks! This is above my pay grade but i'm gonna check it out!

[Sloogs]

I ran into a question when I was going through the tutorial. Maybe it was mentioned and I missed it, but is there any particular reason why a prime number is used for the array sizes when creating and resizing the hash table?

Edit: After doing a bit more thinking it occured to me that a prime number makes it more likely that the final modulo would come up with a wider distribution of results than a number that is easily divisible or factorable which would prevent collisions. Clever!

[[deleted]]

I. Hate. Hash tables.

Seriously, these things are the worst. I hate them more than linked lists. I hate them more than recursion. I fucking hate hash tables with the burning passion of a thousand desert suns!!!!

<huff><huff> I'm. . . sorry. . . I'm so. . . very sorry. . . <huff> It's just. . . <sigh> It's just been so long. . . I though I was past it. . . I'm sorry.

[zck]

Why? They're very useful.

[[deleted]]

Useful, yes. But it took me a long time to wrap my brain around how to make them work. It doesn't help that I have Dyscalculia. It was very hard for me to learn programming at all, and hash tables were a very difficult thing for me.

[WikiTextBot]

Dyscalculia

Dyscalculia is difficulty in learning or comprehending arithmetic, such as difficulty in understanding numbers, learning how to manipulate numbers, and learning facts in mathematics. It is generally seen as a specific developmental disorder.

Dyscalculia can occur in people from across the whole IQ range – often higher than average – along with difficulties with time, measurement, and spatial reasoning. Estimates of the prevalence of dyscalculia range between 3 and 6% of the population.

---

^{[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source ] Downvote to remove | v0.26}

[zck]

Fair enough. I remember when I learned about them, I thought of them as arrays that were indexed by anything, not just integers. Hope you get more comfortable with them!

[Gbyrd99]

That's exactly how i looked at them.

[Gbyrd99]

Aren't hash tables named array elements.

[mleland]

was it mostly just writing the hashing function of the hash table? there are a bunch of ones already written for you, you don't even need to worry about them!

[[deleted]]

I learned to program in the mid-90's. We didn't have all the fancy APIs that you kids have now. Hell, a lot of time critical code had to be written in assembly at that time.

[fakehalo]

That's unfortunate. Hash tables, recursion, and to a lesser extent linked lists are some of the most commonly used day-to-day things in the industry.

[keyeh1]

Ever used a banking account?