Comment calculer le code de hachage d'une chaîne à la main?

Je me demandais comment calculer le code de hachage pour une chaîne donnée par la main. Je comprends qu'en Java, vous pouvez faire quelque chose comme:

String me = "What you say what you say what?";  
long whatever = me.hashCode();

Que tout va bien et dandy, mais je me demandais comment le faire à la main. Je connais la formule pour calculer le code de hachage d'une chaîne est quelque chose comme:

S0 X 31 ^ (n-1) + S1 X 31 ^ (n-2) + .... + S(n-2) X 31 + S(n-1)

Où S indique le caractère dans la chaîne, et n est la longueur de la chaîne. À l'aide de 16 bits unicode puis, le premier caractère de la chaîne de moi, ce serait calculé comme:

87 X (31 ^ 34)

Cependant, qui crée un incroyablement grand nombre. Je ne peux pas imaginer l'ajout de tous les personnages ensemble comme ça. Ainsi, pour le calcul de la plus faible-de l'ordre de 32 bits du résultat, alors, que ferais-je? Longtemps que ce soit d'au-dessus est égal à -957986661 et je ne suis pas la façon de calculer cela?

OriginalL'auteur thomascirca | 2010-09-25

  1. 14

    Prendre un coup d'oeil au code source de java.lang.String.

    /**
 * Returns a hash code for this string. The hash code for a
 * <code>String</code> object is computed as
 * <blockquote><pre>
 * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 * </pre></blockquote>
 * using <code>int</code> arithmetic, where <code>s[i]</code> is the
 * <i>i</i>th character of the string, <code>n</code> is the length of
 * the string, and <code>^</code> indicates exponentiation.
 * (The hash value of the empty string is zero.)
 *
 * @return  a hash code value for this object.
 */
public int hashCode() {
    int h = hash;
    int len = count;
    if (h == 0 && len > 0) {
        int off = offset;
        char val[] = value;
        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}
    merci pour améliorer ma réponse! 🙂
    Je reçois l'idée de base (je peux calculer des petites chaînes) mais, quand la chaîne est grande, je ne suis pas sûr de ce qu'il faut faire.
    la taille de la chaîne n'est pas important. Ce sont les valeurs de l'aide d'une boucle, il n'a pas d'importance combien de temps de la boucle, c'est plus compliqué.

    OriginalL'auteur dty

  2. 6

    La plupart des fonctions de hachage de ce genre de calculer la valeur de hachage modulo certains grand nombre (par exemple, un grand premier). Cela évite les débordements et maintient la plage de valeurs retournées par la fonction à l'intérieur de la plage spécifiée. Mais cela signifie aussi une gamme infinie de valeurs d'entrée obtiendrez une valeur de hachage à partir d'un ensemble fini de valeurs possibles (c'est à dire [0,le module)), d'où le problème de collisions de hachage.

    Dans ce cas, le code devrait ressembler à quelque chose comme ceci:

       public int hash(String x){
        int hashcode=0;
        int MOD=10007;
        int shift=29;
        for(int i=0;i<x.length();i++){
            hashcode=((shift*hashcode)%MOD+x.charAt(i))%MOD;
        }
        return hashcode; 
    }

    Exercice pour le lecteur:

    Voir le code pour le hashCode fonction de java.util.Chaîne de caractères. Pouvez-vous voir pourquoi il n'utilise pas de module explicitement?

    Je ne vois pas... Pourriez-Vous l'expliquer?
    Notez que x%2^n = x&(2^n-1). Donc, si vous ne l'arithmétique modulo 2^n, vous avez juste besoin de garder les n derniers bits de votre valeur, en supprimant les bits supérieurs. Maintenant, pensez à ce qui se produit lorsque vous utilisez un int pour représenter votre valeur. Toute l'arithmétique vous aura pour résultat que seuls les 32 derniers bits de gauche plus de. Voila, vous avez l'arithmétique modulo 2^32.
    La droite. Comment n'avez-vous pas voir que jjczopek >_<.

    OriginalL'auteur MAK