Quais são as vantagens do hash de cuco sobre o hashing perfeito dinâmico?

As tabelas de hash perfeitas dinâmicas e as tabelas de hash do cuco são duas estruturas de dados diferentes que suportam pesquisas de pior caso O (1) e inserções e exclusões esperadas em tempo de O (1). Ambos requerem O (n) espaço auxiliar e acesso a famílias de funções de hash para suas operações.

Eu acho que essas duas estruturas de dados são bonitas e brilhantes por si só, mas não tenho certeza de ver como e quando uma delas seria preferível à outra.

Existem contextos específicos em que uma dessas estruturas de dados tem uma clara vantagem sobre a outra? Ou eles são principalmente intercambiáveis?

Hash perfeito dinâmico no sentido de Dietzfelbinger et al. precisa apenas de hash 2 independente . Embora existam alguns resultados no hash simples para tabelas de hash de cuco, como o hash de tabulação distorcida e "Famílias de Hash explícitas e eficientes suficientes para hash de cuco com stash", o hash perfeito dinâmico original é mais robusto em algum sentido.

No hash do cuco, as pesquisas podem ser realizadas em paralelo, enquanto no esquema de hash perfeito dinâmico original de Dietzfelbinger et al., As pesquisas exigem dois acessos de memória encadeados, nos quais o segundo acesso usa informações recuperadas do primeiro.

É relativamente fácil aumentar a eficiência de espaço do hash do cuco, permitindo que cada slot retenha mais de um item. Para slots de tamanho 4, a eficiência de espaço é algo como 95%. Ou seja, os itens podem ser inseridos até que 95% do espaço da tabela seja usado para reter itens, não apenas os locais onde os itens podem ir.

Por outro lado, os limites de Dietzfelbinger et al. o papel no hashing perfeito dinâmico prova apenas que as operações de inserção podem prosseguir desde que a tabela não tenha mais de 3% da capacidade.

Usos de hash de cuco $O(1)$blocos de memória a qualquer momento e precisa liberar ou realocar memória raramente. Hash perfeito dinâmico no sentido de usos de Dietzfelbinger$O(n)$blocos de memória e usará mais espaço na fragmentação interna e externa. Existem maneiras de evitar isso, mas adicionam complexidade ao algoritmo.