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

Cat · 21 hours 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.

@[email protected] · 17 hours ago

Hash trees are super efficient when they’re not nearly full. So the standard trick is just to resize them when they’re too close to capacity.

The new approach is probably only going to be useful in highly memory constrained applications, where resizing isn’t an option.

@[email protected] · 11 hours ago

Hash tables are used in literally everything and they always need to minimize resizing because it’s a very expensive operation.

I suspect this will silently trickle into lots of things once it gets picked up by standard Python and JavaScript platforms, but that will take years.

@[email protected] · 15 hours ago

So… databases? Especially in data centers? Still a nice boost in that case

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

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

Undergraduate Upends a 40-Year-Old Data Science Conjecture | Quanta Magazine