如何手动计算字符串的哈希码？

Question

我想知道如何手动计算给定字符串的哈希码.我知道在Java中,你可以这样做:

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

这都是好事和花花公子,但我想知道如何手工完成.我知道计算字符串哈希码的给定公式是这样的:

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

其中S表示字符串中的字符,n表示字符串的长度.然后使用16位unicode,字符串me中的第一个字符将被计算为:

87 X (31 ^ 34)

然而,这创造了一个疯狂的大数字.我无法想象像这样将所有角色加在一起.那么,为了计算最低阶32位的结果,我该怎么办？从上面的长度等于-957986661并且我不是如何计算的？

Answer 1

看一下源代码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;
}

Answer 2

这一类的最散列函数计算散列值模有较大的数值(如大素数).这样可以避免溢出,并将函数返回的值范围保持在指定范围内.但这也意味着无限范围的输入值将从有限的一组可能值(即[0,模数))获得哈希值,因此存在哈希冲突的问题.

在这种情况下,代码看起来像这样:

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

为读者练习:

请参阅hashCodejava.util.String函数的代码.你能明白为什么它没有明确使用模数吗？