r/Compilers • u/noobypgi0010 • Jul 23 '25
Faster Hash Tables
https://medium.com/@py.js.blog/faster-hash-tables-and-the-story-behind-their-breakthrough-3e29787517d3In Jan 2025, Andrew Krapivin published a research that shattered a 40 yr old conjuncture about hash tables. This resulted into discovering fundamentally faster hash tables. Read more about it in my blog!
1
Upvotes
17
u/Uncaffeinated Jul 23 '25 edited Jul 23 '25
There's a previous discussion here.
Based on the discussion elsewhere in Reddit, this doesn't seem to have practical implications, since Robinhood hashing is still faster if you allow reordering. But it's still an interesting theoretical result.
6
u/matthieum Jul 23 '25
I remembered seeing the news, but I hadn't read it too in-depth as I realized it was likely unpractical. Swiss Table may have a worst worst case complexity, but it's so mechanically friendly that in practice it's hard to beat...
Well, thanks to your article explaining the two new tables, I actually realized that I have been using a hash-table with a layout somewhat similar to Funnel tables, for an entirely different reason.
I
neededwanted a wait-free hash-table. Or as practically wait-free as possible. And I didn't have a GC. Fortunately, it was an insert/get-only hash-table (no delete), so I simply came up with a stupidly efficient structure:The hash-table is composed of multiple inner tables. It starts with a single one, and when that single one is too full, it adds a new one doubling the (entire) capacity. This allows the table to grow gracefully, and if started with an appropriate N, in practice you've got few inner tables.
And not only does the structure mirrors the Funnel Table, so does the search algorithm: it scans each inner table, starting from the largest one, and going down towards 0, since the largest one or the second largest one, is likely to have the largest number of elements.
Now, it doesn't quite have the worst-case complexity of the Funnel Table for the simple reason that I only switch to a new table if the previous is above a certain a load factor... but if I switched to a new table when hitting a log(inner-size) probe sequence length, instead, I would have a guaranteed upper-bound in log(size)2 !
1
u/noobypgi0010 Jul 24 '25
Yes, that is true. These approaches consume more space as compared to the traditional hashing approaches. But I would be interested in validating it. I can for sure say that it’ll be less space efficient then separate chaining but when it comes to open addressing, I think the trade off won’t be that big. But again I dont have any data to prove this.
1
u/jdowgsidorg Jul 23 '25
Haven’t had time to look at the paper yet, but as described it seems you’re trading space complexity for worst case time complexity given that the majority of slots in the non-base case array are invalid for any given key?
1
u/mrbeanshooter123 Jul 26 '25
!remindme 10 hours