•  04-07-2019
  •  | 
  •  

Domanda

Qualcuno ha un'implementazione di hash del cuculo in C? Se ci fosse una versione Open Source, non GPL sarebbe perfetta!

Dato che Adam lo ha menzionato nel suo commento, qualcuno sa perché non è molto usato? È solo una questione di implementazione o le buone proprietà teoriche non si materializzano nella pratica?

Altri suggerimenti

Come hanno sottolineato altre risposte, è vero che la più semplice hashtable del cuculo richiede che il tavolo sia mezzo vuoto. Tuttavia, il concetto è stato generalizzato a d -ary hash cuculo, in cui ogni chiave ha d possibili luoghi in cui annidare, al contrario di 2 posti nella versione semplice.

Il fattore di carico accettabile aumenta rapidamente all'aumentare di d . Solo per d = 3, puoi già utilizzare una tabella completa pari al 75%. Il rovescio della medaglia è che hai bisogno di d funzioni hash indipendenti. Sono un fan delle funzioni hash di Bob Jenkins per questo scopo (vedi http://burtleburtle.net /bob/c/lookup3.c ), che potresti trovare utile in un'implementazione dell'hash del cuculo.

L'hashing del cuculo è relativamente inutilizzato al di fuori del mondo accademico (a parte le cache hardware, che a volte prendono in prestito idee, ma in realtà non si implementano completamente). Richiede una tabella hash molto scarsa per ottenere un buon tempo sugli inserimenti: è necessario avere il 51% della tabella vuota per ottenere buone prestazioni. Quindi è veloce e occupa molto spazio o lento e utilizza lo spazio in modo efficiente, mai entrambi. Altri algoritmi sono sia efficienti in termini di tempo che di spazio, sebbene siano peggiori del cuculo quando si tiene conto solo del tempo o dello spazio.

Ecco un generatore di codice per tabelle hash di cuculo . Controllare la licenza del generatore per verificare che l'output non sia GPL. Dovrebbe essere, ma controlla comunque.

-Adam

Anche se è una vecchia domanda, qualcuno potrebbe essere comunque interessato :)

Questo documento descrive l'implementazione di un hash cuckoo d-ary parallelo su GPU (CUDA / OpenCL). È descritto molto bene e implementarlo in base alla descrizione è abbastanza semplice. In genere vale la pena leggere, se sei interessato a questo argomento. (Avrai bisogno di un login ACM però.)

Il linguaggio IO ha uno, in PHash.c. Puoi trovare il codice per IO su Github. IO ha la licenza BSD.

Vedo il punto sull'utilizzo ma questo è stato il mio ragionamento per provare questo particolare schema di hashing. Per favore fatemi sapere se ho perso qualcosa.

Per quanto ne so, le possibili alternative agli hashtable per creare un dizionario dinamico sono alberi binari e skiplist (bilanciati). Solo per la discussione facciamo un estratto dalla chiave e dai tipi di valore e supponiamo che accederemo ai valori attraverso un void * .

Per un albero binario avrei: 

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

Quindi, supponendo che i puntatori abbiano tutte le stesse dimensioni s , per memorizzare n avrò bisogno di 4 s byte.

Le Skiplist sono quasi uguali al numero medio di puntatori in un nodo è 2.

In una tabella hash avrei: 

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

Quindi, ogni elemento richiederà solo 2 s byte da archiviare. Se il fattore di carico è del 50%, per memorizzare n elementi avrò bisogno degli stessi 4 s byte degli alberi.

Non mi sembra troppo male: l'hashtable del cuculo occuperà più o meno la stessa quantità di memoria di un albero binario ma mi darà il tempo di accesso O (1) anziché O (log n).

Senza contare la complessità di mantenere l'albero bilanciato e le informazioni aggiuntive che potrebbero essere necessarie per memorizzare le informazioni di bilanciamento nel nodo.

Altri schemi di hashing potrebbero ottenere un fattore di carico migliore (diciamo 75% o 80%) senza alcuna garanzia sul tempo di accesso nel caso peggiore (che potrebbe anche essere O (n)).

A proposito, d-ary cuckoo hashing e " hash del cuculo con una scorta " sembra essere in grado di aumentare il fattore di carico pur mantenendo un tempo di accesso costante.

L'hashing del cuculo mi sembra una tecnica preziosa e ho pensato che fosse già stato esplorato; questa è la ragione della mia domanda.

Non posso parlare di software, ma l'hash del cuculo è sicuramente usato nell'hardware e sta diventando molto popolare. I principali fornitori di apparecchiature di rete hanno studiato l'hash del cuculo e alcuni lo utilizzano già. L'attrazione per l'hash del cuculo proviene ovviamente dal tempo di ricerca costante, ma anche dal tempo di inserimento quasi costante.

Sebbene teoricamente l'inserzione possa essere illimitata, in pratica può essere limitata a O (log n) del numero di righe nelle tabelle e, se misurata, il tempo di inserzione è in media di circa 1,1 * d accessi alla memoria. Questo è solo il 10% in più rispetto al minimo assoluto! L'accesso alla memoria è spesso il fattore limitante nelle apparecchiature di rete.

Le funzioni hash indipendenti sono indispensabili e selezionarle correttamente è difficile. Buona fortuna.

A seguito di un commento di "onebyone", ho implementato e testato un paio di versioni di hash Cuckoo per determinare il reale fabbisogno di memoria.

Dopo alcuni esperimenti, l'affermazione secondo cui non devi ripetere fino a quando la tabella non è piena per quasi il 50% sembra essere vera, specialmente se " stash " il trucco è impiantato.

Il problema è quando si ingrandisce la tabella. L'approccio abituale è quello di raddoppiarne le dimensioni, ma questo porta a un nuovo utilizzo del 25% della tabella!

In effetti, supponiamo che l'hashtable abbia 16 slot, quando inserisco l'ottavo numero di elemento, finirò gli slot buoni e dovrò reash. Lo raddoppierò e ora il tavolo ha 32 slot con solo 8 di essi occupati, il che è uno spreco del 75%!

Questo è il prezzo da pagare per avere una "costante" tempo di recupero (in termini di limite superiore per il numero di accesso / confronto).

Ho ideato uno schema diverso, però: a partire da una potenza di 2 maggiore di 1, se la tabella ha n slot e n è una potenza di due, aggiungi n / 2 slot altrimenti aggiungi n / 3 slot: 

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

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

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

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

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

ecc.

Insieme al presupposto che il riassestamento avverrà solo quando la tabella sarà piena al 50%, questo porta al fatto che la tabella sarà vuota solo al 66% (1/3) anziché vuota al 75% (1/4) dopo un reash (cioè il caso peggiore).

Ho anche capito (ma devo ancora controllare la matematica) che ingrandendo ogni volta di sqrt (n), lo spazio sprecato si avvicina asintoticamente al 50%.

Ovviamente il prezzo da pagare per un minore consumo di memoria è l'aumento del numero di reash che sarà necessario alla fine. Purtroppo niente viene gratis.

Investigherò ulteriormente se qualcuno è interessato.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top