浮点数的散列函数

2022-01-09 00:00:00 floating-point hashtable c++ hash-function

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

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

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

你不必直接给我函数，但我想看看/理解不同的概念......

注意事项:

  1. 我不需要它真的很快，只要可能的话均匀分布即可.

  2. 我已经读到，由于计算速度的原因，不应该对浮点数进行散列，有人可以确认/解释这一点并给我其他为什么不应该散列浮点数的原因吗?我真的不明白为什么(除了速度)

解决方案

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

编辑:

通常，由于舍入误差和浮点运算的固有限制，如果您期望浮点数 a 和 b 应该彼此相等，因为数学这么说，你需要选择一些相对小的delta>0，然后声明 a 和 b 相等，如果 abs(a-b) abs(a-b) <delta，其中abs是绝对值函数.有关详细信息，请参阅这篇文章.p>

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

float x = 1.0f;x = x/41;x = x * 41;如果 (x != 1.0f){std::cout <<"哎呀...
";}

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

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

I'm currently implementing a hash table in C++ and I'm trying to make a hash function for floats...

I was going to treat floats as integers by padding the decimal numbers, but then I realized that I would probably reach the overflow with big numbers...

Is there a good way to hash floats?

You don't have to give me the function directly, but I'd like to see/understand different concepts...

Notes:

  1. I don't need it to be really fast, just evenly distributed if possible.

  2. I've read that floats should not be hashed because of the speed of computation, can someone confirm/explain this and give me other reasons why floats should not be hashed? I don't really understand why (besides the speed)

解决方案

It depends on the application but most of time floats should not be hashed because hashing is used for fast lookup for exact matches and most floats are the result of calculations that produce a float which is only an approximation to the correct answer. The usually way to check for floating equality is to check if it is within some delta (in absolute value) of the correct answer. This type of check does not lend itself to hashed lookup tables.

EDIT:

Normally, because of rounding errors and inherent limitations of floating point arithmetic, if you expect that floating point numbers a and b should be equal to each other because the math says so, you need to pick some relatively small delta > 0, and then you declare a and b to be equal if abs(a-b) < delta, where abs is the absolute value function. For more detail, see this article.

Here is a small example that demonstrates the problem:

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

Depending on your platform, compiler and optimization levels, this may print ooops... to your screen, meaning that the mathematical equation x / y * y = x does not necessarily hold on your computer.

There are cases where floating point arithmetic produces exact results, e.g. reasonably sized integers and rationals with power-of-2 denominators.

相关文章