0

Rectangle クラスがあります。長さ、幅、面積 (すべて整数) があります。同じ長さと幅を持つすべての長方形が同じ値にハッシュされるようにハッシュしたいと思います。これを行う方法は何ですか?

編集:私はそれが幅広い質問であることを理解しています。それが私がそれを行うための「a」方法を求めた理由です。最善の方法ではありません。

4

3 に答える 3

1

適切で単純なスキームは、次のように整数のペアのハッシュを計算することです。

hash = length * CONSTANT + width

CONSTANT経験的に、 が素数の場合、最良の結果 (つまり、数の衝突が最も少ない) が得られます。多くの人が1のような値を推奨しますが、最適な選択はとの値31の最も可能性の高い範囲によって異なります。それらが厳密に制限されていて、十分に小さい場合は、よりもうまくいく可能性があります。lengthwidth31

ただし、31実用的な目的にはおそらく十分です2。このレベルでのいくつかの衝突は、パフォーマンスに大きな違いをもたらす可能性は低く、完全なハッシュ関数でさえ、ハッシュ テーブル レベルでの衝突をなくすことはできません...ハッシュ値のモジュラスを使用する場所です。


1 - この数字がどこから来たのか、またはそれを裏付ける実証研究があるかどうかはわかりません...一般的なケースでは. (ASCII)文字列のハッシュに由来すると思われます。しかし31、素数は ... メルセンヌ素数 ( 2^7 - 1) です。これは、ハードウェアの倍数が遅い場合、シフトと減算を使用して計算できることを意味します。

2 - 何かを「破壊」しようとして意図的にハッシュ関数の衝突を作成することを心配する必要がある場合は除外しています。

于 2013-08-31T00:55:34.957 に答える
0

HashCodeBuilderクラスを持つ Apache Commons ライブラリを使用できます。aと aを持つRectangleクラスがあると仮定すると、次のメソッドを追加できます。widthheight

@Override
public int hashCode(){
  return new HashCodeBuilder().append(width).append(height).append(children).toHashCode();
}
于 2013-08-31T00:11:20.537 に答える