Hashing cuco tornou a busca em tempo constante ao expulsar uma chave como um ovo de cuco

Tabelas hash de endereçamento aberto padrão se degradam quando as entradas se agrupam e as cadeias de sondagem crescem. Rasmus Pagh e Flemming Friche Rodler perguntaram o que aconteceria se cada chave tivesse exatamente dois slots possíveis em vez de um.

O dicionário deles, apresentado em 2001 no BRICS em Aarhus, usa duas funções hash e duas tabelas. Em uma colisão, a chave que chega expulsa o ocupante, que recursivamente vai para sua outra casa. A busca é garantida em no máximo duas sondagens.

Como as tabelas só precisam estar cerca de metade cheias em média, a estrutura permanece eficiente em memória enquanto oferece uma busca constante garantida no pior caso.

Dê a cada chave dois lugares e realoque o perdedor

Duas posições possíveis limitam uma busca a duas sondagens, independentemente do conjunto de chaves.

A expulsão resolve colisões sem uma longa cadeia de sondagem ou uma lista encadeada.

Mantém alta ocupação, portanto usa bem a memória enquanto permanece amigável ao cache.

Escolha uma estrutura de dados que seja rápida no pior caso, não apenas em média. A expulsão de duas escolhas transforma uma colisão rara e cara em uma busca limitada a duas sondagens.

O hashing cuco tornou-se um resultado de referência na teoria e na prática de dicionários. Sua garantia de tempo constante e localidade de cache o tornaram atraente para hardware e roteamento de alto desempenho, e a ideia de expulsão influenciou esquemas posteriores de hash e sketching.