•  04-07-2019
  •  | 
  •  

Pergunta

Alguém tem uma implementação de Cuckoo hashing em C? Se houvesse um Open Source, versão não GPL seria perfeito!

Desde Adam mencionou em seu comentário, alguém sabe por que ele não é muito usado? É apenas uma questão de implementação ou as boas propriedades teóricas não se concretizem na prática?

Outras dicas

Como outras respostas têm para fora pontas, é verdade que o mais simples hashtable cuco exige que a tabela ser meio vazio. No entanto, o conceito foi generalizado para d hash cuco -ary, em que cada tecla tem d possíveis lugares para ninho, ao contrário de 2 lugares na versão simples.

o factor de carga aumenta rapidamente aceitáveis ??como d é aumentada. Por apenas d = 3, você já pode usar em torno de um 75% de tabela completa. A desvantagem é que você precisa d hash funções independentes. Eu sou um fã de funções hash Bob Jenkins para este fim (ver http://burtleburtle.net /bob/c/lookup3.c ), que podem ser úteis em uma implementação de cuco hashing.

Cuckoo hashing está fora relativamente não utilizada da academia (com exceção de caches de hardware, que às vezes emprestar idéias de, mas realmente não implementar totalmente). Ela exige uma tabela hash muito escassa para obter um bom tempo com inserções - você realmente precisa ter 51% de sua mesa vazia para o bom desempenho. Por isso, é tanto rápido e tem um monte de espaço, ou espaço lento e usos de forma eficiente - nunca ambos. Outros algoritmos são ambos tempo e espaço eficiente, embora eles são piores do cuco quando apenas tempo ou espaço é levado em conta.

Aqui está uma href="http://www.theiling.de/projects/lookuptable.html" rel="noreferrer"> gerador de código . Verifique a licença do gerador para verificar se a saída não é GPL. Deveria ser, mas verifique qualquer maneira.

-Adam

Mesmo que seja uma questão antiga, alguém ainda pode estar interessado:)

Este papel descreve a aplicação de uma d-ária cuco de hash paralelo em GPUs (CUDA / OpenCL). É descrito muito bem e implementá-lo com base na descrição é bastante fácil. Geralmente vale a pena ler, se você estiver interessado neste tópico. (Você vai precisar de um login ACM embora.)

A linguagem IO tem um, em PHash.c. Você pode encontrar o href="http://github.com/stevedekorte/io" rel="nofollow código para IO no Github. IO é BSD licenciado.

Eu vejo o ponto sobre a utilização, mas este foi o meu raciocínio para tentar este esquema de hashing particular. Por favor ket-me saber se eu perdi alguma coisa.

Para meu conhecimento, possíveis alternativas para hashtables para criar um dicionário dinâmico são (balanceada) árvores binárias e skiplists. Apenas para discussão deixar de abstrair os tipos de chave e valor e vamos supor que vamos acessar valores através de um void *.

Para uma árvore binária eu teria: 

struct node {
  void *key;
  void *value;
  struct node *left;
  struct node *right;
}

Assim, os ponteiros assumindo ter todas o mesmo tamanho s , a loja n itens I terá 4 s bytes.

Skiplists são quase o mesmo que o número médio de ponteiros em um nó é 2.

Em um hashtable eu teria: 

struct slot {
  void *key;
  void *value;
}

Assim, cada item será apenas requre 2 s bytes para ser armazenado. Se o fator de carga é de 50%, a loja n itens I terá o mesmo 4 s bytes como árvores.

Não parece muito ruim para mim: o hashtable cuco vai ocupar mais ou menos a mesma quantidade de memória como uma árvore binária, mas vai me dar O (1) tempo de acesso, em vez de O (log n).

Sem contar a complexidade de manter a árvore balanceada e a informação adicional que possa ser necessário para armazenar informações de balanceamento no nó.

Outros esquemas de hashing poderia alcançar uma taxa de ocupação melhor (digamos 75% ou 80%) com nenhuma garantia sobre o pior tempo de acesso caso (que pode até ser O (n)).

A propósito, d-ária cuco hash e " cuco hashing com um estoque " parecem ser capaz de aumentar o fator de carga, enquanto mantém o tempo de acesso constante.

Cuckoo hashing parece uma técnica valiosa para mim e eu pensei que já foi explorada; essa é a razão da minha pergunta.

Eu não posso falar para o software, mas hash cuco é certamente usado em hardware e tornando-se muito popular. Principais fornecedores de equipamentos de rede foram olhando para hashing cuco e alguns já usá-lo. A atração de hashing cuco vem do tempo de pesquisa constante, é claro, mas também o tempo perto de inserção constante.

Apesar de inserção pode ser teoricamente ilimitada, na prática isso pode ser delimitada para O (N log N) do número de linhas na tabela (s) e, quando medida, o tempo de inserção é de cerca de 1,1 * A memória d acessos em média. Isso é apenas 10% a mais do que o mínimo absoluto! acesso à memória é muitas vezes o fator limitante em equipamentos de rede.

hash funções independentes são uma obrigação e selecioná-los corretamente é difícil. Boa sorte.

Na sequência de um comentário de "onebyone", já implementado e testado um par de versões de hashing Cuckoo para determinar o requisito de memória real.

Depois de alguma experiência, a alegação de que você não tem que ReAsH até que a tabela é quase 50% completo parece ser verdade, especialmente se o " esconderijo " truque é implmented.

O problema é quando você ampliar a mesa. A abordagem usual é dobrar seu tamanho, mas isso leva à nova tabela sendo apenas 25% utilizaram!

Na verdade, assumir a hashtable tem 16 slots, quando eu inserir o número do elemento 8º, I vai ficar sem bons ranhuras e terá de ReAsH. Vou dobrá-lo e agora a tabela é 32 slots com apenas 8 deles ocupado que é um desperdício de 75%!

Este é o preço a pagar para ter uma "constante" tempo de recuperação (em termos de limite superior para o número de acesso / comparação).

Eu já concebeu um esquema diferente, no entanto: a partir de uma potência de 2 maior que 1, se a tabela tiver n ranhuras e n é uma potência de dois, adicionar n / 2 slots add otherwhise n / 3 slots: 

+--+--+
|  |  |                             2 slots
+--+--+

+--+--+--+
|  |  |  |                          3 slots
+--+--+--+ 

+--+--+--+--+
|  |  |  |  |                       4 slots
+--+--+--+--+

+--+--+--+--+--+--+
|  |  |  |  |  |  |                 6 slots
+--+--+--+--+--+--+

+--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  |           8 slots
+--+--+--+--+--+--+--+--+

etc.

Juntamente com o pressuposto de que reashing só ocorrerá quando a mesa é 50% cheio, isso leva ao facto de que a tabela só será 66% esvaziar (1/3), em vez de 75% esvaziar (1/4) depois um ReAsH (isto é, o pior caso).

Eu também descobri (mas ainda precisa verificar a matemática) que ampliando cada vez por sqrt (n), o espaço desperdiçado assintoticamente aproxima de 50%.

É claro que o preço a pagar para o consumo de memória menos é o aumento do número de ReAsH que será necessário no final. Infelizmente, nada vem de graça.

Vou investigar se alguém estiver interessado.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top