1

2 つの質問を 1 つにまとめて申し訳ありませんが、それらは関連しています。

HashCodesHashSetなど。私が理解しているように、それらは一意であり、変化してはならず、オブジェクトの構成を単一の数値として表す必要があります。

私の最初の質問は、2 つの Int16saとを含むオブジェクトについて、 n が大きな数であるようなものを返すことbは安全ですか?GetHashCodea * n + bMath.Pow(2, 16)

またGetHashCode、特に Int32 型を柔軟に返すように見えます。

32ビットは、たとえば、2つのInt16、単一のUnicode文字、または16のN、S、E、Wのコンパス方向を保存できますが、それほど多くはありません。小さないくつかのノードグラフのようなものでさえ、おそらく多すぎるでしょう. これは C# ハッシュ コレクションの制限を表していますか?

4

2 に答える 2

7

私が理解しているように、それらは一意でなければなりません

いいえ。2 32を超える可能な値を持つ可能性があるほとんどの型では、それらを一意にすることはできません。理想的には、2 つのオブジェクトが同じハッシュ コードを持っている場合、それらが等しい可能性は低いですが、それらが等しいと想定してはなりません。重要な点は、それらのハッシュ コードが異なる場合、それらは間違いなく等しくないはずだということです。

私の最初の質問は、2 つの Int16s a と b を含む私のオブジェクトに対して、私の GetHashCode が a * n + b のようなものを返すのは安全かということです。ここで、n は大きな数です。おそらく Math.Pow(2, 16) だと思います。 .

値が 2 つしかない場合Int16は、最も簡単に使用できます。

return (a << 16) | (ushort) b;

その後、値は一意になります。フーラ！

またGetHashCode、特に type を柔軟に返すように見えますInt32。

はい。Dictionaryやなどの型HashSetは、固定サイズを使用して値をバケットに入れることができるようにする必要があります。

32ビットは、たとえば、2つのInt16、単一のUnicode文字、または16のN、S、E、Wのコンパス方向を保存できますが、それほど多くはありません。小さないくつかのノードグラフのようなものでさえ、おそらく多すぎるでしょう. これは C# ハッシュ コレクションの制限を表していますか?

これが制限であるとすれば、C# の制限ではなく .NET の制限になりますが、ハッシュ コードが何を表すのかを誤解しているだけです。

Eric Lippert の優れた (明らかに)ブログ記事があり、詳細についてGetHashCodeはこちらをお読みください。

于 2012-04-14T18:14:05.133 に答える
1

GetHashCodeオブジェクトのすべてのインスタンスに対して一意ではありません (一意にすることもできません)。たとえばInt64、ハッシュ関数が完全に分散されていても、 ハッシュ Int64コードは、あなたが述べたように、Int32.

ただし、これはハッシュ コードを使用するコレクションの制限ではありません。同じ値にハッシュする要素にバケットを使用するだけです。そのため、ハッシュ テーブルへのルックアップが 1 回の操作であるとは限りません。正しいバケットを取得するのは 1 回の操作ですが、そのバケットには複数のアイテムが含まれる場合があります。

于 2012-04-14T18:14:51.577 に答える