使用浮点数作为哈希表的键是否安全？

Question

我需要在我正在开发的工具中存储一些float,int对，其中int值存储了模型中float值出现的次数。我想知道这样做是否安全。

当使用浮点数进行直接比较（或作为哈希内容）时，有限精度可能是一个问题，因此我认为应该避免类似的方法，我是对的吗？

实际上，问题在于我没有与这些浮点数配对的其他信息，所以我不能使用任何其他东西作为哈希表的键，但同时，由于键会很多，拥有良好的性能也很重要。

也许最好的解决方案是使用二叉搜索树（或更高级的数据结构），以获得至少O(logn)的平均情况，即使常数因子更好也可以。

你有什么建议吗？只是让你知道我正在使用OCaml进行开发，但我认为这些考虑可以被认为是语言无关的。

- Jack

Answer 1

浮点数的常见问题在于计算是近似的。如果你用两种不同的方式计算相同的值，结果可能会略有不同。 （在某些情况下，通过以相同的方式两次计算相同的值，也可以得到轻微的差异。）

因此，如果你在浮点数上进行任何计算，你将得到近似值，并且不应该依赖相等性。如果你的源代码使用了各种方式计算浮点数，那么传递给你的数据将是近似的。如果你得到了确切的浮点数值，并且可以保证任何应该相同的数字具有完全相同的位表示，则相等性与正常情况下一样工作，并且可以使用哈希表。

- David Thornley

---

在某些情况下，通过以相同的方式计算相同的值两次可能会得到轻微的差异。这些情况是什么？ - Max

@Alec：如果编译器在一个操作的实例中使用寄存器，在另一个实例中使用内存，由于精度差异，您可能会得到不同的结果。x86 FP具有80位寄存器，但在存储时使用32位和64位，在四舍五入之前。因此，cos（23）== cos（23）可能返回false（这实际上发生在我身上）。 - Joseph Garvin

一个简单的解决方法是在比较之前将结果存储在变量中。 - Yay295

Answer 2

我认为这里有几个问题

使用浮点数作为哈希表键是否安全？

是的。我现在想不出哪种语言不符合哈希表键所需的要求（通常是稳定的哈希代码和相等语义）。

拥有大量键的哈希表可以吗？

取决于有多少。如果键的数量太多，导致表扩展超过允许的内存大小，那么肯定不行，因为它会导致内存不足的情况。没有更多上下文的情况下，很难回答这个问题的一部分。可能只有你自己能回答。

与其他类型（如int）相比，float的精度是否使其变得更糟糕？

这取决于具体实现，但我认为在OCaml中，float具有双精度（8字节）。因此，问精度是否使其无效作为键等同于问C#中的long类型是否不适用作哈希表键。它们都有相同数量的可能值（它们都是8字节）。我肯定会说long是有效的键类型（经常使用它，没有任何问题）。

我认为真正的问题是您是否不负责任地创建float实例以用作键。

如果哈希表内存不足，二叉树是否更好？

可能会更好，但差别不大。二叉树和哈希表都有开销。对于哈希表，通常是未使用的桶和桶内部列表中的下一个指针。对于二叉树，树中的每个元素都有两个额外的开销（左右指针）。如果内存不足，我不确定转换为二叉树是否会显着改善情况。

- JaredPar

Answer 3

你是在说一个性能问题还是一个有效性问题？

对于有效性：如果你想要计算相同浮点数的出现次数，那就没有问题。如果你想要计算大致相同的浮点数的出现次数，你需要弄清楚对于你来说什么是“大致相同”。

- David M.

Answer 4

如果你确定要计算一个确切浮点数值的实例数量，那么你可能没问题。

正如David所说，使用哈希表作为浮点数键的内在问题是，哈希表使用相等性来识别键，而由于计算误差，浮点数的相等性是一个略微不可靠的概念。没有一般性保证sin(pi / 6) == 0.5，甚至没有保证(2.0 / 3) * (2.0 / 3) == (4.0 / 9)。 在这两种情况下，左边可能与右边有稍微或更大的不同。

因此，如果您要将一些以0.5输入的条目和一些以sin(pi / 6)计算的条目计算在一起，并且您希望它们被一起计算，则需要做更多的工作，而不仅仅是对浮点数值进行哈希处理。

你可能可以通过四舍五入再哈希来解决问题，但你永远无法完全避免这个问题。例如，如果你将值四舍五入到最近的0.001，那么你会将0.2020001和0.2020003识别为“相同的值，有计算误差”，但不会将距离同样接近的0.1014999和0.1015001识别为相同的值。我在这里使用了十进制的例子以方便输入，但当然，“float”通常意味着二进制表示。

对于二叉树来说，完全相同的问题也会出现。哈希表并不关心它们的键数据是什么，它们只关心是否有人能够提供一个函数h，该函数将键映射到整数，使得对于任何你想要认为“相等”的x和y，h(x) == h(y)。然后为了性能，你需要确保h不会引入更多的“碰撞”（h(x) == h(y)的实例，其中x != y）比随机机会。使用浮点数完全没有障碍。你必须确保在哈希中不包括任何不参与比较的内容，并且如果包括所有参与比较的信息，则有助于解决问题。

如果您可以解决实际计数的问题，那可能会引导您找到所需的数据结构。如果您希望匹配具有一定容差度的值，则最好将所有浮点数排序，然后寻找值的集群。

- Steve Jessop