散列浮点值

Question

最近,我很好奇浮点数的哈希算法是如何工作的,所以我查看了源代码boost::hash_value.事实证明这很复杂.实际实现循环遍历基数中的每个数字并累积哈希值.与整数散列函数相比,它涉及更多.

我的问题是:为什么浮点哈希算法会更复杂？为什么不将浮点值的二进制表示形式哈希,就好像它是一个整数？

喜欢:

std::size_t hash_value(float f)
{
  return hash_value(*(reinterpret_cast<int*>(&f)));
}

我意识到float不能保证与int所有系统上的大小相同,但是可以使用一些模板元程序来处理这种事情,以推断出与其相同大小的整数类型float.那么引入一个专门针对浮点类型操作的完全不同的哈希函数有什么好处呢？

Answer 1

从本质上讲,它归结为两件事:

可移植性:当你获取float的二进制表示时,那么在某个平台上,具有相同值的float可能有多个二进制表示.我不知道是否存在这样一个存在问题的平台,但由于解密数字的复杂性,我不确定这是否真的会发生.
第二个问题是你提出的,可能是sizeof(float)不相等的sizeof(int).

我没有发现任何人提到boost hash确实避免了更少的冲突.虽然我认为将尾数与指数分开可能有所帮助,但上述链接并未表明这是驱动设计决策.

Answer 2

不使用位模式的一个原因是必须将一些不同的位模式视为等于并因此具有相同的散列码,即

即使`NaN!= NaN`,哈希函数也被视为黑盒子; 也就是说,哈希值的使用者(例如关联容器)不会为不可比性做好准备.因此,`hash(NaN)== hash(NaN)`必须为true,否则数据类型不应该是hashable. (3认同)
为什么NAN必须被认为是平等的？`NAN!= NAN`. (2认同)

Answer 3

为什么要对浮点值进行哈希处理？出于同样的原因，比较浮点值是否相等存在许多陷阱，对它们进行散列可能会产生类似的（负面）后果。

然而，考虑到您确实想这样做，我怀疑 boost 算法很复杂，因为当您考虑非规范化数字时，不同的位模式可以表示相同的数字（并且可能应该具有相同的哈希值）。在 IEEE 754 中也有正向和负向0比较相等但具有不同位模式的正值和负值。

如果它不会出现在您的算法中，那么它可能不会出现在散列中，但您仍然需要注意发出 NaN 值信号。

另外，散列 +/- 无穷大和/或 NaN 的含义是什么？具体来说，NaN 可以有多种表示形式，它们都应该产生相同的哈希值吗？无穷大似乎只有两种表示形式，所以看起来效果还不错。