Como o hash de cuco garante o O (1) lookups na presença de persistentes colisões de hash?

Question

Como o hash de cuco garante o O (1) lookups na presença de persistentes colisões de hash?

#1 resposta do (3 votos)

5

A maioria das implementações de tabela de hash garante O (1) caso médio, mas O (n) caso máximo de pesquisa (onde 'n' é o número de chaves na tabela). Mas Cuckoo Hashing é descrito como O (1) no máximo. Aparentemente, isso é feito usando duas funções hash e, se houver uma colisão com uma, ela usa a alternativa. Se houver colisões com os dois, primeiro ele tenta embaralhar os itens para criar espaço, mas se houver três chaves com o mesmo valor com as duas funções hash, isso falhará.

Pelo que entendi, a próxima abordagem é alterar as funções hash.

Em uma implementação de tipo genérico (por exemplo, esta implementação do Haskell ) a maneira óbvia de fazer isso é fornecer uma interface que permita que uma família de funções hash seja fornecida, neste caso a Hashable typeclass, que contém uma função hashWithSalt :: Int -> a -> Int (onde a é o tipo que está sendo processado ). No entanto, isso fornece apenas um único parâmetro Int e uma única saída Int , que é 32 bits * 2 = 64 bits de hash e sal possíveis, portanto, com quaisquer valores contendo mais dados que 65 bits, ainda haverá potencial itens que sempre colidem. Em um pior caso teórico (por exemplo, gerado usando este código que certamente parece mostrar O (1) tempo de pesquisa pelo menos para n < = 50 - acima disso, o tempo de inserção torna-se problematicamente grande por algum motivo) pode haver 'n' itens que colidam com todas as funções potenciais de hash.

Como, portanto, é possível que a complexidade máxima da pesquisa seja O (1)? Existe algum truque de implementação que eu não tenha entendido que evita esse problema?

data-structures big-o hashtable

por Jules 01.04.2016 / 14:33

fonte

1 resposta

Tags data-structures big-o hashtable

Como se estrutura um projeto de linguagem de montagem? Preciso declarar uma variável de temporizador de atraso como volátil mesmo se eu acessá-la de outro módulo

score 3 · Answer 1

A pesquisa seria implementada em uma linguagem procedural, como

lookup(key){

    int h1 = hash1(key);
    if(table[h1%table.length].key == key){
        return table[h1%table.length].value;

    int h2 = hash2(key);
    if(table[h2%table.length].key == key){
        return table[h2%table.length].value;

    return null;

}

Sem loops, sem complexidade, nada que faça a pesquisa demorar mais do que um constante pior momento.

A mágica que faz este trabalho está na lógica de inserção e repetição e exige que nenhum elemento de 3 mapeie para o mesmo par de hashes ou, mais geralmente, para cada conjunto de elementos n , deve haver pelo menos n hashes exclusivos .

Algumas implementações requerem que a função hash seja sintonizável com um parâmetro para que possa selecionar 2 parâmetros arbitrários para o hash. Então, quando a pré-condição acima for violada, ela selecionará 2 novos parâmetros e refazer a gravação.