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

我想知道如何计算给定字符串的哈希码。我明白，在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然后，从字符串的第一个字符我会被计算为：

87 X (31^34)

然而，创建一个疯狂大的数字。我无法想象像这样将所有角色加在一起。那么，为了计算最低阶的32位结果，我该怎么做？从上面长什么等于-957986661，我不是怎么计算的？

来源

2010-09-25 thomascirca

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

来源

2010-09-25 20:18:24 dty

@BalusC，感谢您提高我的答案！ :-) – dty 2010-09-25 20:33:42

我得到的基本思路（我可以计算小字符串），但是当字符串变大时，我不确定要做什么。 – thomascirca 2010-09-25 21:18:12

@ user458346，字符串的大小并不重要。这是使用循环的值，不管循环多长时间，它都会变得更复杂。 – 2010-09-25 22:00:20

大多数散列函数计算散列值modulo一些大的数目（例如一个大素数）。这可以避免溢出并将函数返回的值的范围保持在指定的范围内。但是这也意味着无限范围的输入值将从有限的可能值集（即[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; 
    }

读者练习：

看到代码为hashCode功能java.util.String。你能明白为什么它不明确使用模数？

来源

2010-09-25 20:23:09 MAK

我看不到...你能解释一下吗？ – jjczopek 2010-09-25 23:33:49

@jjczopek：注意'x％2^n = x＆（2^n-1）'。所以如果你用2^n算术模2，你只需要保留你的值的最后n位，丢弃任何更高的位。现在想想当你使用'int'来表示你的价值时会发生什么。你所做的任何运算都只会导致最后的32位被遗漏。瞧，你有算术模2^32。 – MAK 2010-09-26 20:29:18

没错。你怎么看不到那个jjzzkk> _ <。 – dcousens 2011-11-19 08:06:40

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

回答

相关问题