13

鉴于 .Net 能够通过 IntPtr 检测位数(尽管通过反射器查看大量它被标记为不安全 - 耻辱)我一直认为 GetHashCode 返回一个 int 可能是短视的。

我知道最终使用一个好的散列算法,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 位进行异或运算。我真的无法想象一个更好的通用型。(截断为 Int32 是不好的——你怎么能正确地散列低 32 位全为零的 64 位值?)

如果 IntPtr 被用作散列返回值,那么代码将必须有条件分支(是 32 位吗?是 64 位吗?等等),这会减慢散列函数的速度,从而破坏整点。

我想说,如果你有一个实际上有 20 亿个桶的哈希表,那么你可能正处于编写整个自定义系统的阶段。(可能数据库会是更好的选择?)在那个大小下,确保桶被均匀填充将是一个更紧迫的问题。(换句话说,一个更好的散列函数可能会比大量的桶支付更多的红利)。

如果您确实想要内存中的多 GB 映射,那么没有什么可以阻止您实现一个具有等效 64 位哈希函数的基类。但是,您必须编写自己的 Dictionary 等价物。

于 2010-01-14T14:31:55.333 回答
4

是否意识到返回的哈希码GetHashCode用于哈希表中的寻址?使用更大的数据类型将是徒劳的,因为无论如何所有哈希表都较小。额外的信息只会被浪费,因为它不能被充分使用。

常见的哈希表具有几千到几百万个条目。一个 32 位整数足以覆盖这个索引范围。

于 2010-01-14T14:36:43.513 回答