4

我想我的问题也可以这样问:一个十进制值可以在双精度变量中以多种方式表示。

我有一个哈希表实现,双精度浮点数将是键,我正在使用一种哈希算法来构建哈希,同时迭代双精度的每个字节(至少在我的系统上是 64 位的,所以8 个字节来散列)。我的问题是,如果单个值(例如“1.2345”)可以以双倍多于 1 的方式以二进制形式表示,那么它可能会导致单个值有多个可能的哈希值。

我不确定在哪里研究这种可能性。如果我不得不猜测,我会猜测这是不可能的,或者如果有可能对其进行规范化以确保值在给定系统上始终具有相同的表示形式。我主要是在寻找对此的确认。

如果一个值可以有多种表示形式,那么我需要在散列它之前对该值进行规范化,我希望能就如何做到这一点提出建议。

编辑:

我发现了更多关于浮点数的信息。它们被存储为一个 mantessa 和一个指数。所以我的问题是单个浮点数是否可以由多个 mantessa 和指数的组合表示。

4

3 回答 3

2

浮点数的按字节散列会有两个问题。

第一个令人惊讶地经常出现,即 0 有两种表示形式,一种表示每个可能的符号位。(0 和负 0。)这些不仅在数学上相等,而且还需要在 C/C++ 中测试相等。负 0 在计算中经常出人意料地出现,尽管并非所有人都printf将其打印为 -0。(在 Intel 硬件上,至少 0.0/-1.0 是 -0.0。)

所以你需要确保两个零散列到同一个东西。

另一个问题是 NaN。有相当多的 NaN,但它们(在技术上)甚至无法与它们自己进行比较,因此它们制作了糟糕的哈希键。可能最简单的解决方案是忽略它们,因为没有人应该期望 NaN 可用作哈希键。但问题是,如果有人试图将一个放入您的哈希表,然后再次放入,如果您使用浮点==检查密钥是否存在,它最终可能会被输入两次。因此,一个简单的错误(或蓄意攻击)可能会通过扩展哈希表来迅速耗尽内存。(如果用 memcmp 比较字节,就不会有这个问题。)

于 2013-09-26T00:51:31.320 回答
2

IEEE 754 二进制浮点对除零外的每个可表示值都有一个编码,其中有一个 +0 和一个 –0。

目前大多数 C 实现都使用 IEEE 754 二进制格式。然而,并不是所有的浮点运算都正确实现(例如,从字符串中的十进制转换为二进制浮点可能会产生稍微不准确的结果),并且运算链的结果可能与您使用精确算术得到的值不同,并且不同的链可能会产生不同的值,即使它们在数学上是相同的。(后者包括使用不提供严格浮点计算的不同编译器编译相同源代码的结果。)

IEEE 754 还指定了十进制浮点格式,并且确实有多种值表示形式。

于 2013-09-26T00:12:45.510 回答
0

有可能的。双精度值比浮点数更精确,但在精度方面仍然不是 100% 密封的。使用定点或整数对表示(即:值的每个部分的整数)。

于 2013-09-25T23:42:08.440 回答