Bonne fonction de hachage pour les chaînes

si c'est un truc de sécurité, Vous pouvez utiliser Java crypto:

import java.security.MessageDigest;

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

vous devriez probablement utiliser la chaîne .hashCode () .

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

ne soyez pas tenté d'exclure des parties d'un objet à partir d' le calcul du code de hachage pour améliorer performance -- Joshua Bloch, Effective Java

utilisant seulement les cinq premiers caractères est un mauvaise idée . Penser noms hiérarchiques, tels que URLs: 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 seau dans une carte de hachage, présentant des performances terribles.

Voici une histoire de guerre paraphrasée sur le hashcode de chaîne de " Java efficace ":

la fonction de hachage de chaîne mise en œuvre dans tous les rejets antérieurs à 1.2 examinés au plus seize caractères, uniformément réparties sur toute la chaîne, en commençant avec le premier caractère. Pour les grands collections de noms hiérarchiques, comme Url, cette fonction de hachage affiche comportement terrible.

Si vous faites cela en Java, alors pourquoi le faites-vous? Il suffit d'appeler .hashCode() sur la chaîne

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

cette fonction fournie par Nick est bonne mais si vous utilisez new String(byte[] bytes) pour faire la transformation en String, elle a échoué. Vous pouvez utiliser cette fonction pour le 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

// 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;
}

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

si vous voulez voir les implémentations standard de l'industrie, je regarderais java.sécurité.MessageDigest .

" les condensés de messages sont des fonctions de hachage unidirectionnel sécurisées qui prennent des données de taille arbitraire et produisent une valeur de hachage de longueur fixe."

FNV-1 est une bonne fonction de hachage pour les cordes.

pour les longues chaînes (plus longues que, disons, environ 200 caractères), vous pouvez obtenir de bonnes performances de la fonction de hachage MD4 . En tant que fonction cryptographique, elle a été cassée il y a environ 15 ans, mais à des fins non cryptographiques, elle est encore très bonne, et étonnamment rapide. Dans le contexte de Java, vous devrez convertir les 16 bits char valeurs en mots de 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 trop de travail dans le cadre d'une affectation en classe, mais cela vaut la peine d'essayer.

sdbm:cet algorithme a été créé pour sdbm (a public-domain reimplementation of ndbm) database library

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;
}

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 comme entrée une chaîne de longueur arbitraire.

         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();
}

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

 int k = key.length();
    int sum = 0;
    for(int i = 0 ; i < k-1 ; i++){
        sum += key.charAt(i)<<(5*i);
    }

C'est une bonne idée de travailler avec des nombres impairs en essayant de développer une bonne fonction hast pour la chaîne. cette fonction prend une corde et renvoie une valeur d'index, jusqu'ici son travail assez bon. et a moins de collision. l'indice varie de 0 à 300 peut-être même plus que cela, mais je n'ai pas obtenu plus haut jusqu'à présent, même avec de longs mots comme" ingénierie é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'indice comme il augmenter comme le mot "ours" (0*b) + (1*e) + (2*a) + (3*r) qui vous donnera une valeur int pour jouer avec. la première fonction de hachage au-dessus de collision à "ici" et" entendre " mais encore grand à donner quelques bonnes valeurs uniques. celui-ci n'entrent pas en collision avec le "ici" et "entendre" parce que je multiplie chaque caractère à l'indice 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;
}

Voici une fonction de hachage simple que j'utilise pour une table de hachage que j'ai construit. Il s'agit essentiellement de 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 est les mots sont hachurés selon leur première lettre. Donc, le mot commençant par " a " serait d'obtenir une clé de hachage de 0, b 1 et ainsi de suite et 'z' 25. Les nombres et les symboles auraient une clé de hachage de 26. Il y a un avantage de cette fournit; vous pouvez calculer facilement et rapidement où un mot donné serait indexé dans la table de hachage depuis son tout 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 dit à Jem un jour, "je préférerais que vous tirez sur les boîtes de conserve dans le jardin, mais je sais que vous allez après les oiseaux. Tirez sur tous les blue jays tu veux, si tu peux les frapper, mais c'est un péché de tuer un oiseau moqueur."Ce fut la seule fois où j'ai J'ai déjà entendu Atticus dire que c'était un péché de faire quelque chose, et J'ai demandé à Mademoiselle Maudie à ce sujet. "Votre père a raison," dit-elle. "Les oiseaux moqueurs ne fais une chose, sauf faire de la musique pour qu'on en profite. Ils ne mangent pas jusqu' les jardins des gens, ne nichent pas dans des cages à maïs, ils ne font pas une chose mais chantez leurs cœurs pour nous. C'est pourquoi c'est un péché de tuer un mockingbird.

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 don’t don’t don’t do don’t do day
4 --> eat enjoy. except ever
5 --> for for father’s
6 --> gardens go
7 --> hearts heard hit
8 --> it’s in it. I it I it’s 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 --> people’s
16 --> 17 --> right remember rather
18 --> sin sing said. she something sin say sin Shoot shot said
19 --> to That’s 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 you’ll you
25 --> 
26 --> “Mockingbirds ” “Your ‘em “I’d