浮点数哈希化

Question

最近，我对浮点数的哈希算法很感兴趣，所以我查看了boost::hash_value的源代码。结果发现这是相当复杂的。实际实现会循环每个进制下的数字并累加哈希值。与整数哈希函数相比，它要复杂得多。

我的问题是：为什么浮点数哈希算法应该更复杂呢？为什么不只是像哈希整数一样哈希浮点数的二进制表示？

例如：

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

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

- Channel72

---

按照您的写法，您违反了严格别名规则（如果“int”与“float”的大小不同，则更糟），但我很想知道将其转换为给定长度的“char*”的答案。 - Mark B

可能是浮点数的哈希函数的重复问题。 - legends2k

Answer 1

请看https://svn.boost.org/trac/boost/ticket/4038。

本质上有两个问题：

1. 可移植性：当您获取浮点数的二进制表示时，可能在某些平台上出现相同值的浮点数具有多个二进制表示的情况。我不知道是否实际存在此类问题的平台，但是由于非规范化数字的复杂性，我不确定这是否可能发生。

2. 第二个问题是您提出的，即sizeof(float)可能不等于sizeof(int)。

我没有找到任何人提到boost哈希确实避免了更少的碰撞。虽然我认为将尾数与指数分开可能会有所帮助，但以上链接并未表明这是主要设计决策。

- H. Brandsmeier

Answer 2

不仅仅使用位模式的一个原因是，一些不同的位模式必须被视为相等，因此具有相同的哈希码，即：

• 正零和负零
• 可能非规格化数字（我认为这在IEEE 754中不会发生，但C允许其他浮点表示）。
• 可能是NAN（至少在IEEE 754中有很多。实际上，它要求将NAN模式视为与自身不相等，这可能意味着它们不能在哈希表中有意义地使用）

- Michael Borgwardt

---

为什么必须将NAN视为相等？NAN！= NAN。 - Steve Jessop

实际上，我撤回之前的说法。标准规定：“对于表达式h(k)的所有求值，如果k的值相同，则结果相同。”而不是（我原以为的）“所有满足k == l的h(k)和h(l)的求值结果相同”。因此，根据哈希要求，“==”比“具有相同值”不那么相关。两个不同的NAN是否“具有相同值”是一个我无法处理的标准组合练习 :-) - Steve Jessop

尽管NaN != NaN，但散列函数应该被视为黑盒子；也就是说，哈希值的使用者（如关联容器）不会考虑非可比性。因此，要么hash(NaN) == hash(NaN)必须为真，要么数据类型就不能被哈希化。 - rwong

Answer 3

你为什么希望哈希浮点数值？和比较浮点数值相等一样，哈希它们也有许多缺陷。但是如果你确实想要这样做，我认为 Boost 算法之所以复杂，是因为考虑到非规格化数时，不同的位模式可以表示相同的数字（应该具有相同的哈希值）。在 IEEE 754 中，还存在正零值和负零值，其比较相等但具有不同的位模式。

如果在哈希中不涉及此问题，可能在算法中也不会出现，但仍需要注意信号 NaN 值。另外，哈希正无穷/负无穷和/或 NaN 的含义是什么？特别地，NaN 可以有许多表示形式，它们都应该产生相同的哈希值吗？正无穷似乎只有两种表示形式，因此看起来应该可以正常工作。

- Mark B

---

你能详细说明一下为什么你认为对正负无穷大和NaN进行哈希是毫无意义的吗？我不明白这可能是一个问题。 - Luc Touraille

至少在IEEE 754中，由于非规格化（denormalization）处理，我认为不可能存在相同值的不同模式。 - Michael Borgwardt

@Michael Borgwardt 当然，IEEE 754 中可能会出现 +/- 0 和各种 NaN 值。但我不确定其他的值。 - Mark B

除非标准另有规定，我希望+/- inf的处理方式与该类型的任何其他值相同 - 理想情况下它们应该具有不同的哈希值。如果您的浮点类型中有两个+inf的表示方式，则它们必须具有相同的哈希值。 - Steve Jessop

很好的回答，除了毫无意义的“为什么要这样做？”。有用例存在。仅仅因为你想不到它们... - Timmmm

我有一个使用案例：我需要存储一堆3D向量，但其中许多向量是相等的。如果我能找到一个唯一值列表，然后只使用该列表中的索引，我将减少约75％的内存消耗。哈希表是将它们分组的最快方法。但我需要一个3D向量的哈希值...这些向量是3D三角网格中平滑法线的信息。 - galinette

Answer 4

我想这是为了让两台具有不兼容浮点格式的机器哈希到相同的值。

- TonyK

---

假设我只想在std :: unordered_set中使用浮点数，没有理由哈希值会在机器之间共享。 - galinette