Fowler-Noll-Vo FNV1-64 ハッシュコード計算機

FNV-1 64ビットハッシュ関数は、Fowler-Noll-Vo (FNV) ハッシュ関数ファミリーの一部であり、ハッシュ値の良好な分布を維持しながら高速にハッシュ処理を実行するように設計されています。ハッシュテーブル、チェックサム、データルックアップなどのアプリケーションで広く使用されています。この関数は64ビット（8バイト）のハッシュコードを生成します。このハッシュコードは、多くの場合、16桁の16進数で表されます。

完全開示：このページで使われているハッシュ関数の特定の実装を書いたのは私ではない。これはPHPプログラミング言語に含まれる標準関数である。私は便宜上、ウェブ・インターフェースを作成し、ここで一般に利用できるようにしただけである。

Fowler-Noll-Vo FNV-1 64ビットハッシュアルゴリズムについて

私は数学者ではありませんが、このハッシュ関数を、数学者ではない仲間にも理解しやすいアナロジーを使って説明してみたいと思います。科学的に正しく、しかも恐ろしい数学的な説明がお好みなら、きっと他の場所で見つけられるでしょう ;-)

まず、FNV-1アルゴリズムを特別なスムージーを作るレシピに例えてみましょう。加える材料（フルーツ、牛乳、蜂蜜など）は、文字、数字、あるいはファイル全体といったデータの一部を表します。

さて、目標はこれらの材料を非常に特殊な方法で混ぜ合わせることです。レシピにほんの少し変更を加えるだけでも（例えばブルーベリーを1つ追加するだけで）、スムージーの味は全く異なるものになります。ハッシュ関数はこのように機能します。ハッシュ関数は、材料（または入力データ）の組み合わせごとに、固有の「フレーバー」（またはハッシュ値）を作成します。

FNV-1 アルゴリズムがこれを実行する方法は、複数のステップから成るプロセスです。

ステップ1：ベース（オフセットベース）から始める

特別なスムージーベースをブレンダーに注ぐようなものだと想像してみてください。このベースは、どんな材料を加えても常に同じです。FNV-1では、これは「オフセットベース」と呼ばれています。これは、単に開始時の数字を当てはめたものです。

ステップ2：材料を一つずつ追加する（データ処理）

さあ、材料を一つずつ加えていきましょう。例えば、イチゴ、バナナ、そしてハチミツ。それぞれが1バイトのデータを表します。

ステップ3：秘密の乗数（FNVプライム）でブレンドする

材料を一つずつ加えたら、ブレンドボタンを押します。ところが、ここでちょっとした工夫があります。ブレンダーがすべての材料に「FNVプライム」と呼ばれる秘密の「魔法の数字」を掛け合わせます。これにより、材料が完璧に混ざり合うのです。

ステップ4：魔法のひと手間を加える（XOR演算）

次の材料を加える前に、魔法の粉を少し振りかけます（これはXOR演算です）。まるで予想外の方法で風味をひっくり返し、小さな変化でも大きな違いを生み出すような感覚です。

ステップ5：完了するまで繰り返す

すべての材料を加工し終わるまで、新しい材料を加えるたびに、混ぜたり魔法をかけたりし続けます。

ステップ6：最終スムージー（ハッシュ値）

完成したらスムージーを注ぎます。最終的な味（ハッシュ値）は、材料の組み合わせによって決まります。ブルーベリーを1粒でも追加すれば、全く違う味になるでしょう。

ここで紹介しているのはオリジナルのFNV-1 64ビット版です。改良されたFNV-1a 64ビット版も利用可能です: リンク

さらに読む

この投稿が気に入った場合は、次の提案も気に入るかもしれません:

• HAVAL-128/4 ハッシュコード計算機
• Tiger-128/4 ハッシュコード計算機
• RIPEMD-256 ハッシュコード計算機