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

Write a hash table in C

github.com

Post reply on HN
Print view View original

31–40 of 58 posts

Re: Write a hash table in C

#31

Post by MandieD »

sgslo wrote: post #8
jnordwick wrote: post #7

Why is this extremely basic CS 101 stuff being voted up today? Definitely not HN material.

Because not everyone who reads HN went through a CS program, and may have not seen implementations of common data structures like this before. Its a well-written tutorial that conveys the topic well.

Heck, I did go through the CS program at an infamously competitive mid-Atlantic school with decent grades, and I still liked the tutorial and am glad to have seen it on HN.

We can always use a look back at what's behind the "leaky abstractions" (to quote Joel Spolsky) that make our modern software world possible.

Re: Write a hash table in C

#33

Post by joeberon »

B1narySunset wrote: post #21
eighthnate wrote: post #18

Earlier quoted context omitted.

> There's room for both. Sure. I'm all for learning ML, Scheme, C/C++, Python, Ruby, Java/C#, etc. > There's a reason why a lot of CS programs have shuffled from primarily C to Python (some had Java in between). The reason is called dumbing down the curriculum. My fall freshman year, my college tried to switch from C to Java in order to make it easier for the general population to get into CS and there was a major pu…

The dumbing down of the curriculum so that music/english majors can pass CS classes doesn't do anyone any favors. You sound butt-hurt

Level of discourse on Hacker News 2017

Re: Write a hash table in C

#34

Post by fizixer »

I've heard of two possibilities (as a recommendation) for using data structures in C without having to develop them:

- BSD queue.h offers linked lists, queues, etc [1].

- UT-hash offers hash tables [2].

I've also read some people being frustrated with them, probably due to the quirky syntax/API. On the plus side (BSD at least) it's just a header file that you can download, include and start using.

[1] http://bxr.su/OpenBSD/sys/sys/queue.h

[2] https://troydhanson.github.io/uthash/

Re: Write a hash table in C

#35

Post by smegel »

This might seem academic, but I actually had a real reason to hand-roll a hash table implementation that would work in process-shared memory (as an Apache module). It was based on the hash table implemented in mod_ldap, and was part of an LRU cache.

Re: Write a hash table in C

#36

Post by grzm »

B1narySunset wrote: post #30
eighthnate wrote: post #25

Earlier quoted context omitted.

Huh? I'm not butthurt. Seems like you are though. I'm sorry having standards and expectations is something that offends so many people. C isn't a "difficult" language. It's something any CS major should have an understanding of. I can't believe on hackernews, I'd get attacked for saying people should learn C. Nevermind that most OSes and most languages themselves are written in C. Even python interpreters are written…

You're being attacked because of your condescending tone implying that music and english majors aren't smart enough to pass the CS curriculum

You're being attacked

Regardless of how much you may disagree with what someone said or how they said it, attacking them for it (even verbally) is not an appropriate response. It only contributes to worsening the discourse. If you can't find a way to disagree or express an opinion constructively, it's better to refrain from commenting at all.

Re: Write a hash table in C

#37

Post by pfranz »

eighthnate wrote: post #18
pfranz wrote: post #16

Earlier quoted context omitted.

There's room for both. There's a reason why a lot of CS programs have shuffled from primarily C to Python (some had Java in between). Not having to deal with boilerplate and housekeeping lets you focus on learning the topic at hand. Especially in a classroom setting where you're probably focusing on the specific subject instead of real-world dirtiness. But after learning the basic concept, you do need an actual imple…

> There's room for both. Sure. I'm all for learning ML, Scheme, C/C++, Python, Ruby, Java/C#, etc. > There's a reason why a lot of CS programs have shuffled from primarily C to Python (some had Java in between). The reason is called dumbing down the curriculum. My fall freshman year, my college tried to switch from C to Java in order to make it easier for the general population to get into CS and there was a major pu…

> Sure. I'm all for learning ML, Scheme, C/C++, Python, Ruby, Java/C#, etc.

Personally, I prefer to dig into 1 or 2 programming languages deeply instead of shallowly hop around half a dozen. I seem to retain the deep stuff a lot better. Even when coming back to languages I used heavily years ago (Bash or Perl, for example) I end up having to look up basic things like how loops or functions are defined when I pick them up again.

> The reason is called dumbing down the curriculum.

Do you feel the same way about SICP's choice of using Scheme? One of the innovations of SICP was that CS courses spent too much time explaining the details of a programming language [1]. That was 30 years ago. There are orthogonal discussions on the goals of CS changing over time.

> In an idealistic world, people go from Java/Python to C/Assembly, but that's rarely the case.

Maybe there's no business need? My wife works in video games. That's one industry where programmers often have deep knowledge of hardware and use assembly--but, there's still only a couple of them at each studio. Most people programming are doing game scripting or content creation.

> CS should begin with Math

Your argument seems to be against abstraction. Math is all about abstraction. So is programming. It's been interesting to see programmers tinker with hardware as things like Arduino and Raspberry Pi have become more popular. When writing software they take things for granted, but when interacting with hardware they have to account for things like debounce.

[1] https://people.eecs.berkeley.edu/~bh/sicp.html

Re: Write a hash table in C

#39

Post by twic »

to3m wrote: post #24
msarnoff wrote: post #20

"The language doesn't come with [a hash table implementation] included" The standard library does come with a half-baked hash table implementation[1] (hcreate/hdestroy/hsearch) that only allows creation of _one_ global hash table. GNU libc[2] adds hcreate_r/hdestroy_r/hsearch_r that allows multiple tables to be created. The APIs are strange and antiquated. On the other hand, the hash table implementation described in…

The hcreate nonsense is POSIX, not C99, so a conforming C implementation might not include it.

How does junk like this ever get into a standard? Didn't a whole committee of very experienced systems programmers have to sit down and say, "yes, these are routines that i think people will find generally useful"?

It looks like the same header, search.h, also includes functions for working with binary trees, where the user passes in the root pointer, and so which support multiple trees:

http://pubs.opengroup.org/onlinepubs/9699919799/functions/ts...

So this committee must have signed off on the hashtable stuff even though they had an example of how to do it properly right next to it!

Re: Write a hash table in C

#40

Post by pacaro »

clarry wrote: post #22

Don't allocate these items individually; don't store pointers to such items. They're tiny, and the pointer chasing + allocator bookkeeping overhead + potential randomisation make it inefficient for no gain. Just allocate an array of items. This way you'll also deal with fewer potential errors. Speaking of errors, please handle them and fix the API so that the caller can know if there's a problem.

Yeah, reading through that jumped out at me.

Also the use of strdup, while a reasonable choice, should also come with caveats about ownership and copying

I stopped at the use of pow for exponentiation in the hash function. Just iteratively multiply your factor and take the modulus on each round.

This would handle utf-8 just fine if characters are cast to unsigned in the hash function and a larger prime factor is used

None of these are real criticisms, I'd just love to see a pointer to more in depth information on how to really write hash functions

I hope that i missed it, but this definitely needs a clear statement that this is a pedagogical exercise and not a production ready implementation

Post reply on HN