Nano IDが%を使わない理由 — 36文字なら256中112を捨てる

ランダムな ID を自前で作るとき、乱数を1バイト取って alphabet[byte % alphabet.length] と書くのはよくある書き方である。文字が64種類ならこれで問題ないが、62種類や36種類にした途端、一部の文字だけが出やすくなる。いわゆる modulo bias で、ID の予測しにくさがその分だけ下がる。

この記事では、ハシトシステムの NanoID 生成ツール と、npm の nanoid パッケージ（手元の node_modules に入っていた 3.3.11 の index.js）のコードを読み、偏りの大きさと、それを避ける「マスクして範囲外を捨てる」方式の手間を Node.js で数える。

256 を文字数で割り切れないと偏る

1バイトの乱数は 0〜255 の256通りで、どれも同じ確率で出る。これを % n で 0〜n-1 に縮めると、256 が n で割り切れない場合、余りの分だけ小さい番号が1回多く選ばれる。

  • 62文字（英大小文字+数字）: 256 = 62 × 4 + 8。先頭8文字（A〜H）は5回、残り54文字は4回選ばれる。A〜H は他の文字の1.25倍出やすい。
  • 36文字（英小文字+数字）: 256 = 36 × 7 + 4。先頭4文字（a〜d）は8回、残りは7回。約1.14倍。
  • 10文字（数字のみ）: 256 = 10 × 25 + 6。0〜5 は26回、6〜9 は25回。1.04倍。
  • 64文字（URL で使える英数字と _ -）: 256 = 64 × 4 で割り切れるので偏らない。

nanoid の既定の nanoid() 関数は64文字のアルファベットを使い、pool[i] & 63 で下位6ビットを取り出しているだけで、捨てる処理は無い。64文字だから成り立つ書き方で、これを真似て文字数だけ変えると偏りが入る。

マスクで切り出し、範囲外は捨てる

文字数を自由に選べる customAlphabet は、別の関数 customRandom を通る。該当部分は次のとおりである（nanoid 3.3.11 の index.js から）。

1
2
3
4
let mask = (2 << (31 - Math.clz32((alphabet.length - 1) | 1))) - 1
let step = Math.ceil((1.6 * mask * defaultSize) / alphabet.length)
// ...
id += alphabet[bytes[i] & mask] || ''

mask は 0〜(文字数-1) を覆う最小の「2のべき乗 - 1」である。36文字なら35を覆う63（2進で 111111）になる。バイトを & 63 で 0〜63 に縮めると64通りが均等に出るので、36以上が出たら alphabet[...] が undefined になり、|| '' で何も足さずに次のバイトへ進む。残った 0〜35 は均等なので、偏りは消える。

代わりにバイトを捨てる。36文字なら64通りのうち28通りを捨てるので、1バイトあたりの採用率は 36/64 = 56.25% になる。256通りで数えると112個が捨てられる。

ツール側の maskFor は clz32 を使わず、mask = 1 から始めて mask < n - 1 の間だけ左シフトして1を足す、というループで同じ値を出している。ツールのソースには、条件を mask < n にすると64文字のときに127になり、半分のバイトを捨てることになる、というコメントが残っている。2〜256 のすべての文字数で nanoid の式と値が一致することは、下の手順で確かめた。

step は「1回で足りる」ように多めに取る

捨てる分があるので、21文字の ID を作るのに21バイトでは足りないことが多い。customRandom は1回に step バイトをまとめて取り、足りなければもう一度取る。step は 1.6 × mask × 長さ ÷ 文字数 を切り上げた値で、mask ÷ 文字数 はおおよそ採用率の逆数になる。1.6 はそれに掛ける余裕分である。

36文字・21文字なら ceil(1.6 × 63 × 21 ÷ 36) = 59 バイトになる。59バイトのうち採用されるのは平均で約33個なので、ほとんどの場合1回で21文字がそろう。

実際に試す

