Hashing Cuckoo

O hashing cuco atribui a cada chave duas posições candidatas: h1(k) na Tabela 1 e h2(k) na Tabela 2. A busca é sempre O(1) no pior caso, pois a chave só pode residir em uma dessas duas posições, de modo que uma consulta verifica exatamente dois locais e termina. A inserção coloca a nova chave em sua posição na Tabela 1; se essa posição estiver ocupada, o ocupante atual é expulso para sua própria posição alternativa, e essa expulsão pode se propagar por várias chaves até que uma posição vazia seja encontrada. Pagh e Rodler provaram em 2001 que essa cadeia se resolve em O(1) passos esperados sob uma família de funções de hash aleatórias, e na prática o desempenho no caso médio é equivalente ao endereçamento aberto para fatores de carga de até aproximadamente 50% por tabela.

O principal modo de falha é um ciclo na cadeia de expulsões, que ocorre quando o grafo de deslocamentos (chaves como arestas, posições como nós) contém um ciclo. Nesse ponto, a inserção precisa refazer o hash de toda a tabela usando novas funções de hash. A probabilidade de ciclo cresce acentuadamente acima de um fator de carga combinado de aproximadamente 50% por tabela (total de 50% de 2n posições), por isso as implementações tipicamente refazem o hash ao ultrapassar esse limiar. Implementações práticas incluem a libcuckoo, que alcança mais de 100 milhões de operações por segundo em hardware moderno combinando hashing cuco com travamento otimista, e muitos classificadores de pacotes de rede de alto desempenho onde a latência de busca O(1) no pior caso é um requisito rígido.