#Undergraduate Disproves 40-Year-Old Conjecture, Invents New Kind of #HashTable
A young computer scientist and two colleagues show that searches within data structures called #hashtables can be much faster than previously deemed possible.
https://www.wired.com/story/undergraduate-upends-a-40-year-old-data-science-conjecture/
https://archive.ph/2Tl3q
Still working on #swad, and currently very busy with improving quality, most of the actual work done inside my #poser library.
After finally supporting #kqueue and #epoll, I now integrated #xxhash to completely replace my previous stupid and naive hashing. I also added a more involved #dictionary class as an alternative to the already existing #hashtable. While the hashtable's size must be pre-configured and collissions are only ever resolved by storing linked lists, the new dictionary dynamically nests multiple hashtables (using different bits of a single hash value). I hope to achieve acceptable scaling while maintaining also acceptable memory overhead that way ...
#swad already uses both container classes as appropriate.
Next I'll probably revisit poser's #threadpool. I think I could replace #pthread condition variables by "simple" #semaphores, which should also reduce overhead ...
How to handle a hash table?
“You didn’t just come up with a cool hash table ... You’ve actually completely wiped out a 40-year-old conjecture!”
https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/
#hashTable #infosec
I have no understanding of what a hash table is but I’ve heard of them and know that they’re important and useful. I like the utter randomness of this story. A student looked at an old paper “for fun” and blew the longstanding Yao’s conjecture out of the water. I also like that nobody knows what it might be good for right now but it might lead to something cool later on. Go #science!
https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/
Designing A Fast Concurrent Hash Table, https://ibraheem.ca/posts/designing-papaya/.
The author presents a novel Rust library called papaya, that is a (really) fast concurrent hash table. The article explains the inspirations, the differences with other libraries, the new techniques etc. A really instructive article.
