24

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

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

有没有很好的方法来散列浮点数？

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

笔记：

  1. 我不需要它非常快，如果可能的话，只需均匀分布即可。

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

4

7 回答 7

17

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

编辑：

通常，由于舍入误差和浮点运算的固有限制，如果您希望浮点数a和b应该彼此相等，因为数学上是这样的，您需要选择一些相对较小delta > 0的 ，然后声明a和b相等如果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 次方的有理数。

于 2010-11-21T13:49:49.663 回答
11

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

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

这样，您将屏蔽掉 12 个最低有效位，从而产生一定程度的不确定性……但这实际上取决于您的应用程序。

于 2010-11-21T14:03:19.990 回答
9

您可以使用 std 哈希，这还不错：

 std::size_t myHash = std::cout << std::hash<float>{}(myFloat);
于 2016-09-30T11:04:10.950 回答
6 
unsigned hash(float x)
{
    union
    {
        float f;
        unsigned u;
    };
    f = x;
    return u;
}

技术上未定义的行为，但大多数编译器都支持这一点。替代解决方案：

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

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

于 2010-11-21T13:45:52.137 回答
4

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

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

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

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

建议的实施步骤：

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

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

Python是在生产代码_Py_HashDouble中如何散列 a 的一个很好的参考（忽略最后的检查，因为这是 Python 的特殊值）。float-1

于 2015-02-16T21:12:54.747 回答
1

如果你有兴趣，我刚刚做了一个使用浮点并且可以散列浮点数的散列函数。它还通过了 SMHasher（这是非加密哈希函数的主要偏差测试）。由于浮点计算，它比普通的非加密哈希函数慢很多。

我不确定tifuhash是否会对所有应用程序都有用，但有趣的是看到一个简单的浮点函数同时通过 PractRand 和 SMHasher。

主状态更新函数非常简单，如下所示：

function q( state, val, numerator, denominator ) {
  // Continued Fraction mixed with Egyptian fraction "Continued Egyptian Fraction"
  // with denominator = val + pos / state[1]
  state[0] += numerator / denominator;
  state[0] = 1.0 / state[0];

  // Standard Continued Fraction with a_i = val, b_i = (a_i-1) + i + 1
  state[1] += val;
  state[1] = numerator / state[1];
}

无论如何，你可以在 npm 上获取它， 或者你可以查看 github

使用很简单：

const tifu = require('tifuhash');

const message = 'The medium is the message.';
const number = 333333333;
const float = Math.PI;

console.log( tifu.hash( message ), 
  tifu.hash( number ),
  tifu.hash( float ),
tifu.hash( ) );

这里有一个关于 runkit 的一些哈希的演示https://runkit.com/593a239c56ebfd0012d15fc9/593e4d7014d66100120ecdb9

旁注：我认为将来使用浮点，可能是浮点计算的大数组，可能是将来制作更多计算要求的哈希函数的有用方法。我发现使用浮点的一个奇怪的副作用是哈希是依赖于目标的，我推测它们也许可以用来识别计算它们的平台。

于 2017-06-12T08:12:44.600 回答
0

由于 IEEE 字节排序，Java Float.hashCode() 和 Double.hashCode() 没有给出好的结果。这个问题是众所周知的，可以通过这个加扰器来解决：

class HashScrambler {

    /**
     * https://sites.google.com/site/murmurhash/
     */
    static int murmur(int x) {
        x ^= x >> 13;
        x *= 0x5bd1e995;
        return x ^ (x >> 15);
    }

}

然后你会得到一个很好的哈希函数，它还允许你在哈希表中使用 Float 和 Double。但是您需要编写自己的哈希表，允许自定义哈希函数。

由于在哈希表中您还需要测试相等性，因此您需要完全相等才能使其工作。也许后者是詹姆斯·K·波尔克总统打算解决的问题？

于 2020-12-12T00:18:15.180 回答