Conjectura de 40 anos sobre tabelas hash quebrada

Por quatro décadas, cientistas da computação aceitaram a conjectura de Andrew Yao de 1985 sobre a eficiência de pesquisas em tabelas hash. No entanto, Krapivin e sua equipe desenvolveram uma nova tabela hash que supera dramaticamente o limite de pior caso de Yao. Seu novo algoritmo atinge um tempo de consulta e inserção muito mais rápido e, surpreendentemente, o tempo médio de consulta é constante, independentemente da plenitude da tabela. Este resultado inovador não apenas refuta uma crença antiga, mas também abre novas vias para otimização de tabelas hash.