C#等しい契約に違反するクラスのハッシュコードを選択する方法は?
-
08-07-2019 - |
質問
特定の理由により、公式の Equals
契約に従わないクラスが複数あります。上書きされた GetHashCode()
では、これらのクラスは単に0を返すため、ハッシュマップで使用できます。
これらのクラスの一部は同じインターフェースを実装しており、このインターフェースをキーとして使用するハッシュマップがあります。したがって、すべてのクラスは少なくとも GetHashCode()
で異なる(ただし一定の)値を返す必要があると考えました。
問題は、この値を選択する方法です。最初のクラスに1、次のクラス2などを返すようにするだけですか?または、次のようなものを試してください
class SomeClass : SomeInterface {
public overwrite int GetHashCode() {
return "SomeClass".GetHashCode();
}
}
では、ハッシュはより均等に分散されますか? (返された値を自分でキャッシュする必要がありますか、Microsoftのコンパイラはこれを最適化できますか?)
更新: Equalsは契約に違反しているため、各オブジェクトに個別のハッシュコードを返すことはできません。具体的には、この問題。
解決
ベクタークラスを作成するときに、この問題に遭遇しました。ベクトルの等価性を比較したかったのですが、浮動小数点演算では丸め誤差が発生するため、近似的な等価性が必要でした。簡単に言えば、実装が対称的、再帰的、推移的でない限り、等しいをオーバーライドすることは悪い考えです。
他のクラスは、equalsがそれらのプロパティを持っていると想定しているため、それらのクラスを使用するクラスも同様であるため、奇妙なケースに陥ることがあります。たとえば、リストは一意性を強制するかもしれませんが、いくつかの要素Bと等しいと評価される2つの要素になります。
ハッシュテーブルは、平等を破った場合の予測不可能な動作の完璧な例です。例:
//Assume a == b, b == c, but a != c
var T = new Dictionary<YourType, int>()
T[a] = 0
T[c] = 1
return T[b] //0 or 1? who knows!
別の例はセットです:
//Assume a == b, b == c, but a != c
var T = new HashSet<YourType>()
T.Add(a)
T.Add(c)
if (T.contains(b)) then T.remove(b)
//surely T can't contain b anymore! I sure hope no one breaks the properties of equality!
if (T.contains(b)) then throw new Exception()
ApproxEqualsなどの名前の別の方法を使用することをお勧めします。 ==演算子をオーバーライドすることも検討してください。これは仮想ではないため、Equalsのような他のクラスで誤って使用されることはないためです。
ハッシュテーブルに参照等価を実際に使用できない場合、可能な場合のパフォーマンスを台無しにしないでください。 IApproxEqualsインターフェイスを追加し、クラスに実装し、おおよそ等しいキーを探して関連する値を返すキーを列挙する拡張メソッドGetApproxをDictionaryに追加します。また、特に3次元ベクトルまたは必要なもののためにカスタム辞書を作成することもできます。
他のヒント
「等しい契約に違反する」場合、キーとして使用する必要があるかどうかはわかりません。
それをキーとして使用しているため、ハッシュを正しく取得する必要があります... Equals
ロジックが何であるかは非常に不明ですが、等しいと見なされる2つの値 には同じハッシュコードが必要です。同じハッシュコードを持つ2つの値が等しい必要はありません。
定数文字列を使用しても実際にはあまり役に立ちません-値は型に均等に分割されますが、それはそれについてです...
GetHashCode()
をオーバーライドして定数値を返すための推論がどうなるか興味があります。 「契約」に違反するだけでなく、ハッシュの概念に違反する理由 GetHashCode()
関数をまったくオーバーライドせず、 Object
からデフォルトの実装をそのままにしますか?
編集
実行したことが、参照ではなくコンテンツに基づいてオブジェクトを一致させることができる場合、異なるクラスに異なる定数を使用することで提案することは機能しますが、非常に非効率的です。やりたいことは、クラスのコンテンツを取得し、速度と均等な分散のバランスをとる値を生成できるハッシュアルゴリズムを考案することです(ハッシュ101)。
私はあなたが何を探しているのかわからないと思います...「良い」ではありません;このパラダイムの定数を選択するためのスキーム。一方が他方より優れているわけではありません。実際のハッシュを作成するようにオブジェクトを改善してください。
ハッシュの衝突が発生すると、HashTable / DictionaryはEqualsを呼び出して、探しているキーを見つけます。一定のハッシュコードを使用すると、そもそもハッシュを使用する速度の利点がなくなります-線形検索になります。
Equalsメソッドは、契約に従って実装されていないと言っています。これはどういう意味ですか?違反の種類に応じて、HashTableまたはDictionaryは単に遅くなる(線形検索)か、まったく機能しません。