Node.js 24.11.1（Windows 11）で実行した。依存パッケージは要らない。次の内容を nanoid-bias.mjs として保存する。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// nanoid-bias.mjs : 乱数バイトから ID の文字を選ぶときの偏りを、256 通りの全数で数える
import { randomFillSync } from 'node:crypto';

const ALPHA = {
  url: 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-', // 64
  alnum: 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789',   // 62
  lower: 'abcdefghijklmnopqrstuvwxyz0123456789',                             // 36
  digits: '0123456789',                                                       // 10
};

// nanoid の customRandom と同じマスク: 0..n-1 を覆う最小の 2^k - 1
const maskOf = (n) => (2 << (31 - Math.clz32((n - 1) | 1))) - 1;

// 1バイト（0..255）の全通りを流して、各文字が何回選ばれるかを数える
function countAll(n, pick) {
  const c = new Array(n).fill(0);
  let rejected = 0;
  for (let b = 0; b < 256; b++) {
    const i = pick(b, n);
    if (i === null) rejected++; else c[i]++;
  }
  return { min: Math.min(...c), max: Math.max(...c), rejected };
}
const byMod = (b, n) => b % n;
const byMask = (b, n) => { const i = b & maskOf(n); return i < n ? i : null; };

console.log('alphabet  n   % : min-max(回)  先頭が出やすい倍率 | & mask : mask min-max 捨てる');
for (const [name, a] of Object.entries(ALPHA)) {
  const n = a.length;
  const m = countAll(n, byMod);
  const k = countAll(n, byMask);
  console.log(
    `${name.padEnd(8)} ${String(n).padStart(2)}   ${m.min}-${m.max}`.padEnd(26) +
    `${(m.max / m.min).toFixed(3)}`.padEnd(20) +
    `| ${String(maskOf(n)).padStart(3)}  ${k.min}-${k.max}  ${k.rejected}/256`
  );
}

// customAlphabet の1回あたりのバイト数 step と、1回で足りる割合を実測する
const size = 21;
for (const [name, a] of Object.entries(ALPHA)) {
  const n = a.length, mask = maskOf(n);
  const step = Math.ceil((1.6 * mask * size) / n);
  const trials = 100000;
  let oneShot = 0;
  const buf = Buffer.alloc(step);
  for (let t = 0; t < trials; t++) {
    randomFillSync(buf);
    let got = 0;
    for (const b of buf) if ((b & mask) < n) got++;
    if (got >= size) oneShot++;
  }
  console.log(`${name.padEnd(8)} step=${String(step).padStart(2)}  1回で21文字そろう割合 ${(oneShot / trials * 100).toFixed(3)}%`);
}
1
node nanoid-bias.mjs

出力（下の4行は乱数を使うので、実行のたびに少し変わる）:

1
2
3
4
5
6
7
8
9
alphabet  n   % : min-max(回)  先頭が出やすい倍率 | & mask : mask min-max 捨てる
url      64   4-4         1.000               |  63  4-4  0/256
alnum    62   4-5         1.250               |  63  4-4  8/256
lower    36   7-8         1.143               |  63  4-4  112/256
digits   10   25-26       1.040               |  15  16-16  96/256
url      step=34  1回で21文字そろう割合 100.000%
alnum    step=35  1回で21文字そろう割合 100.000%
lower    step=59  1回で21文字そろう割合 99.960%
digits   step=51  1回で21文字そろう割合 99.919%

% の列では、64文字以外のすべてで最小と最大が1回ずれている。& mask の列はどの文字数でも最小と最大が同じで、その代わりに右端の数だけバイトを捨てている。36文字では256通り中112通り、10文字では mask が15なので96通りを捨てる。

step 分のバイトで1回のうちに21文字がそろう割合は、10万回の試行で99.9%を超えた。そろわなかった残りは、customRandom がもう一度 step バイトを取って続きを埋める。

ツールのループ版のマスクが nanoid の式と一致するかは、次の1行で確かめられる。

