4

さまざまなデータ（URL、キーワードなど）のハッシュを生成するための要件の一部として、PHPベースのプロジェクトにFNVハッシュアルゴリズムを統合しようとしています。

NevenBoyanovによるこの実装を見ました。彼は、PHPの算術制限のために、乗算の代わりにビット単位のシフトと加算を使用することを余儀なくされたと述べました。彼の実装は正しいですか？私の知識はコンピュータサイエンスのこの分野ではどういうわけか限られているので、自分でそれを確認することはできません。

私が持っているもう一つの質問は、FNVのさまざまな「フレーバー」についてです。32ビット、64ビット、および128ビットのバリアントを提供することを確認しましたが、上記の実装を使用すると、常に8文字の16進ハッシュが得られます（dechex（）を使用して整数の結果を16進に変換します）。

「Loremipsumdolorsit amet、consecteturadipiscingelit。Proinatlibero mi、quis luctus massa。」という入力が与えられると、次の16進数の結果が得られます。

  • （32ビットオフセット）5b15c0f2
  • （64ビットオフセット）6ea33cb5

なんでそうなの？64ビットFNVからの16文字の16進結果を期待しています。「フレーバー」は、使用される算術演算とシードの種類のみを指し、結果の長さは指しませんか？（つまり、64ビットFNVと言うと、ハッシュ関数は64ビット操作とシードを使用しますが、結果は32ビットのままです）

少しの啓蒙をいただければ幸いです:)

4

2 に答える 2

2

PHP FNV ハッシュ関数を書いたのはかなり前で、それは特定の目的のためのものでした。そのため、当時は 32 ビット実装で十分でした。

最初の質問に答えるために、実装は、アルゴリズム (コード) とサンプル結果を比較することにより、他の (C および C++) 実装に対してテストされました。したがって、32 ビットの結果の場合、正常に機能します。

64 ビット (または 128 ビット) バージョンを自分で実装する場合は、最初に FNV_offset_basis を変更する必要がありますが、73 行目の現在の式も変更する必要があります。

$hash += ($hash<<1) + ($hash<<4) + ($hash<<7) + ($hash<<8) + ($hash<<24);

... これは、2 進数で 1000000000000000110010011 である数値 16777619 (FNV_prime_32) を掛けることと同じです2^24 + 2^8 + 2^7 + 2^4 + 2^1 + 2^0。

64 ビットの場合は、1099511628211 を乗算する必要があります - バイナリ 100000000000000000000000000000110110011 ... 式: 2^88 + 2^8 + 2^7 + 2^5 + 2^4 + 2^1 + 2^0.

式が PHP によってどのように処理されるかはわかりませんが、$hash << 88自分で実験する必要があります。私の PHP 5.2.x では、31 を超える数値ではうまく機能しませんでした。

$hash = $hash & 0x0ffffffff;最後に、結果からガベージを削除するために を変更する必要がある場合があります。実験でわかった。64ビットの場合、otは次のようになり$hash = $hash & 0x0ffffffffffffffff;ます。PHP で正しく動作するかどうかを確認します。

より高い演算精度のために、他の PHP ライブラリを使用することもできます。私の意見では、ビット単位のシフトを使用する方が高速です。

実際、任意の数のビットに対して FNV ハッシュを生成できます。

于 2012-06-20T07:35:58.860 に答える
0

私が引用した実装は、32 ビット FNV1 専用であることがわかりました。私はなんとか FNV のC ソースをコンパイルし 、バイナリとトムが提案したツールを使用して、64 ビット FNV が実際に 16 文字の 16 進ハッシュを返すことを確認しました。

于 2012-06-12T05:45:10.363 に答える