A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.
-
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
-
-
This is the paper the article is about: https://arxiv.org/pdf/2501.02305
-
Also never even start optimizing until you profile and are sure the bit you are trying to optimize even matters to the overall performance of your program.
-
-
-
-
-
-
The paper was published by IEEE and with professors as co-authors. Only the second author is a student. And I wouldn't dismiss it out of hand like that because of a magazine article. Students come up with breakthroughs all the time.
The paper itself says it disproves Yao's conjecture. I personally plan to implement and benchmark this because the results seem so good. It could be another fibonacci heap situation, but maybe not. Hash tables are so widely used, that it might even be worthwhile to make special hardware to use this on servers, if our current computer architecture is only thing that holds back the performance.Edit: author sequence
-
-
yupyup, just send HTML over the wire. it's fine.
-
-
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.
-
-
...before the program even exists...?
-
So... databases? Especially in data centers? Still a nice boost in that case
-
-
Everyone prepare for your minds to be blown:
-
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.
