[C++] dizionario hash - funzione hash per stringhe, dimensione vettore

[matteo martis]

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]

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]

intentevo dire una funzione hash che spalma discretamente bene gli elementi nell'array...
CRC32 ??

[franzauker2.0]

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]

grazie!!!

[MItaly]

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.