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

tyler@programming.dev ⁨2⁩ ⁨months⁩ ago

• OhNoMoreLemmy@lemmy.ml ⁨2⁩ ⁨months⁩ 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.

  source

  • deegeese@sopuli.xyz ⁨2⁩ ⁨months⁩ 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.

    source
  • Sekoia@lemmy.blahaj.zone ⁨2⁩ ⁨months⁩ ago

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

    source
• source_of_truth@lemmy.world ⁨2⁩ ⁨months⁩ ago

  I don’t think the speed of hash tables is a problem in most applications.

  source

  • zkfcfbzr@lemmy.world ⁨2⁩ ⁨months⁩ ago

    Hash tables are often used behind the scenes. dicts and sets in python both utilize hash tables internally, for example.

    source

    • source_of_truth@lemmy.world ⁨2⁩ ⁨months⁩ ago

      I’ve only used java but java hash tables are stupid fast in my experience, like everything else in my crap programs was 1000 times slower than the hash table access or storage.

      source

      • 0x0@lemmy.dbzer0.com ⁨2⁩ ⁨months⁩ ago

        Sorry to be blunt, but you don’t know what you’re talking about.

        source

        • -> View More Comments
      • deegeese@sopuli.xyz ⁨2⁩ ⁨months⁩ ago

        If you use a hash table, you search every time you retrieve an object.

        If you didn’t retrieve, why would you be storing the data in the first place?

        source

        • -> View More Comments
  • lime@feddit.nu ⁨2⁩ ⁨months⁩ ago

    anything that deserializes arbitrary json will put it into a hash table, right? it would definitely speed up the web.

    source

    • frezik@midwest.social ⁨2⁩ ⁨months⁩ ago

      Depends on the implementation, but most will, yes. There are other forms of associative arrays, like trie or binary tree, but hash is the most common.

      source
    • barsoap@lemm.ee ⁨2⁩ ⁨months⁩ ago

      Using bencode over json would probably speed up the web more. Not to mention good ole X.690. The web is completely cooked when it comes to efficiency.

      source

      • lime@feddit.nu ⁨2⁩ ⁨months⁩ ago

        the biggest speedup would probably come from using proper schemas that can be efficiently parsed. but we’ve made our bed out of ad-hoc protocols.

        source

        • -> View More Comments
• rockSlayer@lemmy.world ⁨2⁩ ⁨months⁩ ago

  Infrastructural APIs are much slower to change, and in a lot of cases the use of those APIs are dependent on a specific version. The change will definitely occur over time as the practical limitations are discovered

  source