Hacker News Reader

Comment by ancientstraits | Hacker News Reader

The "how to implement a hash table" article https://benhoyt.com/writings/hash-table-in-c/ was really helpful for me. I thought that hash tables were something that were basically impossible to make in C, but this showed that it was simpler.

View on HN

You can also look at how CPython implements hash tables in C. The implementation is surprisingly approachable for a real world one.

SDL3's properties API uses an internal hashtable I'm waiting for them to make public.

I also like https://github.com/tidwall/hashmap.c for general use.

Yep.

https://news.ycombinator.com/item?id=49913084

Why? The only thing missing is the proper data structures and algorithms background.

Which during my degree, the lab deliverables were 100% C code.

Here, one possible book:

Data Structures, Algorithms, and Software Principles in C (1994 edition)

https://www.amazon.com/dp/0201591189

When I was in university, hash tables were definitely among the things we had to learn about and then implement in C, probably in first year. Per Wikipedia, the concept dates to 1953 (with an implementation in assembly); of course people made them in C once that was an option.

I always liked that idea of just doing a linear wrap-around sweep through an array that holds (key, value) pairs, until you find the pair with the key you're looking for (for 'get' or 'contains?') or an empty spot (for 'put'). The trick to make this fast is that the hash function (key -> int) tells you at which index to start the sweep.

No secondary data structures, super simple to implement, and it works great for small use cases.

This isn't great though if you need to find out if an element exists in the table, and you have the ability to remove elements from it. I suppose you could optimize the hash table after deletions, but that again would be slow.. ?

Btw, this reminds me a bit of Cuckoo hashes. Never used them but seems like a nice idea.

The expected or amortized complexity of the standard hash table operations (put, get, contains, remove) are all O(1) for linear probing (under the usual assumptions for the hash function and as long as the table does not get too full). Of course that doesn't shield a single operation from being O(n) in the worst case.

The standard hash table has buckets, though, not just a single array that is probed through in case there's no space for a value in the slot determined by the hash function?

Right, that's the beauty of this simple approach: there's only one array and it doubles as the storage for buckets. But yes, the table will have a maximum size after which you cannot add more entries. That is, in practice you would create a new hashtable with a larger capacity and rehash all the existing entries into the new, bigger table (in practice, you would do that even sooner than that, namely when a certain load factor is passed - see my previous comment where I alluded to the role of the load factor).

The cool thing, however, is: if the size of the new hashtable is double the size of the old hashtable, your amortized insertion costs are still only O(1)!

(And you don't just have to take my word for it: take my original comment and paste it into the AI interface of your choice and have it create a concrete implementation. Ask it to add a remove operation, and an automatic doubling of the array size + rehashing when the table reaches a load factor of, say, 0.7 -- the resulting code should be very manageable, and then you can run your own tests and measure times!

This is maybe not the smartest way to do hashing, but its appeal lies in its simplicity and hence compactness of implementation. There are many cases where you don't even need a 'remove' operation, and where you never have to worry about growing the array because you know that you're only ever going to hash a certain number of elements at most.)

Let's say we have removed all elements from the hash. Then all following contains -calls will need to be O(n), if I understood correctly? They need to check every slot in the array to confirm inexistence, rather than just one bucket.

Arrays are hash tables. You can implement a very simple hash table from a tutorial, but can you implement a sophisticated one? What about a concurrent hash table?

Yeah, I'm pretty sure we made hash tables in the first C class I took in college in my second semester freshman year. If you can make a linked list, and then make an array of them, and a function to map keys to array indexes, you have a hash table. Whether it's actually performant is entirely a separate question, but a naive hash table is still a hash table.

Hash tables are awesome. They are both an incredibly simple data structure and a seriously deep rabbit hole. Most of the complexity comes from collision resolution [1], and how you handle resolution largely determines what kind of hash table you have. There are at least dozens of collision resolution approaches. The simplest, and probably the one you implemented in your undergrad C class was open addressing. That’s also what I implemented as an undergrad. But there are many more approaches, some quite a bit more complicated, and many of them let you continue to shave off asymptotic costs when you run collision resolution, or they improve locality for typical lookups, allowing better cache utilization, etc. Hash tables are super fun to play with, and for full effect, you really do need to implement them in something like C.

I only skimmed the linked article, but I do wonder whether the author ever realized that they needed to think about scope rules. I searched for the word “scope” but never found it. Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain).

[1] https://en.wikipedia.org/wiki/Hash_table#Collision_resolutio...

Yeah, I learned about a bunch of the other algorithms later (forgetting the names, but stuff like "move to the next slot rather than putting collisions into buckets" and "hash a second time if you hit a collision"; I'm sure I'm forgetting some of the nuances).

> Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain)

Well if you like both lexical scope and pain, there's always lisp!

Be careful with Lisp!

You might end up founding one of the first e-commerce sites, sell it for a handsome payday, and then create the first startup accelerator and make insane amounts of money while transforming the industry.

Safer to stick to Blub.

I'd need to solve time travel first for that, but I guess lisp is as good a language as any for figuring that out

> Arrays are hash tables.

Maybe in JavaScript... but there is a topic called datastructures, where arrays are arrays, and hashtables are hastables. If people say this without a flip of an eye I'm not surprised why people write stuff like

> I thought that hash tables were something that were basically impossible to make in C

In a trivial sense, arrays are hash tables with a hash function of the identity f(x)=x.

It’s just not particularly common (or helpful) to view them that way.

Besides the sibling comment, you can used closed hash tables algorithm (open addressing), which is fully based on a single array.

https://en.wikipedia.org/wiki/Open_addressing

If hash tables were impossible to make in C, then it would be impossible to make them in Python, because it is a higher level language than C.

(Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)

But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.

Google for some videos by Raymond Hettinger about Python dictionaries.

Or look at the source code of the Python interpreter.

> But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.

In CPython they are written in C (at the moment). Other Python implementations are written in other languages.

> (Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)

It depends on what you mean by 'anything doable'. Eg Haskell compilers can in principle do lots of crazy optimisations that a C compiler would not be able to safely do, just because they don't have enough information. Even more so for Lean compilers, which can _know_ which of your loops are terminating, instead of making crude assumptions like C compilers.

Btw, higher level languages being implemented in lower level languages is mostly something for interpreters. Writing a C interpreter in Python is pretty much futile, if you care about speed. But writing a C compiler in Python is perfectly fine. And writing a Python compiler in Python is also fine. Many languages self-host (at least some of) their compilers.

IIRC, the first edition of the book "The C Programming Language" (aka K&R), by Kernighan and Ritchie, had a simple example of how to create a hash table in C, including with buckets to handle collisions. It was a simple algorithm. It simply added up the ASCII values of all the characters in the key, modulo some number.

> I thought that hash tables were something that were basically impossible to make in C,

Why would you believe this in the first place?

Yeah it's a strange assumption, as this was taught in basic data structures class years ago and any language can implement any data structure, technically speaking. C especially is a weird assumption because lots of foundational software is written in C including hash tables.

Reply on news.ycombinator.com