8

std::hash（例如，对于doubles 或s）的浮点特化在几乎相等float方面是否可靠？也就是说，如果两个值（例如and ）应该比较相等，但不会用运算符这样做，会如何表现？(1./std::sqrt(5.)/std::sqrt(5.)).2==std::hash

那么，我可以依靠 adouble作为std::unordered_map键来按预期工作吗？

我见过“散列浮点值”，但它询问了提升；我在问 C++11 的保证。

4

4 回答 4

11

std::hash对于可以实例化的所有类型都有相同的保证：如果两个对象相等，则它们的哈希码将相等。否则，他们不会的可能性很大。因此，您可以依赖 adouble作为 an 中的键 来按预期工作：如果两个双精度值不unordered_map相等（由==因为 unordered_map还检查是否相等）。

显然，如果您的值是不精确计算的结果，那么它们不适合unordered_map （也可能不适合任何地图）。

于 2013-02-18T19:42:10.477 回答
8

这个问题有多个问题：

  • 您的两个表达式不比较相等的原因不是有两个 0.2 的二进制表达式，而是没有0.2, 或sqrt(5)!的精确（有限）二进制表示。所以事实上，虽然(1./std::sqrt(5.)/std::sqrt(5.))和.2应该在代数上相同，但它们在计算机精度算术中可能并不相同。（它们甚至不是有限精度的纸笔算术。假设您正在使用小数点后的 10 位数字。sqrt(5)用 10 位数字写出并计算您的第一个表达式。它不会是.2。）

  • 当然，您有一个合理的概念，即两个数字接近。事实上，您至少有两个：一个绝对 ( |a-b| < eps) ，一个相对。但这并不能转化为合理的哈希值。如果您希望eps彼此内的所有数字都具有相同的哈希值，那么1, 1+eps, 1+2*eps, ...所有数字都将具有相同的哈希值，因此所有数字都将具有相同的哈希值。这是一个有效但无用的哈希函数。但它是唯一满足您将附近值映射到相同哈希的要求的方法！

于 2013-02-18T19:43:19.993 回答
3

在 an 的默认散列后面unordered_map有一个std::hash结构，它提供operator()计算给定值的散列。

此模板的一组默认特化可用，包括std::hash<float>和std::hash<double>。

在我的机器（LLVM+clang）上，这些被定义为

template <>
struct hash<float> : public __scalar_hash<float>
{
    size_t operator()(float __v) const _NOEXCEPT
    {
        // -0.0 and 0.0 should return same hash
       if (__v == 0)
           return 0;
        return __scalar_hash<float>::operator()(__v);
    }
};

其中__scalar_hash定义为：

template <class _Tp>
struct __scalar_hash<_Tp, 0> : public unary_function<_Tp, size_t>
{
    size_t operator()(_Tp __v) const _NOEXCEPT
    {
        union
        {
            _Tp    __t;
            size_t __a;
        } __u;
        __u.__a = 0;
        __u.__t = __v;
        return __u.__a;
    }
};

基本上，哈希是通过将联合的值设置为源值来构建的，然后只获得一个大小为size_t.

所以你得到一些填充或者你的值被截断，但这并不重要，因为你可以看到数字的原始位用于计算哈希，这意味着它与==运算符完全一样。具有相同哈希值的两个浮点数（不包括截断给出的冲突）必须是相同的值。

于 2014-12-12T04:52:32.947 回答
2

没有“几乎平等”的严格概念。所以原则上不能保证行为。如果您想定义自己的“几乎相等”概念并构造一个哈希函数，使两个“几乎相等”的浮点数具有相同的哈希值，您可以。但是，只有您对“几乎相等”浮点数的特定概念才适用。

于 2013-02-18T19:29:39.593 回答