An undergraduate student at Rutgers University developed a revolutionary new hash table design that disproved a 40-year-old computer science conjecture by Andrew Yao, demonstrating faster data retrieval times than previously thought possible. The breakthrough shows that hash tables can achieve query times proportional to (log x)² instead of x, and in non-greedy cases, can maintain constant average query times regardless of table fullness.

https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/

#datastructures #computerscience #hashtables #academicresearch #algorithmoptimization