【Hash関数】できるだけ衝突率を上げずにIDを短くしたい

背景

• もともと一意のIDを別DBでも使いたかったが、該当のカラムの文字数に制限があり、そのまま使うことができなかった。

やりたいこと

• 英数字でできたIDををなるべく一意性を保ったまま短くしたい
  • 例: abc123DEF456fgh7890(19桁) => 123abc456DEF(12桁)

手順

1. Hash関数を用いて文字列から数値に変換する
2. その数値を62進数(a-z + A-Z + 0-9)に変換する

こうすることで、一意性をギリギリまで保ったまま短くできると考えた

使用環境・言語

• macOS Mojave 10.14.5
• node 10.19.0
• TypeScript 3.9.7

実装

1. ハッシュ関数の選定

ハッシュ関数と言っても、アルゴリズムや出力サイズ等、様々な種類が存在している。
=> 参考: hashアルゴリズムとハッシュ値の長さ一覧（＋ハッシュ関数の基本と応用）

今回、選定の肝となるのは「出力サイズ」。つまり、何bitの出力が得られるか。
bit数は最終的な桁数に直結するため、ちょうどいいサイズを探す必要がある。

先駆者の方が公開してくださっていたので、任意の長さの短いハッシュ関数を考える（短縮 URLなど） で実際に試しながら良さげなものを探してみる。

結果、今回は64bit出力のfnv1a64を使うことにした。
（64bitを62進数にすると11桁になる）

// 色々ライブラリがあったが、DL数が多いのを選んだ
import fnv1a from '@sindresorhus/fnv1a';

const inputStr = 'abc123DEF456fgh7890';
// jsのNumber型は2^53-1までしか表現できないのでBiGInt型の出力
const hash = fnv1a.bigInt(inputStr, { size: 64 });
console.log(hash); // 9465884287178377307n

2. 10進数を62進数に変換

10進数を2進数に変換するのと同様の方法で62進数に変換する。
62進数の一桁を0~9,a~z,A~Zにすることで、10進数を文字列に変換することができる。

const D_62 = BigInt(62);
const DIGIT_62 =
  '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
​
const decTo62 = (num: bigint): string => {
  const converted = [];
  while (num >= D_62) {
    const quotient = num / D_62;
    const remainder = Number(num % D_62);
    num = quotient;
    // インデックスはNumber型のみ
    // 64bitなら一度1/62にすれば2^53-1以下になる想定
    converted.unshift(DIGIT_62[remainder]);
  }
  converted.unshift(DIGIT_62[Number(num)]);
  return converted.join('');
};

const inputBigInt = BigInt(9465884287178377307);
console.log(decTo62(inputBigInt)); // INdk5tWOAhb

3. 完成したコード

import fnv1a from '@sindresorhus/fnv1a';
​
const D_62 = BigInt(62);
const DIGIT_62 =
  '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
​
const decTo62 = (num: bigint): string => {
  const converted = [];
  while (num >= D_62) {
    const quotient = num / D_62;
    const remainder = Number(num % D_62);
    num = quotient;
    converted.unshift(DIGIT_62[remainder]);
  }
  converted.unshift(DIGIT_62[Number(num)]);
  return converted.join('');
};
​
export const hash11 = (v: string): string => {
  /**
  * 文字列から一意の文字列11桁を生成する
  * 使用しているhashアルゴリズムはfnv1a、サイズは64bit
  * 衝突確率は 2^(bit数/2) 程度と言われているため
  * 2^(64/2) = 4294967296
  * 約42億分の1
  */

  const hash = fnv1a.bigInt(v, { size: 64 });
  return decTo62(hash);
}
​
// 使用例
const v = 'testRequestUID12345'
console.log(v, hash11(v)); // lhu2C5XktMT

4. まとめ

• 同じ入力に対しては毎回同じ文字列が返せる（短くなった分衝突率は上がってしまうが）
  • 「最初のxx桁を切り抜く」よりかはマシ
  • インクリメントで一意のIDを生成するほうが素直
• 要件にあったHash関数ライブラリを見つけるのに苦労した
  • 文字列を引数に取れるものが見つからない・・・

最後まで読んでいただき、ありがとうございました