Bonne fonction de hachage pour les chaînes

160

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.

Leif Andersen
la source
4
Les bonnes fonctions de hachage dépendent fortement de l'entrée du hachage et des exigences de l'algorithme. Un tel hachage ne sera pas très bon si toutes vos chaînes commencent par les mêmes cinq caractères, par exemple. Cela aura également tendance à aboutir à une distribution normale.
WhirlWind
1
Copie
Michael Mrozek
14
Pourquoi ne pouvez-vous pas utiliser Stringle sien hashCode()?
Bart Kiers
@WhirlWind, vrai, je ne suis pas sûr de ce que les chaînes auront, à part cela, il s'agira probablement de texte anglais.
Leif Andersen
@Barl, principalement parce que mon professeur nous a dit d'implémenter notre propre foncteur de hachage ... et la raison pour laquelle je ne voulais pas utiliser Java, c'était parce que c'était générique, et j'imagine qu'un foncteur de hachage plus spécifique serait mieux.
Leif Andersen

Réponses:

161

Habituellement, les hachages ne feront pas de somme, sinon stopet potsauront 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:

int hash = 7;
for (int i = 0; i < strlen; i++) {
    hash = hash*31 + charAt(i);
}
Jonathanasdf
la source
@jonathanasdf Comment pouvez-vous dire qu'il vous donne toujours une clé de hachage unique. Y a-t-il une preuve mathématique? Je pense que nous devons prendre un mod de hachage avec un autre nombre premier plus grand, sinon un problème de débordement se produit.
devsda
17
@devsda Il n'a pas dit toujours unique, il a dit que plus susceptible d'être unique. Quant à savoir pourquoi, une recherche rapide sur google révèle cet article: computinglife.wordpress.com/2008/11/20/… expliquant pourquoi 31 a été utilisé pour le hachage de chaîne Java. Il n'y a pas de preuve mathématique donnée, mais cela explique le concept général des raisons pour lesquelles les nombres premiers fonctionnent mieux.
Pharap
2
Merci beaucoup d'avoir clarifié l'idée de faire un meilleur hachage. Juste pour vérifier - La valeur de retour hashCode () sera utilisée par Java pour mapper vers un index de table avant de stocker l'objet. Donc, si hashCode () renvoie m, il fait quelque chose comme (m mod k) pour obtenir un index de la table de taille k. Est-ce correct?
whitehat
1
"hash = hash * 31 + charAt (i);" produit le même hash pour les spots, les tops, les stop, les opts et les pots.
Jack Straub
1
@maq Je pense que vous avez raison. Je ne sais pas à quoi je pensais.
Jack Straub
139

Si c'est une question de sécurité, vous pouvez utiliser la crypto Java:

import java.security.MessageDigest;

MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
messageDigest.update(stringToEncrypt.getBytes());
String encryptedString = new String(messageDigest.digest());

la source
93
Agréable. J'ai une application d'apprentissage automatique, faisant de la PNL statistique sur un grand corpus. Après quelques passages initiaux de normalisation morphologique sur les mots originaux dans le texte, je jette les valeurs de chaîne et utilise des codes de hachage à la place. Dans tout mon corpus, il y a environ 600 000 mots uniques, et en utilisant la fonction de hachage java par défaut, j'obtenais environ 3,5% de collisions. Mais si je SHA-256 la valeur de la chaîne et que je génère ensuite un hashcode à partir de la chaîne digérée, le taux de collision est inférieur à 0,0001%. Merci!
benjismith
3
Merci de fournir des informations sur les collisions et le nombre de mots. Très utile.
philipp
19
@benjismith Un sur un million est beaucoup trop grand ... est-ce que "moins de 0,0001%" est une manière oblique de dire "exactement 0"? Je doute vraiment que vous ayez vu une collision SHA-256 parce que cela n'a jamais été observé, nulle part, jamais; même pas pour SHA-1 160 bits. Si vous avez deux chaînes qui produisent le même SHA-256, la communauté de la sécurité aimerait les voir; vous serez mondialement connu ... d'une manière très obscure. Voir la comparaison des fonctions SHA
Tim Sylvester
7
@TimSylvester, vous avez mal compris. Je n'ai pas trouvé de collisions SHA-256. J'ai calculé le SHA-256, puis j'ai introduit les séquences d'octets résultantes dans une fonction Java "hashCode" typique, car j'avais besoin d'un hachage 32 bits. C'est là que j'ai trouvé les collisions. Rien de remarquable :)
benjismith
1
N'y a-t-il pas une différence entre le «hachage» et le «chiffrement»? Je comprends que MessageDigest est une fonction de hachage à sens unique, non? De plus, lorsque j'ai utilisé la fonction, j'ai obtenu la chaîne hachée sous la forme d'un grand nombre de caractères UTF indésirables lorsque j'ai ouvert le fichier dans LibreOffice. Est-il possible d'obtenir la chaîne hachée sous la forme d'un groupe aléatoire de caractères alphanumériques au lieu de caractères UTF indésirables?
Nav
38

