Hacker News Reader

Comment by dprkh | Hacker News Reader

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?

View on HN

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.

In LeetCode, it's a very common optimization. If your key values are dense, you use an array. If your key values are sparse, you use a dict.

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

Reply on news.ycombinator.com