1

私は次のクラスを持っています

public class DateRange
{
    private DateTime startDate;
    private DateTime endDate;
    public override bool Equals(object obj)
    {
        DateRange other = (DateRange)obj;
        if (startDate != other.startDate)
            return false;
        if (endDate != other.endDate)
            return false;
        return true;
    }
    ...
}

次のような DateRange をキーとする辞書にいくつかの値を格納する必要があります。

Dictionary<DateRange, double> tddList;

クラスのGetHashCode()メソッドをオーバーライドするにはどうすればよいですか?DateRange

4

5 に答える 5

6

ハッシュを組み合わせるために、Effective Java の次のアプローチを使用します。

unchecked
{
    int hash = 17;
    hash = hash * 31 + field1.GetHashCode();
    hash = hash * 31 + field2.GetHashCode();
    ...
    return hash;
}

この状況でうまく機能しない理由はありません。

于 2010-08-19T20:37:53.677 に答える
5

それは、使用されると予想される値によって異なります。

同じ日の異なる時間ではなく、異なる日の値を持つことが最も多く、現在から 1 世紀以内である場合は、次のように使用します。

unchecked
{
    int hash = startDate.Year + endDate.Year - 4007;
    hash *= 367 + startDate.DayOfYear;
    return hash * 367 + endDate.DayOfYear;
}

これにより、シフトで失われるビット数を減らしながら、ビットが期待値とともに適切に分散されます。素数への依存が衝突で驚くほど悪い場合があることに注意してください（特に、バケット間で分散するためのさらに小さなハッシュを生成するときに、衝突を回避しようとして同じ素数のモジュロを使用するものにハッシュが供給される場合） )私は、より明白な選択肢よりも上の素数を選択しました。それらはちょうど上にあり、ビット分布にとってまだかなり「タイト」であるためです。このように非常に「タイト」であるため、同じプライムを2回使用することについてあまり心配していませんが、367個のバケットを持つハッシュベースのコレクションがある場合は問題があります. これは、過去または未来の日付をうまく処理します (ただし、それほどではありません)。

私が期待していた場合（または他の関係者による一般的な使用のために書いていて、そうでなければ想定できない場合）、私は次のようにします：

int startHash = startDate.GetHashCode();
return (((startHash >> 24) & 0x000000FF) | ((startHash >> 8) & 0x0000FF00) | ((startHash << 8) & 0x00FF0000) | (unchecked((int)((startHash << 24) & 0xFF000000)))) ^ endDate.GetHashCode();

最初の方法は、DateTime の汎用 GetHashCode が必要なほど良くないという前提で動作しますが、これは、それが良いかどうかに依存しますが、1 つの値のビットが混在しています。

2 つの値が同じである、または互いの距離が共通している (たとえば、1 日または 1 時間の範囲が多数ある) など、より明白なトリッキーなケースに対処するのに適しています。最初の例が最もよく機能する場合はそれほど良くありませんが、同じ日を異なる時間で使用する範囲がたくさんある場合、最初の例は完全に最悪です。

編集：Dourの懸念に対してより詳細な回答を与えるには：

Dour は、このページの回答の一部がデータを失っていることを正しく指摘しています。実際、それらはすべてデータを失います。

質問で定義されたクラスには、8.96077483×10 37の異なる有効な状態 (または、各日付の DateTimeKind を気にしない場合は9.95641648×10 36 ) があり、GetHashCode の出力には 4294967296 の可能な状態があります (そのうちの 1 つ - ゼロ -は null 値のハッシュコードとしても使用され、実際のコードで一般的に比較される可能性があります)。何をするにしても、情報を 2.31815886 × 10 27のスケールで縮小します。それは私たちが失った多くの情報です！

あるものは他のものよりも多くを失う可能性があるというのは、おそらく本当です。確かに、いくつかの解決策が他の解決策よりも多くを失う可能性があることを証明することは、有効ではあるが本当に貧弱な回答を書くことによって簡単に証明できます。

（最悪の有効な解決策はreturn 0;、等しいオブジェクトでエラーや不一致が発生しないため有効ですが、すべての値で衝突するため、可能な限り貧弱です。ハッシュベースのコレクションのパフォーマンスは O(n) になり、O と同じくらい遅くなります。関連する定数は、順序付けられていないリストの検索などの O(n) 操作よりも高いため、(n) が進みます)。