Vous devriez probablement utiliser String.hashCode () .

Si vous voulez vraiment implémenter vous-même hashCode:

Ne soyez pas tenté d'exclure des parties importantes d'un objet du calcul du code de hachage pour améliorer les performances - Joshua Bloch, Effective Java

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 fonction de hachage de chaîne implémentée dans toutes les versions antérieures à la version 1.2 a examiné au plus seize caractères, régulièrement espacés dans la chaîne, en commençant par le premier caractère. Pour les grandes collections de noms hiérarchiques, tels que les URL, cette fonction de hachage a affiché un comportement terrible.

Frederik
la source
1
Si l'on utilise une collection à double hachage, il peut être intéressant que le premier hachage soit vraiment rapide et sale. Si l'on a mille longues chaînes, dont la moitié est mappée par une fonction minable à une valeur particulière, et la moitié est mappée à des valeurs distinctes, les performances dans une table à hachage simple seraient mauvaises, mais les performances dans un double- table hachée, où le deuxième hachage a examiné la chaîne entière, pourrait être presque deux fois celle d'une table hachée unique (car la moitié des chaînes n'auraient pas besoin d'être hachées complètement). Cependant, aucune des collections Java standard n'effectue un double hachage.
supercat
Le lien Java efficace est rompu @Frederik
KGs
17

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

Pyrolistique
la source
2
Je le fais dans le cadre de la classe, et une partie de la tâche consiste à écrire plusieurs fonctions de hachage différentes. Le professeur nous a dit d'obtenir de l'aide extérieure pour les «meilleurs».
Leif Andersen
20
Si vous avez besoin de cohérence entre les versions et implémentations de JVM, vous ne devez pas vous fier à .hashCode(). Utilisez plutôt un algorithme connu.
Stephen Ostermiller
7
L'algorithme pour String::hashCodeest spécifié dans le JDK, il est donc aussi portable que l'existence même de la classe java.lang.String.
yshavit
12

Guava'sHashFunction ( javadoc ) fournit un hachage décent non crypto-fort.

Mike Samuel
la source
1
Il est toujours en version bêta à partir de ce commentaire
ThomasRS
1
Et maintenant 404'd.
Shawn
8

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.

private static final char[] hex = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

public static String byteArray2Hex(byte[] bytes) {
    StringBuffer sb = new StringBuffer(bytes.length * 2);
    for(final byte b : bytes) {
        sb.append(hex[(b & 0xF0) >> 4]);
        sb.append(hex[b & 0x0F]);
    }
    return sb.toString();
}

public static String getStringFromSHA256(String stringToEncrypt) throws NoSuchAlgorithmException {
    MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
    messageDigest.update(stringToEncrypt.getBytes());
    return byteArray2Hex(messageDigest.digest());
}

Peut-être que cela peut aider quelqu'un

Festus Tamakloe
la source
Vous pouvez simplement passer le tableau d'octets à messageDigest.update ().
szgal
byteArray2Hex () - c'est parfaitement ce que je cherchais! Merci beaucoup :)
Krzysiek
5
// djb2 hash function
unsigned long hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

Logique source derrière la fonction de hachage djb2 - SO

