7

我被问到这个面试问题。我不确定它的正确答案是什么（以及答案背后的原因）：

sin(x) 是一个好的散列函数吗？

4

8 回答 8

4

如果您的意思是sin()，这不是一个好的散列函数，因为：

  • 这是完全可以预测的，对某些人x来说，它并不比它x本身更好。密钥和密钥的散列之间不应存在看似明显的关系。
  • 它不会产生整数值。您不能使用浮点索引对数组进行索引/下标，并且哈希表中必须存在某种数组。
  • 浮点数是非常特定于实现的，即使您使用sin().
  • sin()可能比一些更简单的整数算术函数慢得多。
于 2012-10-10T21:45:30.960 回答
3

并不真地。

  1. 它慢得可怕。
  2. 无论如何，您都需要将结果转换为某种整数类型，以避免浮点相等比较的疯狂。（实际上并不是 FP 相等比较特有的常见精度问题，它们是由计算两种略有不同的方式引起的；我的意思是特别是由诸如 387 派生的 FPU 在其寄存器中存储额外的精度位之类的事实引起的问题，因此，如果在寄存器中的两个新计算的值之间进行比较，则与将其中一个操作数从内存加载到寄存器中的情况不同，您可能会得到不同的答案。）
  3. 它在波峰和波谷附近几乎是平坦的，因此量化步骤（乘以某个大数并舍入为整数）将在最小值和最大值附近产生许多散列值，而不是均匀分布。
于 2012-10-10T21:48:17.680 回答
1

基于数学知识：

Sine(x) 是周期性的，所以它会从不同的 x 值达到相同的数字，所以 Sine(x) 作为散列函数会很糟糕，因为你会得到多个值散列到完全相同的点。返回值在 0 和 pi 之间有 ** 无限多个值，但超过该值将重复。所以 0 & pi & 2*pi 都会散列到同一个点。

如果您可以使增量足够小，并将 Sine(x) 乘以 x^2 或类似性质的东西，那么它充其量只是平庸，但话又说回来，如果您要这样做，为什么不只使用 x^2无论如何，把周期函数一起扔掉。

**无限：一个足够大的数字，我不愿意数。

注意：Sine(x) 的值很小，可能会受到舍入误差的影响。

注意：从正弦函数中获取的任何值都应该乘以一个整数，然后进行修改或取地板或天花板，以便该值可以用作数组偏移量等。

于 2012-10-10T21:44:32.963 回答
1

sin(x)是三角函数，每 360 度重复一次，所以它会是一个糟糕的散列函数，因为散列会经常重复。

一个简单的反驳：

sin(0) == sin(360) == sin(720) == sin(..)

这不是 goodhash 函数的属性。

即使你决定使用它，也很难表示 sin 返回的值。正弦函数：

sin x = x - x^3/3! + x^5/5! - ...

由于浮点精度问题，这无法准确表示，这意味着对于相同的值，它可能会产生两个不同的哈希值！

于 2012-10-10T21:46:42.893 回答
1

还有一点需要注意：

对于 sine(x) 作为散列函数 - 给定近距离范围内的键也将具有近距离散列值，这是不可取的。一个好的散列函数可以均匀地分布散列值，而不管键的性质如何。

于 2012-10-10T22:17:01.763 回答
0

哈希值通常必须是整数才能有用。由于sin不生成整数，因此不合适。

于 2012-10-10T21:48:21.587 回答
0

假设我们有一个字符串 s。它可以表示为十六进制的数字并提供给函数。如果您添加 2 pi，它将不再是有效输入，因为它不再是整数（该函数只接受非负整数）。您必须找到一个会产生冲突的字符串，而不仅仅是将字符串的十六进制表达式乘以 2 pi。并且将（连接？） 2 pi 直接添加到字符串不会有助于发现冲突。虽然可能有另一种方法，但不是那么微不足道。

于 2015-11-23T22:31:32.513 回答
-1

如果使用得当，我认为 sin(x) 可以成为出色的加密哈希函数。输入应该是以弧度表示的自然数，并且从不包含 pi。我们必须使用任意精度的算术。对于每个自然数 x（弧度），sin(x) 始终是一个超越无理数，并且没有其他自然数具有相同的正弦值。但是有一个问题：攻击者可以通过计算散列的反正弦来获取有关输入的信息。为了防止这种情况，我们忽略了小数部分和小数部分的一些前数字，只保留接下来的 n（比如 100）位数字，使得这种攻击在计算上不可行。似乎输入的微小变化会产生完全不同的结果，这是一个理想的属性。该函数的结果在统计上似乎是随机的，这也是一个很好的属性。一世' 我不知道如何证明它是抗碰撞的，但我不明白为什么它不能。另外，我想不出一种方法来找到导致特定散列的特定输入。我并不是说我们应该盲目地相信它肯定是一个好的地穴。哈希函数。我只是认为成为其中之一似乎是一个很好的候选人。我们应该给它一个机会，并专注于证明它是。这对我来说可能是一个非常好的。对于那些可能会说它很慢的人：是的，确实如此。这在散列密码时很好。在这里，我为这个想法附上了一些 perl 代码。它使用 bash 和 bc 在 linux 上运行。（bc 是一个命令行任意精度计算器，包含在大多数发行版中）我将检查此页面以获取任何答案，因为这让我很感兴趣。不过不要苛刻，我只是一名CS本科生，愿意学习更多。

use warnings;
use strict;
my $input='5AFF36B7';#Input for bc (as a hex number)
$input='1'.$input;#put '1' in front of input, so that 0x0 , 0x00 , 0x1 , 0x01 , etc ... ,
                  #all give different nonzero results

my $a=`bc -l -q <<< "scale=256;obase=16;ibase=16;s($input)"`;#call bc, keep result in $a

#keep only fractional part
$a=~tr/a-zA-Z0-9//cd;#Clean up string, keep only alphanumerics
my @m = $a =~ /./g;#Convert string to array of chars

#PRINT OUTPUT
#We ignore some digits, for security reasons:
#If we don't ignore any of the first digits, an attacker could gain information
#about the input by computing the inverse of sin (the arcsin of the hash)
#By ignoring enough of the first digits, it becomes computationally
#infeasible to compute arcsin
#Also, to avoid problems with roundoff error, we ignore some of the last digits
for (my $c=100;$c<200;$c++){
    print $m[$c];
}
于 2015-11-23T21:41:25.923 回答