Bonne Fonction de Hachage pour les Chaînes

Question

J'essaie de penser à une bonne fonction de hachage pour les chaînes. Et je me disais que ça pourrait être une bonne idée de résumer les valeurs unicode pour les cinq premiers caractères de la chaîne (en supposant qu'il a cinq, sinon arrêter, où elle se termine). Serait-ce une bonne idée, ou est-il mauvais?

Je fais cela en Java, mais je ne peux pas imaginer que ferait beaucoup de différence.

Answer 1

Généralement les hachages de ne pas faire des sommes, sinon, arrêter et pots aura le même hash.

et vous n'auriez pas de limite pour les n premiers caractères parce que sinon, la maison et les maisons ont le même hash.

Généralement hashs prendre des valeurs et de le multiplier par un nombre premier (il est plus susceptible de générer unique de hachages) de Sorte que vous pourriez faire quelque chose comme:

int hash=7;
for (int i=0; i < strlen; i++) {
    hash = hash*31+charAt(i);
}

Answer 2

Vous devriez probablement utiliser String.hashCode().

Si vous voulez vraiment mettre en œuvre hashCode vous-même:

Ne succombez pas à exclure des parties d'un objet à partir d' le code de hachage de calcul pour améliorer performance -- Joshua Bloch, Efficace Java

En utilisant seulement les cinq premiers caractères est une mauvaise idée. Pensez hiérarchique des noms, tels que les Url: ils ont tous le même code de hachage (parce qu'elles commencent par "http://", ce qui signifie qu'ils sont stockés dans le même seau dans une table de hachage de la carte, présentant terrible de la performance.

Voici une histoire de la guerre paraphrase sur la Chaîne hashCode de "Effective Java":

La Chaîne de hachage une fonction d' dans toutes les versions antérieures à 1.2 examiné au plus seize personnages, uniformément réparties sur toute la chaîne, en commençant avec le premier caractère. Pour les grands les collections de l'hiérarchique des noms, comme Url, cette fonction de hachage affiche comportement terrible.

Answer 3

Si vous faites cela en Java, alors pourquoi le faites-vous? Appelez simplement .hashCode() sur la chaîne

Answer 4

La goyave est HashFunction décent non-crypto-fort de hachage.