1
node -e "function maskFor(n){var m=1;while(m<n-1)m=(m<<1)|1;return m} const u=n=>(2<<(31-Math.clz32((n-1)|1)))-1; const bad=[]; for(let n=2;n<=256;n++) if(maskFor(n)!==u(n)) bad.push(n); console.log('mismatch', bad)"
1
mismatch []

長さと文字数で衝突しにくさが変わる

偏りを消しても、ID の強さは「文字数の長さ乗」で決まる。1文字あたりのビット数は log2(文字数) で、21文字なら64文字で126ビット、36文字で約108.6ビット、10文字では約69.8ビットになる。ツールが使う誕生日問題の近似 sqrt(2 × N × ln(1/(1-p)))（N は文字数の長さ乗）で、衝突確率が1%に達する個数を出すと次のとおりである。

文字数 長さ ビット数 1%で衝突する個数
64 21 126.0 約 1.31 × 10^18
62 21 125.0 約 9.37 × 10^17
36 21 108.6 約 3.11 × 10^15
10 21 69.8 約 4.48 × 10^9

数字だけの21桁は、約45億個で衝突確率が1%に届く。文字の種類を減らしたら、そのぶん長さを足す必要がある。

実装するときの注意

  • byte % 文字数 で文字を選ばない。64、32、16 のように256を割り切る文字数でない限り、先頭側の文字が出やすくなる。
  • マスクは「文字数-1 を覆う最小の 2^k - 1」にする。大きすぎるマスクは偏りこそ生まないが、捨てるバイトが増えて遅くなる。
  • 捨てる前提でバイトを多めに取る。nanoid は 1.6 × mask × 長さ ÷ 文字数 を1回分として取り、足りなければ取り直す。
  • 乱数源は暗号論的なものに限る。ハシトシステムのツールは crypto.getRandomValues が使えない環境では生成せず、その旨を表示する。Math.random に黙って切り替えると、偏りを消しても予測できる ID になる。
  • アルファベットに同じ文字を2回入れない。ツールは重複を落としてから使う。重複があると、その文字だけ2倍出やすくなる。

まとめ

  • 1バイトを % 62 で文字にすると、先頭8文字が他の1.25倍出る。36文字なら先頭4文字が約1.14倍になる。
  • nanoid の customAlphabet は、0〜(文字数-1) を覆う最小のマスクで切り出し、範囲外を捨てて偏りを消す。36文字なら256通り中112通りを捨てる。
  • 捨てる分を見込んで1回に ceil(1.6 × mask × 長さ ÷ 文字数) バイトを取る。36文字・21文字なら59バイトで、10万回中99.9%以上が1回で足りた。

コードは nanoid の GitHub リポジトリ で読める。ブラウザの乱数 API は MDN の Crypto.getRandomValues() を参照。ほかの ID 形式は「ULIDをブラウザで生成する」「UUID v7を自前実装する」「Snowflake ID を BigInt で分解する」も参照。

ツール: NanoID 生成（ハシトシステム）。長さと使う文字を選ぶと ID を生成し、その組み合わせで衝突確率が1%に達する個数と、指定した頻度で作り続けた場合の年数を出す。

プログラミング
#JavaScript #Node.js #Nano ID #乱数
Nano IDが%を使わない理由 — 36文字なら256中112を捨てる
https://blog.hashito.biz/2026/10/13/nanoid-modulo-bias-mask-rejection-step-36-chars/
著者
hashito
作成日
2026年10月13日
著作権

このバージョンはその範囲に入るのか

依存の話でいちばん間違えやすいのは ^1.2.3 や ~1.2.3 がどこまでを許すかです（^0.2.3 のようにメジャーが 0 のときは規則が変わります）。範囲とバージョンを貼ると、下限・上限に展開したうえで一致・不一致とその理由を表示するsemver 範囲判定ツールを置いています。ブラウザの中だけで動き、入力はどこにも送信しません。