どれだけ失われたかを測定することは困難です。XOR が残っている情報量を半分にすることを考えると、XOR がビットを交換するよりも失う前にいくつかのビットをどれだけシフトするか。素朴な人でさえ、x ^ yswap-and-xor よりも多くを失うことはありません。共通の値でより衝突するだけです。swap-and-xor は、plain-xor が衝突しない値で衝突します。

可能な限り多くの情報を失うことはないが、4294967296 または 4294967296 に近い可能な値をそれらの値の間で適切に分散して返すソリューションの選択肢を得ると、問題はもはやどれだけの情報が失われるかではありません (答えは元の情報の4.31376821×10 -28しか残っていないが、どの情報が失われているか。

これが、上記の最初の提案が時間要素を無視する理由です。1 日に 864000000000 の「ティック」 (100 ナノ秒単位の DateTime の分解能) があり、シナリオを考えているため、意図的にそれらのティックの 2 つのチャンク (2 つの間に7.46496×10 23の可能な値) を破棄します。とにかくその情報が使用されていない場所。この場合、どの情報が失われるかを選択するような方法でメカニズムを意図的に構築しました。これにより、特定の状況のハッシュが改善されますが、開始日と終了日がまったく異なる値を持つ場合、まったく価値がなくなります。同じ日ですが、時間は異なります。

同様に、x ^ y は他のどの選択肢よりも多くの情報を失うことはありませんが、失う情報は他​​の選択肢よりも重要である可能性が高くなります。

どの情報が重要である可能性が高いかを予測する方法がない場合 (特に、クラスが公開され、そのハッシュ コードが外部コードによって使用される場合)、安全に行うことができる仮定がより制限されます。

全体として、prime-mult または prime-mod メソッドはシフトベースの方法よりも情報を失う点で優れています。目標を念頭に置いて（素数でさえ、それ自体が互いに素である数はありません）、その場合、それらははるかに悪いものになります。一方、シフトベースのメソッドは、シフトベースのさらなるハッシュにフィードされると、実際には機能しなくなります。任意のデータと任意の使用のための完全なハッシュはありません (クラスに有効な値がほとんどなく、それらすべてに一致する場合を除きます。この場合、生成するハッシュよりも厳密にエンコーディングになります)。

要するに、何をしても情報は失われます。失う情報が重要なのです。

于 2010-08-19T22:14:25.463 に答える
4

さて、良いハッシュ関数が持つべき特性を考えてみてください。それはする必要があります：

  • Equalsに同意する-つまり、2つのオブジェクトに対してEqualsが真である場合、2つのハッシュコードも同じである必要があります。
  • クラッシュすることはありません

そしてそれはすべきです：

  • 非常に速くなる
  • 同様の入力に対して異なる結果を与える

私がすることは、非常に単純なアルゴリズムを考え出すことです。たとえば、最初のハッシュコードから16ビット、2番目のハッシュコードから16ビットを取得し、それらを組み合わせます。代表的なサンプルのテストケースを作成してください。実際に使用される可能性が高い日付範囲、およびこのアルゴリズムが適切な分布を提供するかどうかを確認します。

一般的な選択は、2つのハッシュを一緒に排他的論理和することです。誰かがXからXまでの長さゼロの範囲を表現したいと思う可能性があるため、これは必ずしもこのタイプにとって良い考えではありません。2つの等しいDateTimeのハッシュをxorすると、常にゼロになります。多くのハッシュ衝突のレシピ。

于 2010-08-19T20:41:47.980 に答える
1

範囲の一方の端をシフトする必要があります。そうしないと、2 つの等しい日付がゼロにハッシュされます。これは、私が想像する非常に一般的なシナリオです。

return startDate.GetHashCode() ^ (endDate.GetHashCode() << 4);
于 2010-08-19T20:38:01.587 に答える
0 
return startDate.GetHashCode() ^ endDate.GetHashCode();

良いスタートかもしれません。startDate と endDate の間の距離が等しいが日付が異なる場合に、適切な分布が得られることを確認する必要があります。

于 2010-08-19T20:35:03.897 に答える