短い文字列から、低コストで安定したハッシュ値を作りたい場面はよくあります。たとえば、一時的なキーを作るときや、同じ入力から常に同じ値を得たいときです。そういう場面でよく出てくるのが FNV-1a です。

ただし、FNV-1a 自体は単純でも、JavaScript でそのまま書くと仕様どおりの 32-bit 計算にならないことがあります。ここで最初に注意したいのは、この点です。難しいのはアルゴリズムの理解というより、JavaScript で 32-bit 整数演算をどう表現するかです。

この記事では、まず FNV-1a が何をするハッシュなのかを短く確認し、そのあとで、素朴な実装が仕様とずれる箇所を確認します。そのうえで、Math.imul と >>> 0 が何を補っているのかを順に整理します。

以下では、まず FNV-1a の動きを簡単に確認し、そのあとで素朴な実装がどこで仕様とずれるのかを確認していきます。

結論

FNV-1a 32-bit は、短い入力に対して低コストで使えるハッシュです。暗号用途には向きませんが、簡単なキー生成には使いやすいです。
JavaScript で押さえたいのは、普通の * ではなく Math.imul を使うことです。これで 32-bit 整数乗算を正しく表現しやすくなります。
さらに >>> 0 を付けると、結果を unsigned 32-bit として扱えます。FNV-1a の 32-bit unsigned 値として扱うために入れておくと分かりやすいです。
文字列をそのまま charCodeAt() で回すと UTF-16 code unit ベースになります。FNV-1a の仕様どおりに byte 列を処理したいなら、TextEncoder で UTF-8 bytes に変換してから計算します。
FNV-1a は軽量で同期的に使いやすい一方、暗号用途や大量データの一意識別には向きません。用途に応じて SHA-256 や xxHash などと使い分けることになります。

FNV-1a の仕様

まずは、「何を 1 単位として繰り返すのか」だけ押さえれば十分です。

FNV (Fowler–Noll–Vo) hash function の 1a variant は次の擬似コードです。

hash := FNV_offset_basis  // 32-bit: 2166136261 (0x811c9dc5)
for each octet of input:
    hash := hash XOR octet
    hash := hash × FNV_prime  // 32-bit: 16777619 (0x01000193)
return hash (32-bit unsigned)

ポイントは「XOR を先に行い、そのあとで掛け算をする」ことです。これが FNV-1 と FNV-1a の違いで、一般には 1a のほうが分布がよいとされています。

もうひとつ重要なのは、仕様が for each octet of input、つまり byte 列 を前提にしていることです。文字列をそのまま回すのではなく、最終的には byte 列として処理する必要があります。

JavaScript での素朴な実装

ここでは、JavaScript で最初に書きたくなる形を確認します。

たとえば、次のように書きたくなります。

function fnv1a(str: string): number {
  let h = 2166136261;
  for (let i = 0; i < str.length; i++) {
    h ^= str.charCodeAt(i);
    h = h * 16777619; // (1) ここが問題
  }
  return h;
}

問題は 2 つあります。

1 つ目は (1) の h * 16777619 です。JavaScript の number は 64-bit 浮動小数点です。整数も表せますが、安全に正確な整数として扱える範囲には限界があります。FNV-1a では 32-bit の値に 16777619 を掛けるため、途中結果が安全整数の範囲を超えやすく、通常の * では仕様どおりの 32-bit 整数乗算になりません。

2 つ目は charCodeAt() です。これは UTF-16 code unit を返すので、ASCII だけなら見た目どおり動きますが、日本語や絵文字を含む文字列では「UTF-8 bytes に対する FNV-1a」とは別の計算になります。

短い ASCII 入力ではそれらしく見えても、長い入力や非 ASCII 文字を含む入力では、参照実装と違う結果になり始めます。ここが JavaScript で FNV-1a を書くときの最初の注意点です。

文字列を byte 列にする

FNV-1a の仕様に寄せるなら、文字列は先に UTF-8 の byte 列へ変換してから処理するのが自然です。JavaScript では TextEncoder を使うと、ここを明確に書けます。

`Math.imul` で 32-bit 乗算

ここからは、JavaScript で 32-bit 整数演算を表現する部分です。

Math.imul + >>> 0 が表現しているのは、「32-bit で掛け算し、その結果を unsigned 32-bit の値として扱う」という流れです。FNV-1a は 32-bit unsigned 整数を前提に進むので、JavaScript ではこの 2 つを組み合わせて書くと意図が明確になります。

Math.imul(a, b) は ECMAScript 2015 で導入された API で、引数を 32-bit signed integer に変換してから乗算し、結果も 32-bit signed integer として返します。通常の * と違って、32-bit 整数演算として扱いたい場面に向いています。

export function fnv1a32(input: string): number {
  const bytes = new TextEncoder().encode(input);

  let h = 0x811c9dc5;

  for (const byte of bytes) {
    h ^= byte;
    h = Math.imul(h, 0x01000193) >>> 0;
  }

  return h >>> 0;
}

Math.imul(h, 0x01000193) の結果は signed 32-bit (-2^31 ~ 2^31 - 1) です。FNV-1a は unsigned 32-bit を前提にしているので、>>> 0 で unsigned に解釈し直します。

