47

Javaのハッシュコード関数を使用して、異なる文字列に対して同じハッシュコードを使用することは可能ですか?または可能であれば、その可能性は何%ですか?

4

12 に答える 12

67

Java ハッシュ コードは 32 ビットです。ハッシュ可能な文字列の数は無限です。

そうです、衝突があります。パーセンテージは無意味です。無限の数のアイテム (文字列) と有限数の可能なハッシュがあります。

于 2012-04-11T08:26:13.773 に答える
30

はい。多くの。

次のペアを見てください

  • 「FB」と「えあ」

その中の文字が同じでなくても、同じハッシュコードを返すことができます。

基本的には、文字列内の文字の合計に整数を掛けたものです。

于 2012-04-11T08:26:09.180 に答える
8

もし可能ならその可能性は何％ですか？

それは特に意味のある質問ではありません。

ただし、String::hashcode関数またはオブジェクトを生成する方法に体系的なバイアスがない限り、2 つの異なる (等しくない)オブジェクトが同じハッシュ コードを持つString確率は 2 32分の 1 になります。String

これは、可能なすべての文字列値のセットから文字列がランダムに選択されることを前提としています。セットを色々と制限すると、確率は上記の数値とは異なります。(例えば、「FB」/「Ea」の衝突が存在するということは、2 文字列すべてのセットで衝突する確率が通常よりも高いことを意味します。)

注意すべきもう 1 つのことは、ランダムに選択された 2 32 個の異なる文字列 (はるかに大きな偏りのない文字列のセットから) がハッシュの衝突を持たない可能性はほとんどないということです。その理由を理解するには、誕生日のパラドックスに関するウィキペディアのページを読んでください。

実際には、2 32の異なる文字列のセットでハッシュ衝突を起こさない唯一の方法は、文字列を選択または生成することです。ランダムに生成された文字列を選択してセットを形成することでさえ、計算コストが高くなります。String::hashCodeこのようなセットを効率的に生成するには、(幸いなことに) 指定されているアルゴリズムのプロパティを活用する必要があります。

于 2012-04-11T08:41:03.177 に答える
7

これはあなたの質問に直接答えることはありませんが、役に立てば幸いです。

以下は のソースコードです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;
}
于 2012-04-11T08:25:31.773 に答える
6

はい、2 つの文字列が同じハッシュコードを持つことは可能です。ウィキペディアの記事を見ると、両方が同じハッシュコード"FB"を持つことがわかり"Ea"ます。メソッド コントラクトには、ahashCode()を使用して同等性を比較する必要があるとは書かれていません。そのために使用したいと考えてequals()います。

Java 1.2 以降、 Stringは、 string のテキスト全体に対して積和アルゴリズムを使用してhashCode()実装されます。

于 2012-04-11T08:30:21.773 に答える
4

はい、ピジョンホールの概念の定義により、2 つの異なる文字列が同じハッシュコードを生成する可能性があり、コードは常にそのような条件に対応するように記述されている必要があります (通常、壊れないことによって)。

于 2012-04-11T08:25:40.540 に答える
3

ランダムな文字列の衝突の割合は最小限に抑える必要があります。ただし、外部ソースから文字列をハッシュすると、攻撃者は同じハッシュコードを持つ数十万の文字列を簡単に作成できます。Java HashMap では、これらはすべて同じバケットにマップされ、効果的にマップをリンクされたリストに変換します。マップへのアクセス時間は、一定ではなくマップ サイズに比例し、サービス拒否攻撃につながります。

プレゼンテーションへのリンクの詳細については、Web アプリケーション プラットフォームに対する効果的な DoS 攻撃に関するこのページを参照してください。

于 2012-04-11T11:28:20.503 に答える