A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible. - ThreadSky

wired.com • 7 days ago

A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.

Comments

gznork26.bsky.social•7 days ago

The article would have been more enlightening if it included a simple explanation of what a hash table is, for readers who don’t already know.

tkpk2020.bsky.social•6 days ago

The book "Weapons of Math Destruction" was right.

christopherquirk.bsky.social•7 days ago

Very cool. And nice write-up.

anarcho-yam.bsky.social•6 days ago

Remember the Trump govt just hacked all the loans and grants that make research like this possible

rednecklefty.bsky.social•7 days ago

I would have loved to have heard Yao's response to this.

nopantscrew.bsky.social•7 days ago

Hot swap em

miragi.bsky.social•6 days ago

From the paper: "...whenever the user inserts a key/value pair (x, y), they are given back a small hint h that they are responsible for storing. ... In the future, when the user wishes to recover the value y for x, they present both the key x and the hint h to the retrieval data structure. "

miragi.bsky.social•6 days ago

Begs the question: How do they look up the hint if they only have x?

csteinbach.bsky.social•6 days ago

Haven't read the paper yet but it sounds like it could be embedded in a session token.

csteinbach.bsky.social•6 days ago

Oddly I don't find the passage you quoted. I'm reading "Optimal Bounds for Open Addressing Without Reordering" (28 Feb 2025) in case you got it from somewhere else.

miragi.bsky.social•6 days ago

https://arxiv.org/abs/2111.12800 then view PDF