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.
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).
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!
Nice, I like this style of exposition. "Let's do this one thing -> well, shit -> (loop)". Term rewriting (graph reduction as you've said) is evaluation.
I also like https://github.com/tidwall/hashmap.c for general use.
Why would you believe this in the first place?
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...
> 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!
> Perl Contains the Lambda Calculus
> (How to write a 163 line program to compute 1+1)
> Length: 90 minutes
Prerequisites: None.
This is also a fun introduction to building up lambda calculus. And it gets up to fizzbuzz!