Algoritmo di hash string rapido con bassi tassi di collisione con numero intero a 32 bit [chiuso]
https://stackoverflow.com/questions/114085
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho un sacco di cose senza nome con cui mi piacerebbe fare ricerche rapide. Un "aardvark" è sempre un "aardvark" ovunque, quindi l'hashing della stringa e il riutilizzo dell'intero funzionerebbe bene per accelerare i confronti. L'intero set di nomi è sconosciuto (e cambia nel tempo). Che cos'è un algoritmo di hashing delle stringhe veloce che genererà valori di bit piccoli (32 o 16) e con un basso tasso di collisione?
Mi piacerebbe vedere un'implementazione ottimizzata specifica per C / C ++.
Soluzione
Una delle varianti FNV dovrebbe soddisfare i tuoi requisiti. Sono veloci e producono output distribuiti in modo abbastanza uniforme.
Altri suggerimenti
Murmur Hash è piuttosto carino.
Per un set di stringhe fisso usa gperf.
Se il tuo set di stringhe cambia devi scegliere una funzione hash. Questo argomento è stato discusso in precedenza:
Qual è l'algoritmo di hashing migliore da usare su una stringa stl quando si usa hash_map?
C'è anche un bell'articolo su eternallyconfuzzled.com .
L'hash One-at-a-Time di Jenkins per le stringhe dovrebbe assomigliare a questo:
#include <stdint.h>
uint32_t hash_string(const char * s)
{
uint32_t hash = 0;
for(; *s; ++s)
{
hash += *s;
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
Un'altra soluzione che potrebbe essere ancora migliore a seconda del caso d'uso è stringhe internate . Ecco come funzionano i simboli, ad es. in Lisp.
Una stringa internata è un oggetto stringa il cui valore è l'indirizzo dei byte stringa effettivi. Quindi si crea un oggetto stringa internato controllando una tabella globale: se la stringa è presente, si inizializza la stringa internata all'indirizzo di quella stringa. In caso contrario, lo si inserisce e quindi si inizializza la stringa internata.
Ciò significa che due stringhe internate costruite dalla stessa stringa avranno lo stesso valore, che è un indirizzo. Quindi se N è il numero di stringhe internate nel tuo sistema, le caratteristiche sono:
- Costruzione lenta (necessita di ricerca e possibilmente allocazione di memoria)
- Richiede dati globali e sincronizzazione nel caso di thread simultanei
- Confronta è O (1), perché stai confrontando gli indirizzi, non i byte di stringa effettivi (questo significa che l'ordinamento funziona bene, ma non sarà un ordinamento alfabetico).
Saluti,
Carl
Perché non usi semplicemente Boost librerie ? La loro funzione di hashing è semplice da usare e la maggior parte delle cose in Boost saranno presto parte dello standard C ++. Alcuni lo sono già.
Aumentare l'hash è facile come
#include <boost/functional/hash.hpp>
int main()
{
boost::hash<std::string> string_hash;
std::size_t h = string_hash("Hash me");
}
Puoi trovare boost su boost.org
Non è mai tardi per un buon argomento e sono sicuro che le persone sarebbero interessate ai miei risultati.
Avevo bisogno di una funzione hash e dopo aver letto questo post e fatto un po 'di ricerca sui link qui riportati, ho trovato questa variante dell'algoritmo di Daniel J Bernstein, che ho usato per fare un test interessante:
unsigned long djb_hashl(const char *clave)
{
unsigned long c,i,h;
for(i=h=0;clave[i];i++)
{
c = toupper(clave[i]);
h = ((h << 5) + h) ^ c;
}
return h;
}
Questa variante esegue l'hashing delle stringhe ignorando il caso, il che soddisfa la mia necessità di hashing delle credenziali di accesso degli utenti. "clave" è "chiave" in spagnolo. Mi dispiace per lo spagnolo ma è la mia lingua madre e il programma è scritto su di esso.
Beh, ho scritto un programma che genererà nomi utente da 'test_aaaa' a 'test_zzzz' e, per allungare le stringhe, ho aggiunto loro un dominio casuale in questo elenco: 'cloud-nueve.com', ' yahoo.com "," gmail.com "e" hotmail.com ". Quindi ognuno di loro sarebbe simile:
test_aaaa@cloud-nueve.com, test_aaab@yahoo.com, test_aaac@gmail.com, test_aaad@hotmail.com and so on.
Ecco l'output del test -'Colision entre XXX y XXX 'significa' Collision of XXX and XXX '. "Palabras" significa "parole" e "Totale" è lo stesso in entrambe le lingue.
Buscando Colisiones...
Colision entre 'test_phiz@hotmail.com' y 'test_juxg@cloud-nueve.com' (1DB903B7)
Colision entre 'test_rfhh@hotmail.com' y 'test_fpgo@yahoo.com' (2F5BC088)
Colision entre 'test_wxuj@hotmail.com' y 'test_pugy@cloud-nueve.com' (51FD09CC)
Colision entre 'test_sctb@gmail.com' y 'test_iohw@cloud-nueve.com' (52F5480E)
Colision entre 'test_wpgu@cloud-nueve.com' y 'test_seik@yahoo.com' (74FF72E2)
Colision entre 'test_rfll@hotmail.com' y 'test_btgo@yahoo.com' (7FD70008)
Colision entre 'test_wcho@cloud-nueve.com' y 'test_scfz@gmail.com' (9BD351C4)
Colision entre 'test_swky@cloud-nueve.com' y 'test_fqpn@gmail.com' (A86953E1)
Colision entre 'test_rftd@hotmail.com' y 'test_jlgo@yahoo.com' (BA6B0718)
Colision entre 'test_rfpp@hotmail.com' y 'test_nxgo@yahoo.com' (D0523F88)
Colision entre 'test_zlgo@yahoo.com' y 'test_rfdd@hotmail.com' (DEE08108)
Total de Colisiones: 11
Total de Palabras : 456976
Questo non è male, 11 collisioni su 456.976 (ovviamente usando l'intero 32 bit come lunghezza del tavolo).
L'esecuzione del programma utilizzando 5 caratteri, ovvero da "test_aaaaa" a "test_zzzzz", esaurisce effettivamente la memoria nella creazione della tabella. Di seguito è riportato l'output. 'No hay memoria para insertar XXXX (insertadas XXX)' significa 'Non è rimasta memoria per inserire XXX (XXX inserito)'. Fondamentalmente malloc () non è riuscito a quel punto.
No hay memoria para insertar 'test_epjcv' (insertadas 2097701).
Buscando Colisiones...
...451 'colision' strings...
Total de Colisiones: 451
Total de Palabras : 2097701
Il che significa solo 451 collisioni su 2.097.701 stringhe. Si noti che in nessuna delle occasioni, ci sono state più di 2 collisioni per codice. Che confermo che è un ottimo hash per me, poiché ciò di cui ho bisogno è convertire l'ID di accesso in un ID univoco a 40 bit per l'indicizzazione. Quindi lo uso per convertire le credenziali di accesso in un hash a 32 bit e uso gli 8 bit in più per gestire fino a 255 collisioni per codice, che sarebbe quasi impossibile generare risultati dei test.
Spero che questo sia utile a qualcuno.
Modifica
Come la casella di test è AIX, la eseguo usando LDR_CNTRL = MAXDATA = 0x20000000 per dargli più memoria e durare più a lungo, i risultati sono qui:
Buscando Colisiones ... Total de Colisiones: 2908 Total de Palabras: 5366384
Sono 2908 dopo 5.366.384 tentativi !!
MOLTO IMPORTANTE : compilando il programma con -maix64 (quindi il segno senza segno è 64 bit), il numero di collisioni è 0 per tutti i casi !!!
Dai un'occhiata a GNU gperf .
Bob Jenkins ha molte funzioni hash disponibili , tutte veloci e con bassi tassi di collisione.
Puoi vedere cosa usa .NET sul metodo String.GetHashCode () usando Reflector.
Immagino che Microsoft abbia trascorso molto tempo a ottimizzarlo. Hanno anche stampato in tutta la documentazione MSDN che è soggetta a modifiche in qualsiasi momento. Così chiaramente è sul loro "radar di ottimizzazione delle prestazioni" ; -)
Sarebbe abbastanza banale portarlo su C ++ anche io avrei pensato.
C'è qualche buona discussione in questa domanda precedente
E una bella panoramica su come scegliere le funzioni hash, nonché statistiche sulla distribuzione di molte altre comuni qui
Descritto qui è un modo semplice per implementarlo da soli: http : //www.devcodenote.com/2015/04/collision-free-string-hashing.html
Uno snippet dal post:
se diciamo che abbiamo un set di caratteri in maiuscolo, allora la lunghezza del set di caratteri è 26 dove A potrebbe essere rappresentato dal numero 0, B dal numero 1, C dal numero 2 e così via fino a Z dal numero 25. Ora, ogni volta che vogliamo mappare una stringa di questo set di caratteri su un numero univoco, eseguiamo la stessa conversione che abbiamo fatto nel caso del formato binario
CRC-32 . Ci sono circa un trilione di link su Google per questo.
