2

ファイルからいくつかの単語とその意味を読み取り、それらを配列にマップする (ハッシュ テーブルを作成する) コードを書きました。多項式ハッシュ コードと圧縮方法を使用します。

私の目標は、衝突をできるだけ少なくすることですが、方法がわかりません。

public int hashcode(Entry my){ 
    Object key=my.getKey(); 
    int sum=0 ,z=33; 
    char[] chars = new char[key.toString().length()]; 
    chars=key.toString().toCharArray(); 
    for(int i=0; i < chars.length; i++){ 
         sum += (chars[i])*Math.pow(z,i);
    } 
    return sum;
}

これは私の圧縮方法です（サイズ100の配列の場合）：

public int compress(int hashcode){ 
    return hashcode%100; 
}

圧縮方法を変更する必要がありますか、それとも役立つ方法がありますか?

4

1 に答える 1

2

あなたが探しているように見えるのは完璧なハッシュ関数ですが、残念ながら、私の知る限り、そのようなハッシュは存在しません:)
もう1つ指摘すべきことは、ハッシュ関数のパフォーマンスは、必要な結果のタイプによっても異なるということです達成する; つまり、ハッシュ関数は電話番号の「保存」には優れたパフォーマンスを発揮しますが、連絡先の名前の保存には不十分な結果をもたらす可能性があるということです。

コードをざっと見てみると、ハッシュ関数が複雑すぎると思います。
最初に、現在のアルゴリズムの問​​題を指摘したいと思います: この行 'sum+=(chars[i])*Math.pow(z,i);' は、4 ～ 5 文字を超える単語の整数範囲をはるかに超える値を返します (単なる推測です)。オーバーフローするなどの理由で大丈夫だと言うかもしれませんが、sum+= 構文は実際には型キャストを隠しているため (sum=sum+ と書いてみてください)、そのような場合、合計はInteger.MAX_VALUE の値。これがおそらく、アルゴリズムが現在遅い理由です。

私があなただったら、辞書の目的で (これはあなたがやろうとしていることのようです)、 Entry#getKey() が String 型であると仮定すると、おそらく次のようになります。

public int hashcode(Entry my) {
    return my.getKey().hashCode();
}

それでも独自のハッシュ関数を作成したい場合は、[単語の長さ + 最初の X 文字の char コード + 最後の文字の char コード] のようなもっと単純なものを使用してみませんか? X を適応させて、結果が整数。ただのアイデア:)

于 2013-01-26T13:13:43.583 に答える