• 0 Posts
  • 38 Comments
Joined 2 years ago
cake
Cake day: June 23rd, 2023

help-circle

















  • The fact that you can achieve a constant average query time, regardless of the hash table’s fullness, was wholly unexpected — even to the authors themselves.

    WTF?

    I mean first of all, the “article” is just crap IMO, like only hinting att “anazing” things. But also containing basic errors like the above. It’s like they don’t understand complexity, a constant average time on what? A specific size of a hash table? Or do they mean it scales linearly with its size? Just go through the whole table and voila you have constant time already.

    So if they did find something, it’s not well explained in the article IMO. Shame, cause those kind of things are interesting, IMO.

    Edit: looks like they “cheat” (in a good way) to “reorder” the table to get their results with smarter inserts (their ‘elastic hashing’) so to not reorder the table. If so, then it’s very smart but not groundbreaking. I’m sick and just skimmed the paper, don’t kill me.