10

有名なJDKのドキュメントには次のように書かれています：java.lang.String.hashCode()

String オブジェクトのハッシュ コードは次のように計算されます。

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

は文字列の * * 番目の文字、 は文字列の長さであり、べき乗を示しintます。s[i]in^

この式の標準的な実装は次のとおりです。

int hash = 0;
for (int i = 0; i < length; i++)
{
    hash = 31*hash + value[i];
}
return hash;

これを見ると、アルゴリズムのコースで寝ていたような気がします。その数式は、上記のコードにどのように変換されますか?

4

5 に答える 5

25

ループを展開します。次に、次のようになります。

int hash = 0;

hash = 31*hash + value[0];
hash = 31*hash + value[1];
hash = 31*hash + value[2];
hash = 31*hash + value[3];
...
return hash;

これで、いくつかの数学的操作を行うことができます。最初のハッシュ値に 0 を挿入します。

hash = 31*(31*(31*(31*0 + value[0]) + value[1]) + value[2]) + value[3])...

もう少し単純化します。

hash = 31^3*value[0] + 31^2*value[1] + 31^1*value[2] + 31^0*value[3]...

そして、それは本質的に与えられた元のアルゴリズムです。

于 2009-05-04T22:26:17.557 に答える
10

帰納法による証明:

T1(s) = 0 if |s| == 0, else s[|s|-1] + 31*T(s[0..|s|-1])
T2(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
P(n) = for all strings s s.t. |s| = n, T1(s) = T2(s)

Let s be an arbitrary string, and n=|s|
Base case: n = 0
    0 (additive identity, T2(s)) = 0 (T1(s))
    P(0)
Suppose n > 0
    T1(s) = s[n-1] + 31*T1(s[0:n-1])
    T2(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] = s[n-1] + 31*(s[0]*31^(n-2) + s[1]*31^(n-3) + ... + s[n-2]) = s[n-1] + 31*T2(s[0:n-1])
    By the induction hypothesis, (P(n-1)), T1(s[0:n-1]) = T2(s[0:n-1]) so
        s[n-1] + 31*T1(s[0..n-1]) = s[n-1] + T2(s[0:n-1])
    P(n)

私はそれを持っていると思います、そして証明が要求されました.

于 2009-05-04T22:31:50.477 に答える
9

最初の数回の繰り返しを見ると、パターンが現れ始めていることがわかります。

ハッシュ0 = 0 + s 0 = s 0
ハッシュ1 = 31(ハッシュ0 ) + s 1 = 31(s 0 ) + s 1
ハッシュ2 = 31(ハッシュ1 ) + s 2 = 31(31(s 0 ) + s 1 ) + s 2 = 31 2 (s 0 ) + 31(s 1 ) + s 2
...
于 2009-05-04T22:31:46.577 に答える
0

すべての文字から文字列のハッシュコードを数えるのはまったく無駄では​​ありませんか? HashSet にフルパスを入れたファイル名またはクラス名を想像してみてください。または、「ハッシュセットは常にリストよりも優れている」ため、リストの代わりに文字列ドキュメントのハッシュセットを使用する人。

私は次のようなことをします：

int off = offset;
char val[] = value;
int len = count;

int step = len <= 10 ? 1 : len / 10;

for (int i = 0; i < len; i+=step) {
   h = 31*h + val[off+i];
}
hash = h

最後に、ハッシュコードはヒントにすぎません。

于 2013-07-21T14:54:15.487 に答える