News for hackers. Stuff that matters.

A comment on Undergraduate Disproves 40-Year-Old Conjecture, Invents New Kind of Hash Table.

Re:Undergraduate Disproves 40-Year-Old Conjecture, Invents N... by vlovich123 on Monday March 17, 2025 @12:56PM (#43390474)
If my reading of the paper was correct, this kind of hash table is incredibly complicated to resize because resizing would invalidate all previously handed out pointers unless you only do chaining?

The other challenge is that computing N hash functions is quite expensive so in practice I think this ends up slower in real world terms despite the big-O speed up?

Does this actually end up beating open addressed hash tables? It seems more like a neat hypothetical CS result that wouldn’t have any actual real world application? That’s cool in and of itself but I’m curious if there’s any real world reason to do this.

[ Parent | on HN ]
Re:Undergraduate Disproves 40-Year-Old Conjecture, Invents N... by hrdwdmrbl on Monday March 17, 2025 @02:01PM (#43391087)
Likely why the article said that it wouldn’t lead to any immediate applications.

Cause from the headline, one would get all excited about the applications

[ Parent | on HN ]
Re:Undergraduate Disproves 40-Year-Old Conjecture, Invents N... by ForTheKidz on Monday March 17, 2025 @05:30PM (#43392909)
Still worth it for situations where you can memoize hashes and reuse them. Basically, any situation where you want to intern strings.
[ Parent | on HN ]
Re:Undergraduate Disproves 40-Year-Old Conjecture, Invents N... by augusto-moura on Monday March 17, 2025 @06:48PM (#43393527)
Also worth it for the cases were you already know the maximum size for the table.
[ Parent | on HN ]
Re:Undergraduate Disproves 40-Year-Old Conjecture, Invents N... by vlovich123 on Tuesday March 18, 2025 @05:38PM (#43405461)
You realize that the number of hashes you have to memoize is variable and unknown ahead of time? And depending on the key, you’re adding a decent amount of overhead on memoization vs just computing the hash on the fly?

I’m going to go ahead and challenge you to actually try implementing this hash table and use it for anything where a normal highly optimized hash table won’t beat this (eg try to beat hashbrown from rust / abseil swisstable in c++)

[ Parent | on HN ]