In che modo l'hashing del cuculo garantisce O (1) ricerche in presenza di collisioni hash persistenti

Question

In che modo l'hashing del cuculo garantisce O (1) ricerche in presenza di collisioni hash persistenti

#1 da (3 voti)

5

La maggior parte delle implementazioni della tabella hash garantiscono O (1) caso medio ma O (n) valore massimo per la ricerca (dove 'n' è il numero di chiavi nella tabella). Ma Cuckoo Hashing è descritto come O (1) massimo. Apparentemente questo lo raggiunge usando due funzioni di hash, e se ottiene una collisione con una, usa quella alternativa. Se ottiene collisioni con entrambi, tenta prima di rimescolare gli oggetti per creare spazio, ma se ci sono tre chiavi che hanno tutte lo stesso valore con entrambe le funzioni hash, questo fallirà.

A quanto ho capito, il prossimo approccio è quello di cambiare le funzioni di hash.

In un'implementazione di tipo generico (ad es. questa implementazione di Haskell ) il modo ovvio per fare ciò è fornire un'interfaccia che permetta di fornire una famiglia di funzioni hash, in questo caso la classe Hashable , che contiene una funzione hashWithSalt :: Int -> a -> Int (dove a è il tipo di hash ). Tuttavia, questo fornisce solo un singolo parametro Int e un singolo output Int , che è 32 bit * 2 = 64 bit di hash e sale possibili, quindi con qualsiasi valore contenente più dati di 65 bit ci sarà ancora un potenziale elementi che sempre si scontrano. In un caso peggiore teorico (ad es. come generato usando questo codice che sembra certamente mostrare O (1) tempi di ricerca almeno per n < = 50 - al di sopra di questo, il tempo di inserimento diventa problematico per qualche motivo) potrebbero esserci "n" elementi che entrano in collisione con tutte le potenziali funzioni di hashing.

In che modo, quindi, è possibile che la massima complessità della ricerca sia O (1)? C'è qualche trucco di implementazione che non ho afferrato che eviti questo problema?

data-structures big-o hashtable

posta Jules 01.04.2016 - 14:33

fonte

1 risposta

Leggi altre domande sui tag data-structures big-o hashtable

Devo dichiarare volatile una variabile del timer di ritardo anche se accedo da un altro modulo Le ispezioni formali sono attualmente in uso?

score 3 · Answer 1

La ricerca sarebbe implementata in un linguaggio procedurale come

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;

}

Nessun loop, nessuna complessità, niente che possa rendere la ricerca più di un tempo costante nel peggiore dei casi.

La magia che rende questo lavoro è nella logica insert e rehash e richiede che nessun 3 elementi sia mappato sulla stessa coppia di hash o più in generale per ogni set di elementi n ci deve essere almeno n hash univoci .

Alcune implementazioni richiedono che la funzione di hash sia sintonizzabile con un parametro in modo che possa selezionare 2 parametri arbitrari per l'hash. Quindi, una volta violata la precondizione precedente, verranno selezionati 2 nuovi parametri e rihash.