40-Year-Old Conjecture on Hash Tables Shattered

For four decades, computer scientists have accepted Andrew Yao's 1985 conjecture on the efficiency of hash table lookups. However, Krapivin and his team have developed a novel hash table that dramatically outperforms Yao's worst-case bound. Their new algorithm achieves a far faster query and insertion time, and surprisingly, the average query time is a constant, irrespective of the table's fullness. This groundbreaking result not only refutes a long-held belief but also opens new avenues for hash table optimization.