PDA

Visualizza la versione completa : [C++] dizionario hash - funzione hash per stringhe, dimensione vettore


matteo martis
10-02-2013, 17:31
Salve!!!
devo creare un dizionario implementato con tabelle hash mediante albero binariodi ricerca di trabocco... vorrei sapere qual'č tra i metodi pių semplici quello pių efficiente per realizzare la funzione hash delle stringhe?... Dato che č dovrebbe essere realizzato mediante i template e che il tipo della chiave č un parametro di tipo, come posso fare per distinguere tra interi e stringhe.
Vorrei anche sapere in che modo scegliere la grandezza del vettore, tenendo presente che i vettori pių efficienti sono quelli la cui lunghezza č un numero primo vicino aad una potenza di due.
Grazie!!!

franzauker2.0
10-02-2013, 18:19
Cosa intendi per "efficiente"?
Se la semantica č quella propria del termine allora usa una funzione che non č un vero e proprio hash in senso proprio, ma č certamente molto efficiente, il venerabile CRC32.
Se invece intendevi "efficace" bisogna aprire (o meglio bisognerebbe) un bel discorsino.

matteo martis
10-02-2013, 18:43
intentevo dire una funzione hash che spalma discretamente bene gli elementi nell'array...
CRC32 ??

franzauker2.0
10-02-2013, 18:50
Originariamente inviato da matteo martis
intentevo dire una funzione hash che spalma discretamente bene gli elementi nell'array...
CRC32 ?? Sė, CRC32.
"spalma" implica che la vuoi efficace, non efficiente, il che dipende essenzialmente da quante saranno gli elementi (stringhe) inserite.
Nel tuo caso non serve chissā quale superfunzione, visto che gestirai le collisioni.
Anzi, per scopo di debug, ti conviene definire una funzione "scema" che NON spalmi affatto gli elementi, magari semplicemente scegliendo come posizione la 0 o la 1 se la lunghezza della stringa č pari o dispari, qualcosa di banale del genere.

Tornando alla domanda ce ne sono tante, per non dire tantissime, e per il tuo caso va benissimo anche la venerabile md5 (lascia perdere chi sostiene che non va bene blablabla), pių efficiente di SHA1, e pių di SHA-256, e decisamente pių di Whirlpool (anche perchč crea stringhe pių piccole).

matteo martis
10-02-2013, 18:57
grazie!!!

MItaly
10-02-2013, 21:14
MD5 & co. nascono come hash crittografici, se tutto quello che devi fare č usarle per calcolare la posizione in una hash table in genere sono inutilmente lenti, ci sono alternative pių semplici e veloci che danno comunque buone distribuzioni; anche solo con una ricerca su Google trovi un sacco di materiale in proposito.

Loading