String.hashCode（）は非効率的ですか？

Question

source code of java.lang.String of openjdk-1.6を見たとき、私はString.hashCode（）は素数として31を使用し、今、私はこれを見てする理由は、私はハッシュコードを比較するかどうかを念頭に置いていた疑問だった

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

を計算することを見ましたがString.equalsはString.equalsを大幅に高速化します。しかし、今のhashCodeを見て、次の質問は、私の心に来る：

• が大きくプライム助け、より良い回避の衝突ではないでしょう、少なくとも短い文字列のために、例えばそれを見て「BC」を「同じハッシュを持っていますAb "（アスキー文字は地域65-122に住んでいるので、それよりも高い上位はない）
• 31をプライムとして使用するか、それが一般的であるために使用されるランダムなものを使用するのが意識的な決定ですか？
• 固定された文字列長の場合、ハッシュの衝突はどのくらいありえますか？この質問は、実際の内容を比較するのを避けるために、hashCodesとStringの長さを比較しても文字列をどれくらいよく比較できるかという元の質問です。
• 少し話題があります：多分理由はありますかString.equalsは追加のショートカットとしてhashCodesを比較しませんか？
• もう少しオフトピック：私たちはと同じという内容の2つの文字列を持っていると仮定しますが、実際に内容を比較することなく平等を宣言する方法はありますか？私は推測することはできませんが、文字列の長さに至るまで、スペースは必然的に衝突するサイズに爆発しますが、いくつかの制限については、特定の文字セット、最大の文字列の長さ、制限する必要がありますそのようなハッシュ関数を持つことができる文字列スペース？

Answer 1

アスキー文字は領域65に住んでいるので、例えば、「BC」は「AB」（同じハッシュを持っていることを見て、少なくとも短い文字列のために、より良い、より大きなプライムヘルプ回避衝突はありません-122は、それよりも高いプライムではないでしょうか？）

文字列内の各文字は、65536（2^16）の値をとることができます。したがって、1文字または2文字の文字列の集合はintの数よりも大きく、ハッシュコードの計算方法は1文字または2文字の文字列の衝突を引き起こします（これは短い文字列と見なされます）。

キャラクタセットを制限すると、衝突の回数を減らすハッシュ関数が見つかります（下記参照）。

良いハッシュは、出力の良好な分布も提供しなければならないことに注意してください。コメントin this codeを33を使用して埋葬し、以下の理由（重点鉱山）を与えます。

バリエーションのchi^2値[...]を比較すると、33番の数値も最高の値ではありません。しかし、33番と17,31,63,127,129のような他のいくつかの同様に良い数は、可能な乗数の大きなセットの残りの数に大きな利点があります。乗算演算は、より高速な演算に置き換えることができます。 1回のシフトと1回の加算または減算のいずれかの操作を加えたものです。そして、ハッシュ関数は良い分布をしなければならず、計算が非常に高速でなければならないので、それらの数は好ましいものでなければならない。。

これらの式は、しばらく前に設計されました。今では理想的ではないように見えても、Stringクラスの規約に文書化されているため、実装を変更することは不可能です。

プライムとして31を使用するか、それが一般的であるために使用されるランダムなものを使用するのが意識的な決定ですか？固定文字列の長さが与えられ、ハッシュ衝突でどのように可能性が

Why does Java's hashCode() in String use 31 as a multiplier?

？

それぞれの可能なint値は、ハッシュコード関数の結果である可能性が同じであると仮定すると、衝突確率は2^32で1です。

String.equalsは、追加のショートカットとしてhashCodesを比較しない理由がありますか？

Why does the equals method in String not use hash?

我々は2つの同一内容の文字列が、別のインスタンスを持っていると仮定すると：実際に内容を比較することなく平等を主張する方法はありますか？

文字列に制約がありません。あなたは文字列をインターンにしてから参照の等価性（==）を調べることができますが、多くの文字列が含まれていると非効率的になります。

このようなハッシュ関数を使用できるように文字列スペースをどのくらい制限する必要がありますか？

あなただけの小さなキャップの文字（26文字）を許可する場合は、6つの文字（包括的）に長さ0の文字列のためのユニークなハッシュを生成したハッシュ関数（sum(i=0..6) (26^i) = 3.10^8）を設計できます。