Javaで自分のハッシュ関数を書き込もうとしています。私はこれがjavaが実装しているものと同じだが自分自身でそれをテストしたいと思っています。なぜ私は別の値を入力し、理由がわからないときに私は衝突を取得しています。javaハッシュ関数の衝突
public static int hashCodeForString(String s) {
int m = 1;
int myhash = 0;
for (int i = 0; i < s.length(); i++, m++){
myhash += s.charAt(i) * Math.pow(31,(s.length() - m));
}
return myhash;
}
は親切に覚えているだけでどのように（どの言語でも...）ハッシュテーブル実際作品：「バケット」それはの（通常は、プライム）数で構成されてい ハッシュ関数の目的は、入ってくるキー値をバケット番号に変換することです。 （ワーストケースのシナリオは、常に、入力キーの100％が単一のバケットに巻かれ、 "リンクされたリスト"を残しています） "典型的には"生成するハッシュ関数を考案しようとしていますモジュロバケットの数、「ほとんどの時間、ほとんどのバケツ」が「多かれ少なかれ均等」になるように、値の「広く分散された」分布。 は（しかし、覚えている：あなたは確認することはできません。）
は「衝突」は完全に予想される： 実際には、「彼らはすべての時間が起こります。」
私の謙虚な意見では、あなたはハッシュ関数を「考えすぎ」と感じています： Math.pow()を使用する説得力のある理由は全くありません。生成する値は絶対値モジュロをバケット数とすることで、ハッシュバケット番号に変換されます。 （あなたのデータ用）は、バケットサイズの結果の分布を観察することです。 （の目的にはまだ十分ですか？）
'Math.pow（...）'はdoubleを返します。これはコンパイルされますか？ –
コンパイルする、はい –
Java StringのhashCode実装では、 'Math.pow'を使用せず、int mathを使用し、intオーバーフローを計算の一部として使用できます。あなたの計算はそうではなく、それは大きな違いです。 –