Em um estudo publicado em janeiro de 2025, Krapivin, agora estudante de pós-graduação na Universidade de Cambridge, juntamente com Farach-Colton, da Universidade de Nova York, e Kuszmaul, demonstraram que uma nova tabela hash pode localizar elementos de forma mais rápida do que se imaginava ser possível, desafiando uma conjectura que há muito era considerada verdadeira.

"É um artigo importante", afirmou Alex Conway, do Cornell Tech, em Nova York. "As tabelas hash estão entre as estruturas de dados mais antigas que temos, e ainda são uma das maneiras mais eficientes de armazenar dados." No entanto, ele destacou que ainda existem questões em aberto sobre seu funcionamento. "Este artigo responde a algumas delas de maneiras surpreendentes."

As tabelas hash se tornaram onipresentes na computação, em grande parte devido à sua simplicidade e facilidade de uso. Elas são projetadas para permitir que os usuários realizem exatamente três operações: pesquisar um elemento, deletar um elemento ou inserir um em um espaço vazio. As primeiras tabelas hash surgiram no início dos anos 1950, e os cientistas da computação as estudaram e utilizaram desde então. Pesquisadores buscavam entender os limites de velocidade para algumas dessas operações, como a rapidez de uma nova pesquisa ou inserção.

Martín Farach-Colton foi fundamental para que Krapivin provasse que sua nova tabela hash contradizia a conjectura de longa data. A resposta sobre a rapidez das operações em uma tabela hash geralmente depende do tempo necessário para encontrar um espaço vazio. Essa dependência, por sua vez, está relacionada ao quão cheia a tabela está, que pode ser descrita em termos de porcentagem total — por exemplo, uma tabela está 50% cheia ou 90% cheia — ou usando um número inteiro, denotado por x, para especificar a proximidade da tabela em relação à capacidade total.

A pesquisa de Krapivin não foi influenciada pela sabedoria convencional, simplesmente porque ele não tinha conhecimento dela. "Eu fiz isso sem saber sobre a conjectura de Yao", revelou ele. Suas investigações com pequenos ponteiros levaram ao desenvolvimento de uma nova tabela hash que não dependia da abordagem conhecida como sondagem uniforme. Para essa nova tabela, o tempo necessário para consultas e inserções no pior caso é proporcional a (log x)², muito mais rápido do que x. Essa descoberta contradiz diretamente a conjectura de Yao, que, há 40 anos, era considerada verdadeira pela maioria dos cientistas da computação.

"Esse resultado é belo porque aborda e resolve um problema clássico", comentou Guy Blelloch, da Carnegie Mellon.

"Não é apenas o fato de que eles refutaram a conjectura de Yao; eles também encontraram a melhor resposta possível para a sua pergunta", disse Sepehr Assadi, da Universidade de Waterloo. "Poderíamos ter esperado mais 40 anos para saber a resposta correta."