浮动的哈希函数

Question

我目前正在用C++实现一个哈希表,我正在尝试为浮点数创建一个哈希函数...

我打算通过填充十进制数来将浮点数视为整数,但后来我意识到我可能会用大数字来达到溢出...

哈希浮点数是否有好方法？

你不必直接给我这个功能,但我想看/理解不同的概念......

笔记:

1. 我不需要它真的很快,如果可能的话,只是均匀分布.

2. 我已经读过浮点数不应该因为计算的速度而被散列,有人可以确认/解释这个并给我其他原因,为什么浮点数不应该被散列？我真的不明白为什么(除了速度)

Answer 1

它取决于应用程序,但大多数时间浮点数不应该被散列,因为散列用于快速查找精确匹配,大多数浮点数是计算产生浮点数的结果,浮点数只是正确答案的近似值.检查浮动相等性的通常方法是检查它是否在正确答案的某个增量(绝对值)内.这种类型的检查不适用于散列查找表.

编辑:

通常,由于舍入误差和浮点运算的固有限制,如果你期望浮点数a并且b应该相互相等,因为数学表示如此,你需要选择一些相对较小的delta > 0,然后你声明a并且b相等if abs(a-b) < delta,abs绝对值函数在哪里.有关更多详细信息,请参阅此文章.

这是一个演示问题的小例子:

float x = 1.0f;
x = x / 41;
x = x * 41;
if (x != 1.0f)
{
    std::cout << "ooops...\n";
}

根据您的平台,编译器和优化级别,这可能会打印ooops...到您的屏幕,这意味着数学等式x / y * y = x不一定在您的计算机上.

在某些情况下,浮点运算会产生精确的结果,例如,合理大小的整数和有2次幂分母的有理数.

Answer 2

如果您的哈希函数执行以下操作,您将在哈希查找中获得某种程度的模糊性

unsigned int Hash( float f )
{
    unsigned int ui;
    memcpy( &ui, &f, sizeof( float ) );
    return ui & 0xfffff000;
}

这样你就可以掩盖12个最低有效位,从而产生一定程度的不确定性......但这实际上取决于你的应用.

Answer 3

您当然可以将 a 表示float为int相同大小的类型来对其进行散列，但是这种简单的方法有一些您需要小心的陷阱......

简单地转换为二进制表示形式很容易出错，因为相等的值不一定具有相同的二进制表示形式。

一个明显的例子：例如，-0.0 不会匹配。*0.0

此外，简单地转换为int相同大小不会给出非常均匀的分布，这通常很重要（例如，实现使用存储桶的哈希/集合）。

建议的实施步骤：

• 过滤掉非有限情况 ( nan, inf) 和 ( 0.0，-0.0 是否需要显式执行此操作取决于所使用的方法)。
• 转换为int相同大小的an
  （即 - 例如使用并集将 the 表示float为 an int，而不是简单地转换为 int ）。
• 重新分配位（这里故意含糊其辞！），这基本上是速度与质量的权衡。但是，如果您在一个小范围内有许多值，您可能不希望它们也处于相似的范围内。

*：您可能也不想检查 (nan和-nan)。如何处理这些完全取决于您的用例（您可能想像nanCPython 一样忽略所有的符号）。

Python_Py_HashDouble是一个很好的参考，帮助您了解如何float在生产代码中对 ,进行散列（忽略-1最后的检查，因为这是 Python 的特殊值）。

Answer 4

你可以使用std哈希,这不错:

 std::size_t myHash = std::cout << std::hash<float>{}(myFloat);

Answer 5

unsigned hash(float x)
{
    union
    {
        float f;
        unsigned u;
    };
    f = x;
    return u;
}

技术上未定义的行为,但大多数编译器都支持这一点.替代方案:

unsigned hash(float x)
{
    return (unsigned&)x;
}

两种解决方案都取决于机器的字节顺序,因此例如在x86和SPARC上,它们将产生不同的结果.如果这不打扰你,只需使用这些解决方案之一.