12

次のようなメソッドを実装するための(一意性の点で)最速でより堅牢な方法は何でしょうか

public abstract String hash(String[] values);

配列には 100 から 1,000のvalues[]メンバーがあり、それぞれ数十文字で、メソッドはvalues[]毎回異なる配列で約 10,000 回/秒実行する必要があります。

バッファを使用して長い文字列を作成し、StringBuilder次にバッファの内容に対してハッシュ メソッドを呼び出す必要がありますvalues[]か?

明らかに、衝突を避けるために少なくとも 64 ビットのハッシュ (MD5 など) が必要ですが、同じ品質でより簡単かつ高速に実行できるものはありますか?

たとえば、どうですか

public String hash(String[] values)
{
    long result = 0;

    for (String v:values)
    {
        result += v.hashCode();
    }

    return String.valueOf(result);
}
4

5 に答える 5

11

単純な加算は直線性があるため絶対に使用しないでください。ただし、コードをわずかに変更して、非常に良好な分散を実現できます。

public String hash(String[] values) {
  long result = 17;
  for (String v:values) result = 37*result + v.hashCode();
  return String.valueOf(result);
}
于 2012-05-14T16:43:30.503 に答える
2

メソッドを組み合わせると、弱点が生じることに注意する必要があります。(Java ハッシュ関数と独自のもの)。カスケード暗号について少し調べてみましたが、これがその一例です。(この追加は、hashCode() の内部に干渉する可能性があります)。

hashCode() の内部は次のようになります。

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }

そのため、数値を加算すると、配列内のすべての文字列の最後の文字が加算され、ランダム性は低下しません (これは、ハッシュ関数にとっては十分に悪いことです)。

真の疑似乱数が必要な場合は、FNVハッシュ アルゴリズムを調べてください。これは、特に HashMaps で使用するために設計された最速のハッシュ アルゴリズムです。

こんなふうになります:

    long hash = 0xCBF29CE484222325L;
    for(String s : strings)
    {
        hash ^= s.hashCode();
        hash *= 0x100000001B3L;
    }

^ 入力としてバイトの代わりに int を取るため、これは FNV の実際の実装ではありませんが、同様に機能すると思います。

于 2012-05-14T16:54:03.457 に答える
1

まず、ハッシュコードは通常数値intです。さらに、あなたのバージョンのハッシュ関数はintを作成し、IMHOが意味を持たない文字列表現を作成します。

次のようにハッシュメソッドを改善します。

public int hash(String[] values) {
    long result = 0;
   for (String v:values) {
        result = result * 31 + v.hashCode();
    }
    return result;
}

hashCode()クラスでの実装を見てみましょうjava.lang.String

于 2012-05-14T16:46:26.167 に答える