ランダムIDを「256で割った余り」で作ると、62文字中8文字だけ25%出やすくなる

背景

私は Hashitosystem という小さなブラウザツール集を一人で作っています。
その中に NanoID（URL に入れても崩れない短いランダムIDの形式）を作るツールがあります。
作る前の私は、乱数のバイトを文字数で割った余りで文字を選べば十分だと思っていました。
動くし、見た目もランダムなので、疑う理由が見当たらないんですよね（ここが一番怖いところです…）。
本家の NanoID のソースを読んだら余りを使っていなかったので、なぜかを手で数えてみました。

結論

先に結論を書きます。
62文字（英大文字・英小文字・数字）から1文字を選ぶとき、0〜255 のバイトを % 62 すると、最初の8文字だけが他より25%出やすくなります。
文字数を覆う最小のビットマスク（62文字なら 63 = 0b111111）でバイトを切り出し、62 と 63 が出たら捨てる。
これで全部の文字が同じ確率になります。

剰余だと何が起きるのか

256 を 62 で割ると、4 余り 8 です。
つまり 0〜255 を % 62 で 62 個の箱に配ると、どの箱にも4個ずつ入ったあと、8個だけ余る。
余った8個は箱の 0〜7 番に入るので、先頭8文字だけが5回、残り54文字は4回の割り当てになる、という仕組みだ。

確率にすると 5/256（約1.95%）と 4/256（約1.56%）で、先頭8文字は 1.25 倍出やすい計算になります。
1回だけ見ても分かりませんが、IDを大量に作るほど偏りは確実に積み上がります。
衝突のしやすさや、推測のしやすさを見積もるときの前提（全文字が等確率）が、こっそり崩れているということでもあります。

実際に全部数えてみます。
下記は 0〜255 の全バイト値を、剰余方式とマスク方式の両方で62文字に割り当てて、回数を集計するだけのスクリプトです。
乱数は使っていません（全部の値を1回ずつ流すので、確率をそのまま数えられます）。
bias.js という名前で保存して、Node.js で実行します。

// 0〜255 の全バイト値を、62文字のアルファベットに割り当てたときの回数を数える
const n = 62;
const modCount = new Array(n).fill(0);
for (let b = 0; b < 256; b++) modCount[b % n]++;
console.log('剰余方式: 5回の文字 =', modCount.filter(c => c === 5).length, '/ 4回の文字 =', modCount.filter(c => c === 4).length);

let mask = 1;
while (mask < n - 1) mask = (mask << 1) | 1;
const maskCount = new Array(n).fill(0);
let dropped = 0;
for (let b = 0; b < 256; b++) {
  const idx = b & mask;
  if (idx < n) maskCount[idx]++; else dropped++;
}
console.log('マスク方式: mask =', mask, '/ 各文字の回数 =', [...new Set(maskCount)], '/ 捨てるバイト =', dropped, '/ 256');

実行結果は下記です。

$ node bias.js
剰余方式: 5回の文字 = 8 / 4回の文字 = 54
マスク方式: mask = 63 / 各文字の回数 = [ 4 ] / 捨てるバイト = 8 / 256

剰余方式では8文字だけ5回になっているのがわかると思います。
マスク方式は全文字がちょうど4回で、そのかわり 256 個中8個のバイトを捨てています。

マスクの決め方

マスクは「0〜(文字数−1) を全部表せる、いちばん小さい 2のべき乗−1」です。
ツールでは下記の関数で求めています。
alphabetLength は使う文字の種類数で、ツールの画面で選んだ文字セットの長さがそのまま入ります。

function maskFor(alphabetLength) {
  const n = Math.max(2, Math.floor(Number(alphabetLength) || 0));
  let mask = 1;
  while (mask < n - 1) mask = (mask << 1) | 1;
  return mask;
}

console.log(maskFor(62)); // 63
console.log(maskFor(64)); // 63
console.log(maskFor(10)); // 15

ここで間違えやすいのが、ループの条件を mask < n と書いてしまうことです（ツールのソースにも、わざわざ注意書きのコメントを残してあります）。
そう書くと64文字のときに 63 で止まらず 127 まで行ってしまい、半分のバイトを捨てることになります。
結果は正しいままなので、テストも通るし画面も普通に動く…という、気づきにくい遅さでした。
必要なのは最大の添字（n−1）を覆うことなので、条件は mask < n - 1 が正しいです。

捨てるぶん、多めに読む

捨てる方式の欠点は、何バイト読めば足りるかが事前に決まらないことです。
NanoID 本家は、1回に読むバイト数を下記の式で決めていて、ツールも同じ式を使っています。
size は作りたいIDの長さ、mask は上の maskFor の結果、alphabetLength は文字の種類数です。

const step = Math.ceil((1.6 * mask * size) / alphabetLength);

62文字・21桁なら 1.6 × 63 × 21 ÷ 62 を切り上げて 35 バイトです。
63 中 62 が採用されるので、35 バイト読めばほぼ1回で21文字そろいます。
足りなかったときだけ、もう一度乱数を読みにいくループにしてあります。

乱数そのものはブラウザの crypto.getRandomValues から取っています。
これが使えない環境では、Math.random に黙って切り替えずに生成を止めるようにしました。
偏りを消しても、元の乱数が推測できるものなら意味が無いからです。

ツールはここで実際に動かせます。
https://hashitosystem.com/tools/nanoid/

なぜここまで気にするかというと、IDの長さを決めるときの「何個作ると衝突するか」の計算が、全文字が等確率という前提で成り立っているからです。
偏りがあると、画面に出している衝突までの年数そのものが少しだけ嘘になります。
自分で乱数から文字を選ぶコードを書くときは、% 文字数 ではなく、ビットマスクで切り出して範囲外を捨てる形にしておくのが正解です。

---

本記事はAI補助で執筆した、個人開発の紹介記事です。