13

.Net には IntPtr を介してビット数を検出する機能があることを考えると (リフレクターを調べると、かなりの量が安全でないとマークされていますが、残念です)、int を返す GetHashCode は近視眼的である可能性があると考えていました。

最終的には、優れたハッシュ アルゴリズムを使用すれば、Int32 によって提供される数十億の順列が完全に適切であることはわかっていますが、それでも、可能なハッシュのセットが狭いほど、より線形な検索が必要になるため、ハッシュされたキーの検索が遅くなります。

同様に、これが面白いと思うのは私だけですか？

struct Int64{
  public override int GetHashCode()
  {
    return (((int) this) ^ ((int) (this >> 0x20)));
  }
}

一方、Int32 は単純に を返しますthis。

パフォーマンスの問題で IntPtr が問題外である場合、おそらく IEquatable などを実装する IHashCode の方がよいでしょうか?

私たちのプラットフォームがメモリ容量、ディスク サイズなどの面でますます大きくなるにつれて、32 ビット ハッシュで十分な時代は確実に長くなる可能性があります。

それとも、インターフェースを介してハッシュを抽象化するか、プラットフォームに応じてハッシュのサイズを調整することに伴うオーバーヘッドが、潜在的なパフォーマンス上の利点を上回っているという単純なケースですか?

4

2 に答える 2

12

Int64 ハッシュ関数は、すべてのビットが考慮されることを確認するためにあります。基本的には、上位 32 ビットと下位 32 ビットを XOR しています。より良い汎用のものを想像することはできません。(Int32 に切り捨てるのは良くありません。下位 32 ビットがすべてゼロの 64 ビット値を適切にハッシュするにはどうすればよいでしょうか?)

IntPtr をハッシュの戻り値として使用すると、コードに条件分岐 (32 ビットですか? 64 ビットですか? など) が必要になり、ハッシュ関数の速度が低下し、ポイント全体が無効になります。

実際に 20 億個のバケットを持つハッシュテーブルがある場合は、おそらくカスタム システム全体を作成する段階にあると言えます。(おそらく、データベースの方が適しているでしょうか?) そのサイズでは、バケットが均等に満たされるようにすることが、より差し迫った問題になります。(つまり、ハッシュ関数が優れているほど、バケットの数が多い場合よりも多くの配当が得られる可能性があります)。

メモリ内に数ギガバイトのマップが必要な場合は、同等の 64 ビット ハッシュ関数を持つ基本クラスを実装することを止めるものは何もありません。ただし、独自の辞書に相当するものを作成する必要があります。

于 2010-01-14T14:31:55.333 に答える
4

によって返されるハッシュ コードが、ハッシュ テーブルでのアドレス指定に使用されることを認識していますか? GetHashCodeとにかくすべてのハッシュテーブルが小さいため、より大きなデータ型を使用しても無駄です。追加情報は、適切に使用できないため、単に無駄になります。

一般的なハッシュ テーブルには、数千から数百万のエントリがあります。この範囲のインデックスをカバーするには、32 ビット整数で十分です。

于 2010-01-14T14:36:43.513 に答える