std :: hash是否保证"相等"浮点数的哈希值相等？

Question

对于几乎相等的问题std::hash,浮点专业化(例如,对于doubles或floats)是否可靠？也就是说,如果两个值(例如和)应该比较相等但不会与运算符进行比较,那么将如何表现？(1./std::sqrt(5.)/std::sqrt(5.)).2==std::hash

那么,我可以依靠double一个std::unordered_map关键来按预期工作吗？

---

我已经看到了" 哈希值浮动值 ",但是询问了提升; 我问的是C++ 11的保证.

Answer 1

std::hash对于可以实例化的所有类型都有相同的保证:如果两个对象相等,则它们的哈希码将相等.否则,他们不会有很大的可能性.所以你可以依赖a double作为一个键 unordered_map来按预期工作:如果两个双精度不相等(由定义==),它们可能会有不同的散列(即使它们没有,它们也是不同的键,因为 unordered_map也检查相等).

显然,如果您的值是不精确计算的结果,则它们不适用于unordered_map (也可能不适用于任何地图).

Answer 2

这个问题存在多个问题:

• 你的两个表达式不比较相等的原因并不是有两个二进制表达式为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, ...所有数字都将具有相同的哈希值,因此,所有数字将具有相同的哈希值.这是一个有效但无用的哈希函数.但它是唯一一个满足您将附近值映射到相同哈希的要求!

Answer 3

在默认哈希值后面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。

因此，您会得到一些填充，或者您的值会被截断，但这并不重要，因为正如您所看到的，数字的原始位用于计算哈希值，这意味着它的工作方式与运算符完全相同==。两个浮点数必须具有相同的值，才能具有相同的哈希值（排除截断引起的冲突）。