7

このインタビューの質問をされました。それに対する正しい答えが何であるかはわかりません（および答えの背後にある理由）：

sin(x) は良いハッシュ関数ですか?

4

8 に答える 8

4

つまりsin()、次の理由により、これは適切なハッシュ関数ではありません。

  • それは非常に予測可能であり、一部xの人にとってはそれ自体に勝るものはありませんx. キーとキーのハッシュの間に一見明らかな関係があってはなりません。
  • 整数値は生成されません。浮動小数点インデックスを使用して配列をインデックス化/添字付けすることはできません。また、ハッシュ テーブルにある種の配列が必要です。
  • 浮動小数点は実装に非常に固有であり、からハッシュ関数を作成したとしてもsin()、別のコンパイラや別の種類の CPU/コンピューターでは機能しない可能性があります。
  • sin()単純な整数演算関数よりもはるかに遅い場合があります。
于 2012-10-10T21:45:30.960 に答える
3

あまり。

  1. 恐ろしく遅いです。
  2. 浮動小数点の等値比較の狂気を避けるために、とにかく結果を何らかの整数型に変換する必要があります。(実際には、FP 等値比較に特有であり、わずかに異なる 2 つのことを計算することから生じる通常の精度の問題ではありません。具体的には、387 派生の FPU が余分なビットの精度をレジスタに格納するという事実のようなものによって引き起こされる問題を意味します。そのため、レジスタ内の新たに計算された 2 つの値を比較すると、オペランドの 1 つだけがメモリからレジスタにロードされた場合とは異なる結果が得られる可能性があります。)
  3. 山と谷の近くではほぼ平坦であるため、量子化ステップ (大きな数を掛けて整数に丸める) により、均等な分布ではなく、最小値と最大値の近くに多くのハッシュ値が生成されます。
于 2012-10-10T21:48:17.680 に答える
1

注意すべきもう1つのポイント：

ハッシュ関数としてのsine（x）の場合-指定された近距離のキーにも近距離のハッシュ値が含まれるため、望ましくありません。優れたハッシュ関数は、キーの性質に関係なく、ハッシュ値を均等に分散します。

于 2012-10-10T22:17:01.763 に答える
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(..)

これは良いハッシュ関数の特性ではありません。

使用することにしたとしても、sin によって返される値を表すのは困難です。罪関数:

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

これは、浮動小数点の精度の問題により正確に表すことができません。つまり、同じ値に対して 2 つの異なるハッシュが生成される可能性があります。

于 2012-10-10T21:46:42.893 に答える
0

ハッシュ値は、通常、有用であるためには整数でなければなりません。sinは整数を生成しないため、適切ではありません。

于 2012-10-10T21:48:21.587 に答える
-1

賢く使えば、sin(x) は優れた暗号化ハッシュ関数になると思います。入力はラジアン単位の自然数である必要があり、決して pi を含んではなりません。任意精度の演算を使用する必要があります。すべての自然数 x (ラジアン) に対して、sin(x) は常に超越無理数であり、同じ正弦を持つ自然数は他にありません。しかし、落とし穴があります。攻撃者は、ハッシュのアークサインを計算することで、入力に関する情報を取得できます。これを防ぐために、小数部分と小数部分の最初の桁のいくつかを無視し、次の n (たとえば 100) 桁のみを保持して、このような攻撃を計算上実行不可能にします。入力を少し変更すると、まったく異なる結果が得られるようです。これは望ましい特性です。関数の結果は統計的にランダムに見えますが、これも良い特性です。私' それが衝突耐性であることを証明する方法がわかりませんが、なぜそれができなかったのかわかりません。また、特定のハッシュになる特定の入力を見つける方法が思いつきません。私は、それが確かに良い地下室であると盲目的に信じるべきだと言っているのではありません。ハッシュ関数。1つになるのは良い候補のように思えます。私たちはそれにチャンスを与え、それが正しいことを証明することに集中すべきです。そして、それは私にとって非常に良いものかもしれません。遅いと言う人へ: はい、そうです。これは、パスワードをハッシュする場合に適しています。ここに、このアイデアの 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 に答える