浮动的哈希函数 [英] Hash function for floats

问题描述

我目前正在使用C ++实现一个哈希表，我想为浮动创建一个哈希函数...

我要处理浮点数整数通过填充十进制数字，但是我意识到，我可能达到溢出与大数字...

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

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

注意：

1. 我不需要它真的很快，




2. 我看过浮动广告不应该被哈希处理，因为计算的速度，有人可以确认/解释这个，并给我其他原因浮动不应该被散列？我不太明白为什么（速度除外）

解决方案

取决于应用程序，但大多数时间浮点不应该被哈希，因为哈希用于快速查找精确匹配，大多数浮点是产生一个只是一个近似正确答案的浮点的计算的结果。检查浮动等式的通常方法是检查它是否在正确答案的一些增量（绝对值）内。

EDIT ：

p>通常，由于舍入误差和浮点运算的固有限制，如果你期望浮点数 a 和 b 应该相等，因为数学说，所以你需要选择一些相对小 delta> 0 ，然后您声明 a 和 b c> abs（ab） delta ，其中 abs 是绝对值函数。有关详情，请参见本文。

下面是一个小例子演示了问题：

  float x = 1.0 F; 
 x = x / 41; 
 x = x * 41; 
 if（x！= 1.0f）
 {
 std :: cout< ooops ... \\\
; 
} 
  

根据您的平台，编译器和优化级别， $ c> 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...\n";
}

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.

这篇关于浮动的哈希函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！