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

How to implement a hash table in C (2021)

benhoyt.com

Post reply on HN
Print view View original

21–30 of 43 posts

Re: How to implement a hash table in C (2021)

#21

Post by elteto »

shawn_w wrote: post #15
floam wrote: post #7

Earlier quoted context omitted.

It has no type, so you can cast it to whatever it actually is. Even a function you will call. The main use case is generic functions. And in data structures like this.

Casting between void pointers and function pointers is, strictly speaking, undefined behavior. Though it does tend to work, it's not something to rely on. (And you don't need casts when converting between void pointers and data pointers)

The dlopen/dlsym API uses void *, there’s really no alternative in C.

It might be undefined in the sense that a language lawyer might care, but for any sane implementation it’s completely valid.

Re: How to implement a hash table in C (2021)

#22

Post by Joker_vD »

> but it is non-ideal that I’m only allowing half the range of size_t.

I am fairly certain that in C it's actually impossible to have an object whose size is larger than half of the range of size_t unless ptrdiff_t is wider than size_t, which normally isn't. Unless, of course, C standard decided to make subtracting two valid pointers into the same array (or one past the end) a potential UB, just because.

Re: How to implement a hash table in C (2021)

#23

Post by maccard »

timo-e-aus-e wrote: post #5

I played around with C++ when I was at university. Then never touched it again. So, with a grin I stumble over things like "void* ht_get(...)" Wait. What? A void pointer? Interesting... I have no clue. I like articles like these. For someone not familiar with C it's a perfect level. In terms of explanation and the code itself.

Remember that this is for c, not c++. Void pointers are entirely unnecessary in c++ unless you’re interoperating with existing libraries and can’t change the interface. You’ll get faster and safer code with templates and function overloading

Re: How to implement a hash table in C (2021)

#24

Post by maccard »

shawn_w wrote: post #15
floam wrote: post #7

Earlier quoted context omitted.

It has no type, so you can cast it to whatever it actually is. Even a function you will call. The main use case is generic functions. And in data structures like this.

Casting between void pointers and function pointers is, strictly speaking, undefined behavior. Though it does tend to work, it's not something to rely on. (And you don't need casts when converting between void pointers and data pointers)

c11 fixed this. C++ allows casting as long as you don’t access the intermediate casted item and cast it back to the type it started as.

In practice though, it works pretty much everywhere in my experience.

Re: How to implement a hash table in C (2021)

#25

Post by mauvehaus »

brabel wrote: post #11
suprjami wrote: post #3

It's the ihih guy! Thanks for being one of the few C bloggers out there.

I enjoy reading posts about C just to see how much boilerplate and footguns higher languages let you avoid. I would like to write C, but I just have no trust I would remember or even know how to do things right (use `calloc` vs `malloc`, free the table when allocation of `entries` fails etc).

Counterpoint: when you're writing C, you end up only implementing as much complexity as you actually need. I rolled a hash table for a project that only need to contain integer keys and (I think) string values. It didn't need to carry around all the complexity to handle hashing arbitrary structured data for keys, etc. Multi-threading was supported but a simple lock over the whole table was sufficient for correctness and met the required performance.

The whole thing was perhaps 200 lines of straightforward code. If you don't need to carry around support for all the third-prime-numbered-Tuesday-of-the-month scenarios that general purpose libraries have to, you end up with code you can understand fully and don't have to spend time reasoning about complexity that doesn't exist.

Re: How to implement a hash table in C (2021)

#27

Post by shawn_w »

akira2501 wrote: post #19
shawn_w wrote: post #17

Earlier quoted context omitted.

POSIX hsearch tables are terrible. There's a reason why nobody uses them. One at a time per program, having to know how big the table needs to be at initialization time with no automatic resizing, an API that's very limited (no way to remove entries, iterate over entries, tell how many entries are in the table, ...)

> One at a time per program Reentrant versions have existed for quite some time. > having to know how big the table needs to be at initialization time with no automatic resizing The posted implementation resizes by creating an entirely new table and then moving all entries. The exact same mechanism is available with hsearch. > no way to remove entries, iterate over entries Strong downside but the posted implementatio…

>> One at a time per program

>Reentrant versions have existed for quite some time.

Not in POSIX. glibc has one, but that doesn't do much good if you want your code to work portably. I do see they've made their way into Free and Net BSD, but not Open. Are they available for Mac? Any of the surviving commercial unixes?

>> having to know how big the table needs to be at initialization time with no automatic resizing

>The posted implementation resizes by creating an entirely new table and then moving all entries. The exact same mechanism is available with hsearch.

That's how resizing a hash table typically works, yes. Except it's normally done automatically and transparently by the hash table code. hsearch doesn't do that. And since it doesn't give you a way to iterate over values in the table, you'd have to keep a separate list of everything you add to it in order to manually delete the existing table and make a bigger one and re-add everything to it... Like I said, it's terrible.

Re: How to implement a hash table in C (2021)

#28

Post by Horffupolde »

mauvehaus wrote: post #25
brabel wrote: post #11

Earlier quoted context omitted.

I enjoy reading posts about C just to see how much boilerplate and footguns higher languages let you avoid. I would like to write C, but I just have no trust I would remember or even know how to do things right (use `calloc` vs `malloc`, free the table when allocation of `entries` fails etc).

Counterpoint: when you're writing C, you end up only implementing as much complexity as you actually need. I rolled a hash table for a project that only need to contain integer keys and (I think) string values. It didn't need to carry around all the complexity to handle hashing arbitrary structured data for keys, etc. Multi-threading was supported but a simple lock over the whole table was sufficient for correctness…

Until it does and you do and you don’t.

Re: How to implement a hash table in C (2021)

#29

Post by SloopJon »

I was noodling in this area recently, trying to speed up some code similar to the tr utility:

    $ echo abcdef |tr abc ghi
    ghidef
For an eight-bit character set, I found that building an array to map every character improved on linear search, even for short replacement strings and relatively short input strings.

There isn't as easy a win for Unicode, so I played with some simple hash tables. Although the conventional wisdom is to use the high-order bits of a hash function's output, FNV-1a is not so good for short inputs of one or two bytes. (I used the 32-bit variant.) It was better just to use the low-order bits.

Post reply on HN