颠覆40年猜想：新型哈希表速度远超预期

剑桥大学的研究生Krapivin与纽约大学的Farach-Colton和Kuszmaul合作，推翻了计算机科学界长期以来被奉为圭臬的Yao猜想。他们设计了一种新型哈希表，其在最坏情况下查找元素的时间复杂度为(log x)²，远低于之前认为的最佳复杂度x。这项突破性研究成果，不仅解决了哈希表领域一个经典难题，也为数据存储效率带来了显著提升，引发了学术界的高度关注。