Hacker News Reader

Comment by saghm | Hacker News Reader

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.

View on HN

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

Reply on news.ycombinator.com