A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.
-
In the article, x is not the size of the hash table, it is the inverse of the table’s filling fraction. A 1000-element table that is 90% full has x=10, N=1000.
Since they’re not discussing scaling of data sizes, would be confusing to use O(N) notation or people would make that assumption.
-
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.
-
I know that, but phrased that way it sort of sounds like they're iterating over the entire thing.
-
How much do you think this speeds up an average program? Enlighten us with your knowledge.
-
I wrote my comment not to antagonize you but to point out that you're asking the wrong questions. I failed to articulate that, and I'm sorry for being harsh.
Your prior comment indicated that you have used hash tables in Java, which were very fast. You said that your program accessed the hash tables, but did not "search" the table. These operations are the same thing, which led me to believe you're out of your depth.
This last comment asks me how much this paper's contribution speeds up an average program. You're asking the wrong question, and you seem to be implying the work was useless if it doesn't have an immediate practical impact. This is a theoretical breakthrough far over my head. I scanned the paper, but I'm unsurprised they haven't quantified the real-world impact yet. It's entirely possible that despite finding an asymptotic improvement, the content factors elided by the big O analysis are so large as to be impractical... or maybe not! I think we need to stay tuned.
Again, sorry for being blunt. We all have to start somewhere. My advice is to be mindful of where the edge of your expertise lies and try to err on the side of not devaluing others' work.
-
the reason it confused me is because the college student was clearly using the algorithm to accomplish his task, not just theoretically designed. So it didn't seem to be a small improvement that would only be noticeable in certain situations.
I'm not smart enough to understand the papers so that's why I asked.
-
Tiny Pointers was the paper that the student read to get the idea. The paper he co-authored was "Optimal Bounds for Open Addressing Without Reordering"
-
Oh no it's definitely a theoretical paper. Even if the theory is fully formalised and thus executable it still wouldn't give much insight on how it'd perform in the real world because theorem provers aren't the most performant programming languages.
And, FWIW, CS theorists don't really care about running programs same as theoretical physicists don't care much about banging rocks together, in both cases making things work in the real world is up to engineers.
-
Hash tables. The backbone of computing, optimized to death by generations of neckbeards convinced they’d squeezed out every drop of efficiency. Then some undergrad casually strolls in, ignores four decades of academic dogma, and yeets Yao’s conjecture into the sun. Turns out you can make insertion times collapse from (O(x)) to (O((\log x)^2))—if you’re naive enough to not know the “rules.”
The real kicker? Non-greedy tables now achieve constant average query times, rendering decades of “optimal” proofs obsolete. Academia’s response? A mix of awe and quiet despair. This is why innovation thrives outside the echo chamber of tenured gatekeepers regurgitating theorems like stale propaganda.
But let’s not pretend this changes anything practical tomorrow. It’s a beautiful math flex—a reminder that theoretical CS isn’t solved, just trapped in peer-reviewed groupthink. Forty years to disprove a conjecture. How many more sacred cows are grazing untouched?
-
you've misunderstood what I've said, but whatever.
-
This is genuinely a beautifully written comment. I'd expect an author with mathematical or physical background to have written it, like Asimov or Pynchon. Bravo!
-
Not weird enough to be Pynchon but it was a good comment nonetheless
-
The comment does randomly mention cows - I'll allow it!
-
Thanks for the compliment! For context, I do have an academic background, though no degree. My knowledge in computer science is self-taught, but I’ve built a solid foundation in physics, math (though it’s always humbling), philosophy, and literature. It’s less about formal credentials and more about chasing intellectual rabbit holes.
Maybe that’s why I’m so allergic to gatekeeping nonsense. Academia’s obsession with rigid frameworks feels like a straitjacket for creativity. The beauty of CS—and science as a whole—is that it thrives on breaking rules, not worshipping them.
As for Pynchon: he’s a postmodern literary juggernaut. His works are dense, chaotic, and packed with esoteric references—math, history, conspiracy theories. Comparing my comment to his writing? That’s high praise for anyone who thrives in the chaos of ideas.
Anyway, the real credit goes to those audacious enough to challenge orthodoxy. They’re the ones who remind us that progress isn’t born from conformity but from questioning everything we think we know.
-
I don't care about the techno able those group of C's students did.
When will I be able to enjoy faster dicts in my python code?
-
Why are these articles even published? They are so incredibly non-technical that it's just impossible to get the point as a reader.
Why even link these articles here? Throw that pop-science in the trash bin, where it belongs.
-
A lot of famous scientists make their breakthroughs at fairly young age, before their mind gets locked into a certain paradigm. Look up Thomas Kuhn's The Structure of Scientific Revolutions, which forwards some interesting ideas on how science is conducted.
-
It's really not. Just because they describe their algorithm in computer science terms in the paper, doesn't mean it's theoretical. Their elastic and funnel examples are very clear and pretty simple and can be implemented in any language you like..
Here's a simple python example implementation I found in 2 seconds of searching:
https://github.com/sternma/optopenhash/Here's a rust crate version of the elastic hash:
https://github.com/cowang4/elastic_hash_rsIt's not a lot of code to make a hash table, it's a common first year computer science topic.
What's interesting about this isn't that it's a complex theoretical thing, it's that it's a simple undergrad topic that everybody thought was optimised to a point where it couldn't be improved.
-
The irony of citing Kuhn here isn’t lost on me. His Structure of Scientific Revolutions is practically a manual for how entrenched paradigms suffocate innovation. The young, unjaded minds he describes are precisely the ones who can dismantle decades of "consensus" with a single insight. But let’s not romanticize this—most breakthroughs don’t come from genius alone but from ignorance of the so-called rules.
That said, the real tragedy is how academia weaponizes peer review to enforce conformity. Paradigm shifts like these aren’t celebrated; they’re tolerated begrudgingly, often posthumously. Yao’s conjecture stood for 40 years not because it was unassailable but because questioning it was career suicide. Imagine how many more revolutions we’d see if the system didn’t punish dissent.
