1

特定の種類のオブジェクト (たとえば、 type MyClass) の値をさまざまなMap<String, MyClass>マップに格納するアプリケーションがあります。

アプリケーションは、

  • 異なるマップから単一のコレクション (共用体) へのオブジェクト参照を取得します。
  • 単一のコレクションを並べ替える (順序を適用するため)
  • 連続するコレクション間の差を計算する (変更を検出するため)
  • 各コレクションのすべてのオブジェクトから単一のハッシュ値を生成します

(統合された) コレクション内のオブジェクトの順序は重要です。

並べ替えを行うには、 を使用してオブジェクト (マップ値) を配置し、 をaddAll()介しArrayListて並べ替えCollections.sort()ます。順序は で定義され、カプセル化された文字列フィールド (たとえば ) を比較することでインターフェイスMyClassを実装します。ComparatormyField

並べ替えが完了すると、すべてのオブジェクトから一意の署名が作成されます。この署名は、同じ値を持つオブジェクトに対して同じである必要がありますmyField。これは現在、文字列の連結 (toLowerCase()とを使用StringBuilder) によって行われ、結果の文字列をハッシュすることで、数千文字の長さにすることができます。

上記（コピー、ソート、比較、ハッシュ）を（一部またはすべて）実行するより効率的な方法はありますか？

4

3 に答える 3

3

一意の署名が必要な場合は、（少なくとも概念的には）次のことを行う必要があります。

  • 関連するデータを文字列またはバッファに連結します。
  • 強力なハッシュ関数を使用して、そのデータのハッシュを取得します。

すべてのデータを実際にバッファにコピーしなくても、その場でハッシュを計算できる可能性があるため、「概念的に」と言います。これは、特定のアプリケーションでどれだけ便利かによって異なります。

Javaで標準的に使用されている32ビットハッシュコードは、一般的に弱すぎて一意のコードを提供できません。

少なくとも64ビットハッシュ関数を使用することをお勧めします（私の記事の1つに、役立つ可能性のある64ビットハッシュ関数の実装例があります）。一意性をより保証するには、MD5などのより強力なハッシュ関数の方が理想的ですが、結果のハッシュコードが広すぎてプリミティブに格納できないというわずかな不便があります。（これは、行う必要のあるトレードオフです。64の強力なハッシュは、通常、数百万のオブジェクト間のすべての意図と目的に対する一意性を保証するのに適しています。MD5は、より広いハッシュコードを犠牲にして、はるかに強力な保証を提供します。）

PS先日、同様の質問にこの回答をしましたが、これも役立つかもしれません。

于 2012-05-11T01:14:19.140 に答える
3

はい、もっと良い方法があります。ハッシュを単純にハッシュします。

List<String> strings;

int hash = 0;
for (String string : strings)
    hash += hash * 31 + string.hashCode();

これは事実上メモリを使用せず、非常に高速であり、StringBuilder アプローチと同等の強度のハッシュ コードを生成します。

于 2012-05-11T01:06:03.047 に答える
1

あなたが本当に欲しいのは、コレクションを独自の方法で記述し (内部の順序付けは重要ではない)、myField のみに依存する結合されたハッシュだけであると仮定すると、次のことをお勧めします。

long hash = 0
for map in maps:
    for key in keys:
        if key in map:
            hash = hash + 64bithash(map[key].myfield)

ここで、追加はすべて実質的にモジュール 2^64 です。これにより、一意になるのに十分な大きさ (64 ビット) であり、順序付けに依存せず (2+3 = 3+2)、並べ替えや追加の構造への格納を必要としない、コレクション全体のハッシュが得られます。 （だから速いでしょう）。

これは、順序が重要ではないことを前提としていることを警告します。有効なハッシュが myfieldと順序付けで使用される情報の両方に依存するように、順序付けで myfield 以外のものを使用している可能性があります。その場合、上記は同等に機能しません (ただし、has に順序付けに使用される情報を含めることで、そうすることができます)。

于 2012-05-11T01:42:55.150 に答える