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

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

  This is very cool news. Would be nice if it had some details on the implementation though

  source

  • bravesilvernest@lemmy.ml ⁨2⁩ ⁨months⁩ ago

    Agreed, I figured they’d have at least some psuedocode but alas

    source

    • sp3tr4l@lemmy.zip ⁨2⁩ ⁨months⁩ ago

      For those in a rush:

      Initial paper outlining theorem (2021):

      arxiv.org/pdf/2111.12800

      Paper that demonstrates and proves its validity (2025):

      arxiv.org/pdf/2501.02305

      I tried a quick search, but I’m not seeing any public implementations that specifically mention or cite ‘Krapavin’ or ‘Tiny Pointers’ anywhere.

      source
• xtrapoletariat@beehaw.org ⁨2⁩ ⁨months⁩ ago

  This is quite cool. They shattered a 40 year-old conjecture on map-insertion speed boundaries. To understand the practical impact I have to read the paper, but given their abundance in CS the potential is huge.

  source
• p03locke@lemmy.dbzer0.com ⁨2⁩ ⁨months⁩ ago

  “Data structures called hash tables”? Editor thinks this is some arcane little-used data technology.

  Hashes are used in literally every programming language that’s worth using.

  source

  • veroxii@aussie.zone ⁨2⁩ ⁨months⁩ ago

    What are you on about? The first paragraph says hash tables are “widely used” and the second says they are “common”.

    “Data structures called hash tables” seems to just be a factual statement of what we’re dealing with, especially for people who are not programmers.

    source

    • JackbyDev@programming.dev ⁨2⁩ ⁨months⁩ ago

      It just feels bizarre. You wouldn’t say something like “a car part called a catalytic converter”.

      source

      • -> View More Comments
  • AnotherDirtyAnglo@lemmy.ca ⁨2⁩ ⁨months⁩ ago

    Some of my best, most useful programs sort data from disparate sources into enormous Hash-Of-Hash structures to produce extremely insightful reports. And I wrote the first version 25 years ago.

    source
• NigelFrobisher@aussie.zone ⁨2⁩ ⁨months⁩ ago

  All we have to do is rename b-trees to “hash tables” and database lookup times will be changed forever.

  source
• possiblylinux127@lemmy.zip ⁨2⁩ ⁨months⁩ ago

  Oh yes, the new revolutionary data structure called a hash table

  source

  • expr@programming.dev ⁨2⁩ ⁨months⁩ ago

    Did you read the article? The claim is that they have invented a new kind of hash table that has vastly improved algorithmic complexity compared to standard hash tables.

    I haven’t read the paper yet, but if what the article claims is true, it could be revolutionary in computer science and open up a ton of doors.

    source

    • possiblylinux127@lemmy.zip ⁨2⁩ ⁨months⁩ ago

      I’m very skeptical

      source

      • -> View More Comments
• JackbyDev@programming.dev ⁨2⁩ ⁨months⁩ ago

  I need to look more into this, I would’ve thought query time on hash tables was already constant.

  source

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

    Only if there’s no collisions. With lots of collisions it’s far from constant.

    source