J'essaie d'imaginer une bonne fonction de hachage pour les chaînes. Et je pensais que ce serait peut-être une bonne idée de résumer les valeurs Unicode pour les cinq premiers caractères de la chaîne (en supposant qu'elle en ait cinq, sinon arrêtez là où elle se termine). Est-ce que ce serait une bonne idée ou une mauvaise idée?
Je fais cela en Java, mais je n'imagine pas que cela ferait une grande différence.
String
le sienhashCode()
?Réponses:
Habituellement, les hachages ne feront pas de somme, sinon
stop
etpots
auront le même hachage.et vous ne le limiteriez pas aux n premiers caractères car sinon, la maison et les maisons auraient le même hachage.
Généralement, les hachages prennent des valeurs et les multiplient par un nombre premier (le rend plus susceptible de générer des hachages uniques) Vous pouvez donc faire quelque chose comme:
la source
Si c'est une question de sécurité, vous pouvez utiliser la crypto Java:
la source
Vous devriez probablement utiliser String.hashCode () .
Si vous voulez vraiment implémenter vous-même hashCode:
Utiliser uniquement les cinq premiers caractères est un mauvaise idée . Pensez aux noms hiérarchiques, tels que les URL: ils auront tous le même code de hachage (car ils commencent tous par "http: //", ce qui signifie qu'ils sont stockés sous le même compartiment dans une carte de hachage, présentant des performances terribles.
Voici une histoire de guerre paraphrasée sur le hashCode String de " Effective Java ":
la source
Si vous faites cela en Java, pourquoi le faites-vous? Appelez simplement
.hashCode()
la chaînela source
.hashCode()
. Utilisez plutôt un algorithme connu.String::hashCode
est spécifié dans le JDK, il est donc aussi portable que l'existence même de la classejava.lang.String
.Guava's
HashFunction
( javadoc ) fournit un hachage décent non crypto-fort.la source
404
'd.Cette fonction fournie par Nick est bonne mais si vous utilisez une nouvelle chaîne (octet [] octets) pour effectuer la transformation en chaîne, elle a échoué. Vous pouvez utiliser cette fonction pour ce faire.
Peut-être que cela peut aider quelqu'un
la source
Logique source derrière la fonction de hachage djb2 - SO
la source
On dit que FNV-1 est une bonne fonction de hachage pour les chaînes.
Pour les chaînes longues (plus longues que, disons, environ 200 caractères), vous pouvez obtenir de bonnes performances avec la fonction de hachage MD4 . En tant que fonction cryptographique, elle a été interrompue il y a environ 15 ans, mais à des fins non cryptographiques, elle est toujours très bonne et étonnamment rapide. Dans le contexte de Java, vous devrez convertir les
char
valeurs 16 bits en mots 32 bits, par exemple en regroupant ces valeurs en paires. Une implémentation rapide de MD4 en Java peut être trouvée dans sphlib . Probablement exagéré dans le contexte d'un travail en classe, mais cela vaut la peine d'essayer.la source
Si vous voulez voir les implémentations standard de l'industrie, je regarderais java.security.MessageDigest .
"Les résumés de messages sont des fonctions de hachage unidirectionnelles sécurisées qui prennent des données de taille arbitraire et produisent une valeur de hachage de longueur fixe."
la source
voici un lien qui explique de nombreuses fonctions de hachage différentes, pour l'instant je préfère la fonction de hachage ELF pour votre problème particulier. Il prend en entrée une chaîne de longueur arbitraire.
la source
sdbm: cet algorithme a été créé pour la bibliothèque de base de données sdbm (une réimplémentation du domaine public de ndbm)
la source
la source
C'est une bonne idée de travailler avec un nombre impair lorsque vous essayez de développer une bonne fonction hast pour la chaîne. cette fonction prend une chaîne et renvoie une valeur d'index, jusqu'à présent, son travail est plutôt bon. et a moins de collision. l'indice va de 0 à 300 peut-être même plus que cela, mais je n'ai pas été plus élevé jusqu'à présent, même avec de longs mots comme «génie électromécanique»
une autre chose que vous pouvez faire est de multiplier chaque caractère int parse par l'index au fur et à mesure qu'il augmente comme le mot "ours" (0 * b) + (1 * e) + (2 * a) + (3 * r) ce qui vous donnera une valeur int avec laquelle jouer. la première fonction de hachage ci-dessus se heurte à «ici» et à «entendre» mais toujours excellente pour donner de bonnes valeurs uniques. celui ci-dessous n'entre pas en collision avec «ici» et «entendre» car je multiplie chaque caractère avec l'index à mesure qu'il augmente.
la source
Voici une fonction de hachage simple que j'utilise pour une table de hachage que j'ai créée. Son essentiellement pour prendre un fichier texte et stocke chaque mot dans un index qui représente l'ordre alphabétique.
Ce que cela fait essentiellement, c'est que les mots sont hachés en fonction de leur première lettre. Ainsi, un mot commençant par «a» obtiendrait une clé de hachage de 0, «b» aurait 1 et ainsi de suite et «z» serait de 25. Les nombres et les symboles auraient une clé de hachage de 26. Cela présente un avantage. ; Vous pouvez calculer facilement et rapidement où un mot donné serait indexé dans la table de hachage puisque tout est dans un ordre alphabétique, quelque chose comme ceci: Le code peut être trouvé ici: https://github.com/abhijitcpatil/general
Ce serait la sortie:
la source
Cela évitera toute collision et ce sera rapide jusqu'à ce que nous utilisions le décalage dans les calculs.
la source