A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.
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.
The article is discussing how to reduce the constant time factor which depends on the filling fraction, which is a speed-memory tradeoff when creating the hash table.
The innovation described allows for the use of fuller tables which are resized less frequently, or faster insertion/retrieval for the existing filling fraction.
“Constant average query time” is not that hard to understand. It means that sometimes access time is e.g. linear, and sometimes you get your content before executing the code. With a hash table large enough and full enough, this can be used to fetch content seconds, minutes, days, potentially years before the program even exists. That’s one hell of a breakthrough.
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.
They managed to get the time to O(1)
The article is discussing how to reduce the constant time factor which depends on the filling fraction, which is a speed-memory tradeoff when creating the hash table.
The innovation described allows for the use of fuller tables which are resized less frequently, or faster insertion/retrieval for the existing filling fraction.
“Constant average query time” is not that hard to understand. It means that sometimes access time is e.g. linear, and sometimes you get your content before executing the code. With a hash table large enough and full enough, this can be used to fetch content seconds, minutes, days, potentially years before the program even exists. That’s one hell of a breakthrough.
[edit] /s, oops
…before the program even exists…?