String クラスのhashCode()メソッドは、個別の String に対して一意のハッシュ コードを生成することが保証されていないことを理解しています。String キーを HashMap-s に入れる (デフォルトの String hashCode() メソッドを使用する) 使用法が多く見られます。putマップが、以前にマップに配置された HashMap エントリを真に異なる文字列キーで置き換えた 場合、この使用法の多くは、重大なアプリケーションの問題を引き起こす可能性があります。
String.hashCode() が異なる String に対して同じ値を返すというシナリオに遭遇する可能性はどのくらいですか? キーが文字列の場合、開発者はこの問題をどのように回避しますか?
開発者は、プログラムの正確さを達成するために、HashMap でのハッシュ衝突の問題を回避する必要はありません。
ここで理解すべき重要な点がいくつかあります。
必要に応じて、さらに詳細を以下に示します。
ハッシュが機能する方法（特に、あなたが尋ねたJavaのHashMapのようなハッシュされたコレクションの場合）は次のとおりです。
HashMap は、指定した値をバケットと呼ばれるサブコレクションのコレクションに格納します。これらは、実際には連結リストとして実装されています。これらの数には制限があります: iirc、デフォルトで開始する 16 で、マップにアイテムを追加すると数が増えます。値よりも多くのバケットが常に存在する必要があります。一例を挙げると、デフォルトを使用して、HashMap に 100 エントリを追加すると、256 バケットになります。
マップでキーとして使用できるすべての値は、ハッシュコードと呼ばれる整数値を生成できなければなりません。
HashMap は、このハッシュコードを使用してバケットを選択します。最終的には、これは整数値moduloをバケットの数にすることを意味しますが、その前に、Java の HashMap には内部メソッド ( と呼ばれるhash()) があり、ハッシュコードを微調整して、いくつかの既知の凝集の原因を減らします。
値を検索するとき、HashMap はバケットを選択し、.equals().
したがって、正確さのために衝突を回避する必要はなく、通常はパフォーマンスについて心配する必要もありません。ネイティブ Java クラス (String など) を使用している場合は、心配する必要はありません。ハッシュコード値を生成します。
独自の hashcode メソッドを作成する必要がある場合 (つまり、名前と姓のペアなど、複合値を持つクラスを作成した場合)、状況は少し複雑になります。ここで間違いを犯す可能性は十分にありますが、ロケット科学ではありません。まず、これを知っておいてください: 正確性を保証するためにしなければならない唯一のことは、等しいオブジェクトが等しいハッシュコードを生成することを保証することです。したがって、クラスの hashcode() メソッドを作成する場合は、equals() メソッドも作成する必要があり、それぞれで同じ値を調べる必要があります。
悪いが正しい hashcode() メソッドを書くことは可能です。これは、「等しいオブジェクトは等しいハッシュコードを生成する必要がある」という制約を満たすことを意味しますが、多くの衝突が発生するため、パフォーマンスは依然として非常に低くなります。
これの標準的な退化の最悪のケースは、すべてのケースに対して単純に定数値 (たとえば 3) を返すメソッドを作成することです。これは、すべての値が同じバケットにハッシュされることを意味します。
それでも機能しますが、パフォーマンスはリンクされたリストのパフォーマンスに低下します。
明らかに、そのようなひどい hashcode() メソッドを作成することはありません。適切な IDE を使用している場合は、IDE を生成することができます。StackOverflow はコードが大好きなので、上記の名/姓クラスのコードを次に示します。
public class SimpleName {
private String firstName;
private String lastName;
public SimpleName(String firstName, String lastName) {
super();
this.firstName = firstName;
this.lastName = lastName;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result
+ ((firstName == null) ? 0 : firstName.hashCode());
result = prime * result
+ ((lastName == null) ? 0 : lastName.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
SimpleName other = (SimpleName) obj;
if (firstName == null) {
if (other.firstName != null)
return false;
} else if (!firstName.equals(other.firstName))
return false;
if (lastName == null) {
if (other.lastName != null)
return false;
} else if (!lastName.equals(other.lastName))
return false;
return true;
}
}
ここで答えを導きます。文字列を使用することは悪い考えではありませんが(@CPerkins はその理由を完全に説明しました)、整数キーを使用してハッシュマップに値を格納する方が優れています。これは、一般的に(目立たないが)高速であり、可能性が低い (実際には可能性がない) ためです。衝突の。
それぞれのケースで 216553 個のキーを使用したこの衝突のグラフを参照してください (この投稿から盗まれ、議論のために再フォーマットされています)。
Hash Lowercase Random UUID Numbers ============= ============= =========== ============== Murmur 145 ns 259 ns 92 ns 6 collis 5 collis 0 collis FNV-1a 152 ns 504 ns 86 ns 4 collis 4 collis 0 collis FNV-1 184 ns 730 ns 92 ns 1 collis 5 collis 0 collis* DBJ2a 158 ns 443 ns 91 ns 5 collis 6 collis 0 collis*** DJB2 156 ns 437 ns 93 ns 7 collis 6 collis 0 collis*** SDBM 148 ns 484 ns 90 ns 4 collis 6 collis 0 collis** CRC32 250 ns 946 ns 130 ns 2 collis 0 collis 0 collis Avg Time per key 0.8ps 2.5ps 0.44ps Collisions (%) 0.002% 0.002% 0%
もちろん、整数の数は 2^32 に制限されており、文字列の数に制限はありません (また、 に格納できるキーの量に理論的な制限はありませんHashMap)。longa (または a でさえ)を使用するfloatと、衝突は避けられないため、文字列よりも「優れた」ものはありません。put()ただし、ハッシュの衝突があっても、get()常に正しいキーと値のペアを配置/取得します (以下の編集を参照)。
結局、それは本当に問題ではないので、より便利なものを使用してください。しかし、利便性に違いがなく、2^32 を超えるエントリを持つつもりがない場合はints、キーとして使用することをお勧めします。
編集
上記は間違いなく当てはまりますが、パフォーマンス上の理由から、元のキーの代わりに "StringKey".hashCode() を使用してキーを生成しないでStringください。2 つの異なる文字列が同じ hashCode を持つ可能性があり、メソッドが上書きされる可能性がありますput()。Java の の実装はHashMap、同じハッシュコードを持つ文字列 (実際にはあらゆる種類のキー) を自動的に処理できるほどスマートなので、Java にこれらを処理させるのが賢明です。
これは問題ではなく、ハッシュテーブルがどのように機能するかだけです。整数よりもはるかに多くの異なる文字列があるため、すべての異なる文字列に対して異なるハッシュコードを持つことはおそらく不可能です。
他の人が書いているように、ハッシュ衝突は equals() メソッドを介して解決されます。これが引き起こす可能性のある唯一の問題は、ハッシュテーブルの縮退であり、パフォーマンスの低下につながります。そのため、Java の HashMap には、バケットと挿入された要素の比率である負荷係数があり、これを超えると、バケット数の 2 倍でテーブルが再ハッシュされます。
これは通常、非常にうまく機能しますが、ハッシュ関数が適切である場合、つまり、特定の入力セットに対して統計的に予想される衝突回数を超えない場合に限られます。String.hashCode()この点では良いですが、常にそうであるとは限りませんでした。伝えられるところでは、Java 1.2より前では、n 番目の文字ごとにのみ含まれていました。これは高速でしたが、n 番目の文字を共有するすべての String に対して予測可能な衝突が発生しました。このような定期的な入力を行うほど不運だった場合や、誰かがアプリに対して DOS 攻撃を行いたい場合は、非常に悪いことです。
HashMap.putこのメソッドは、 を見ただけではキーが同じかどうかを判断できないのではないかと強く思いString.hashCodeます。
ハッシュの衝突が発生する可能性は間違いなくあるため、2 つの s が同じ値を返す場合は、 s が本当に等しいString.equalsことを確認するためにメソッドも呼び出されることが予想されます。 .StringStringhashCode
したがって、新しいキーは、によって返される値が等しい場合にのみ、既に存在するStringキーと同じであると判断され、メソッドは を返します。StringHashMaphashCodeequalstrue
Stringまた、Objectクラス自体には既にhashCodeおよびequalsメソッドがあるため、この考えは 以外のクラスにも当てはまります。
編集
Stringしたがって、質問に答えるには、いいえ、 a のキーに aを使用することは悪い考えではありませんHashMap。
あなたはハッシュの衝突について話している。ハッシュの衝突は、hashCode されているタイプに関係なく問題です。hashCode を使用するすべてのクラス (HashMap など) は、ハッシュの衝突を適切に処理します。たとえば、HashMap はバケットごとに複数のオブジェクトを格納できます。
自分で hashCode を呼び出す場合を除き、心配する必要はありません。ハッシュの衝突はまれですが、何も壊れません。