Cuckoo Hashing

Il cuckoo hashing assegna a ogni chiave due posizioni candidate: h1(k) nella Tabella 1 e h2(k) nella Tabella 2. La ricerca è sempre O(1) nel caso peggiore perché la chiave può trovarsi solo in una di quelle due celle, pertanto una query controlla esattamente due posizioni e termina. L'inserimento colloca la nuova chiave nella sua cella nella Tabella 1; se quella cella è occupata, l'elemento presente viene spostato nella propria cella alternativa, e questa catena di spostamenti può propagarsi attraverso diverse chiavi prima che venga trovata una cella libera. Pagh e Rodler dimostrarono nel 2001 che questa catena si risolve in un numero atteso O(1) di passi con una famiglia di funzioni hash casuali, e in pratica le prestazioni nel caso medio sono paragonabili all'indirizzamento aperto per fattori di carico fino a circa il 50% per tabella.

Il principale modo di fallimento è la presenza di un ciclo nella catena di spostamenti, che si verifica quando il grafo degli spostamenti (le chiavi come archi, le celle come nodi) contiene un ciclo. In quel caso l'inserimento deve effettuare il rehashing dell'intera tabella utilizzando nuove funzioni hash. La probabilità di un ciclo aumenta bruscamente al di sopra di un fattore di carico combinato di circa il 50% per tabella (totale 50% di 2n celle), quindi le implementazioni effettuano tipicamente il rehashing quando questa soglia viene superata. Tra i casi d'uso pratici figurano libcuckoo, che raggiunge oltre 100 milioni di operazioni al secondo su hardware moderno combinando il cuckoo hashing con il locking ottimistico, e numerosi classificatori di pacchetti di rete ad alte prestazioni in cui la latenza di ricerca O(1) nel caso peggiore è un requisito inderogabile.