>>> 0 は 0 ビットの zero-fill right shift です。見た目には何もしていないように見えますが、JavaScript ではこの形で unsigned 32-bit へ揃えられます。ビット列としては同じでも、JavaScript の表示上は signed integer として負の数になることがあります。>>> 0 は、その同じ 32-bit のビット列を unsigned の数値として扱い直すために使います。

ASCII だけを入力にする、あるいは「UTF-16 code unit に対する安定ハッシュ」でよいなら charCodeAt() 版でも動きます。ただし、それは「UTF-16 code unit 列に対する独自の安定ハッシュ」です。FNV-1a の仕様どおりに octet、つまり byte 列を処理したい場合は、TextEncoder を使うほうが意図を明確にしやすくなります。

出力を hex 文字列に

計算結果が得られたら、次は使いやすい形へ変換します。

キーとして使うなら 16 進文字列にしておくと扱いやすいです。

function fnv1aHex(str: string): string {
  return fnv1a32(str).toString(16).padStart(8, '0');
}

console.log(fnv1aHex('hello world')); // "d58b3fa7"

padStart(8, '0') で固定長 8 文字にすると、キーの長さが入力に依存しなくなります。

衝突確率と応用

次に、32-bit ハッシュの衝突リスクを確認します。

FNV-1a 32-bit が返せる値は約 43 億通りです。一見すると十分に多いように見えますが、キーの件数が増えると、同じ値にぶつかる可能性は少しずつ上がります。100 万件規模になると、誕生日パラドックスの影響で衝突を無視しにくくなります。

ランダムに近く分布すると仮定すると、100 万件では期待される衝突ペア数はおよそ 116 件です。そのため、32-bit FNV-1a は「少数の一時キー」や「衝突しても吸収できる用途」には向きますが、大量データの一意識別子としては短めです。

衝突確率をさらに下げたいなら、入力に異なる salt を付けて複数回ハッシュし、その結果を連結する簡易策もあります。ただし、この方法は SHA-256 のような暗号学的な 256-bit ハッシュではありません。FNV-1a を salt 違いで複数回実行して連結しているだけなので、各パートが暗号学的に独立しているわけではありません。ここでは「32-bit 単体より衝突しにくいキーを簡単に作る妥協案」として扱います。

export function simpleStableHashHex(s: string): string {
  const parts: string[] = [];
  for (let i = 0; i < 8; i++) {
    parts.push(
      fnv1a32(String.fromCharCode(i + 1) + s)
        .toString(16)
        .padStart(8, '0'),
    );
  }
  return parts.join('');
}

salt として String.fromCharCode(i + 1) を使う意図は、入力に通常は含まれにくい ASCII 制御文字 (0x01 - 0x08) を区切りとして付けることです。ここでは prefix にして、同じ文字列を少しずつ違う入力として 8 回ハッシュしています。

衝突が問題になる用途では、このような簡易拡張よりも、xxHash 64/128 や SHA-256 など、用途に合った長いハッシュを選ぶほうが設計を整理しやすくなります。

なぜ SHA-256 ではなく FNV-1a を選ぶのか

ここで押さえておきたいのは、FNV-1a が SHA-256 より優れているということではなく、用途が異なるという点です。

Web Crypto API の crypto.subtle.digest('SHA-256', bytes) は非同期です。頻繁に呼ばれる処理の中で単純なキーを作りたいだけなら、毎回 await を挟む構成が重く感じられることがあります。

同期で使えること: 初期化処理や単純なキー生成の中で、そのまま使えます。
依存ライブラリが不要なこと: 短い関数だけで完結します。
計算が軽いこと: 短い入力を大量に処理する場面では有利です。

ただし、衝突耐性は SHA-256 のほうが圧倒的に高いです。したがって、両者は同じ目的で置き換えるものではありません。

用途	推奨
一時的なキー生成 (衝突しても致命的ではない)	FNV-1a
内容そのものを識別するキー	SHA-256
パスワードハッシュ	Argon2id / bcrypt
暗号学的署名	HMAC-SHA-256 / Ed25519

トレードオフ

FNV-1a は暗号学的ハッシュではない: 攻撃者に対する耐性は期待できません。衝突耐性や改ざん検知、署名、認証の用途には使わないほうが安全です。たとえば、攻撃者が入力を自由に制御でき、そのハッシュ値だけを cache key として使っている場合、意図的な衝突によって別の内容を同じキーに寄せられる可能性があります。
Math.imul の利用条件: ES2015 以降です。古い環境 (IE11) では polyfill が必要ですが、Edge runtime / 現代ブラウザでは問題ありません。
64-bit FNV-1a: 32-bit より衝突しにくいですが、JS の Number は 53-bit 精度のため 64-bit 演算は BigInt が必要で、性能が大きく落ちます。用途によっては xxHash 64/128 や SHA-256 を選ぶほうが設計として分かりやすいです。

まとめ

Math.imul + >>> 0 の組み合わせを使うと、FNV-1a 32-bit を JavaScript で仕様どおりに書けます。文字列を一般的に扱うなら、先に TextEncoder で UTF-8 bytes に変換してから処理するほうが安全です。まずは 32-bit 版を正しく書き、衝突確率が気になるときだけ長いキーへ広げる、という順で考えると整理しやすくなります。SHA-256 が必要な場面と、FNV-1a で十分な場面を分けて考えることが、設計上のポイントです。