Undergraduate Upends a 40-Year-Old Data Science Conjecture | Quanta Magazine
www.quantamagazine.org
A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.
  • OhNoMoreLemmy@lemmy.mlEnglish
    6·
    1 day 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.

    • deegeese@sopuli.xyzEnglish
      6·
      18 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.