Pratik Deoghare
la source
1
Je pense que c'est juste un nombre premier pour commencer, pour que nous ayons moins de collisions.
CornSmith
5

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 charvaleurs 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.

Thomas Pornin
la source
Cette fonction de hachage est tellement meilleure que celle fournie avec java.
clankill3r
3

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."

Dean J
la source
1

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.

Yefei
la source
1

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)

static unsigned long sdbm(unsigned char *str)
{   
    unsigned long hash = 0;
    int c;
    while (c = *str++)
            hash = c + (hash << 6) + (hash << 16) - hash;

    return hash;
}
Anchal
la source
0
         public String hashString(String s) throws NoSuchAlgorithmException {
    byte[] hash = null;
    try {
        MessageDigest md = MessageDigest.getInstance("SHA-256");
        hash = md.digest(s.getBytes());

    } catch (NoSuchAlgorithmException e) { e.printStackTrace(); }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < hash.length; ++i) {
        String hex = Integer.toHexString(hash[i]);
        if (hex.length() == 1) {
            sb.append(0);
            sb.append(hex.charAt(hex.length() - 1));
        } else {
            sb.append(hex.substring(hex.length() - 2));
        }
    }
    return sb.toString();
}
Charaf JRA
la source
-1

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»

int keyHash(string key)
{
    unsigned int k = (int)key.length();
    unsigned int u = 0,n = 0;

    for (Uint i=0; i<k; i++)
    {
        n = (int)key[i];
        u += 7*n%31;
    }
    return u%139;
}

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.

int keyHash(string key)
{
    unsigned int k = (int)key.length();
    unsigned int u = 0,n = 0;

    for (Uint i=0; i<k; i++)
    {
        n = (int)key[i];
        u += i*n%31;
    }
    return u%139;
}
Kanthonye
la source
-1

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.

int generatehashkey(const char *name)
{
        int x = tolower(name[0])- 97;
        if (x < 0 || x > 25)
           x = 26;
        return x;
}

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

Donnant le texte suivant comme entrée: Atticus a dit à Jem un jour: «Je préfère que vous tiriez sur des boîtes de conserve dans l'arrière-cour, mais je sais que vous vous attaquerez aux oiseaux. Tirez sur tous les geais bleus que vous voulez, si vous pouvez les frapper, mais rappelez-vous que c'est un péché de tuer un oiseau moqueur. Ce fut la seule fois où j'entendis Atticus dire que c'était un péché de faire quelque chose, et j'en demandai à Mlle Maudie. «Ton père a raison», dit-elle. «Les Mockingbirds ne font rien d'autre que faire de la musique pour que nous puissions en profiter. Ils ne mangent pas les jardins des gens, ne nichent pas dans des berceaux de maïs, ils ne font rien mais chantent tout leur cœur pour nous. C'est pourquoi c'est un péché de tuer un oiseau moqueur.

Ce serait la sortie:

0 --> a a about asked and a Atticus a a all after at Atticus
1 --> but but blue birds. but backyard
2 --> cribs corn can cans
3 --> do dont dont dont do dont do day
4 --> eat enjoy. except ever
5 --> for for fathers
6 --> gardens go
7 --> hearts heard hit
8 --> its in it. I it I its if I in
9 --> jays Jem
10 --> kill kill know
11 --> 
12 --> mockingbird. music make Maudie Miss mockingbird.”
13 --> nest
14 --> out one one only one
15 --> peoples
16 --> 17 --> right remember rather
18 --> sin sing said. she something sin say sin Shoot shot said
19 --> to Thats their thing they They to thing to time the That to the the tin to
20 --> us. up us
21 --> 
22 --> why was was want
23 --> 
24 --> you you youll you
25 --> 
26 --> Mockingbirds  Your em Id
utilisateur2311285
la source
2
Une bonne fonction de hachage distribue les valeurs de manière égale entre les compartiments.
Jonathan Peterson
-1

Cela évitera toute collision et ce sera rapide jusqu'à ce que nous utilisions le décalage dans les calculs.

 int k = key.length();
    int sum = 0;
    for(int i = 0 ; i < k-1 ; i++){
        sum += key.charAt(i)<<(5*i);
    }
kamal el-deen shair
la source