Edited at

hashアルゴリズムとハッシュ値の長さ一覧


「ハッシュ値の衝突」や「データ改ざん防止」など、複数のハッシュ・アルゴリムを組み合わせるためにハッシュ値の長さと速度の一覧が欲しい



TL;DR(このハッシュ関数は何文字?)

この記事はハッシュ関数の出力結果を桁数ごとにまとめたものです。

ハッシュ関数の戻り値の「バイト長」、つまり「ハッシュ値」や「メッセージダイジェスト」で出力される文字の「長さをまとめたもの」がなかったので、長さごとにアルゴリズムを一覧にまとめてみました。また、各アルゴリズムの PHP7.2.6 での計算速度も記載しています。

ハッシュ・アルゴリズム(ハッシュ関数)が何文字の 16 進数で返してくるかの事前確認や処理速度の目安にご利用ください。


🐒 ハッシュ関数の基本やハッシュ値の長さの具体的な用途に関しては下記 TS;DR をご覧ください。


ちなみに「n バイトって HEX 文字列で最大何文字だっけ?」という場合は、単純に n を2倍してください。(1バイト=0xFF、例:4バイト=HEXで8桁=FF FF FF FF



ハッシュ・アルゴリズムの一覧とビット長一覧(ハッシュ値の長さ一覧)

すべて同じメッセージ(文字列)をハッシュ化したものなのに、ビット長(ハッシュ値の長さ)が同じでも、値がまったく異なることに注目ください。



  • 環境:macOS HighSierra (OSX 10.13.6), PHP 7.2.6 (cli), MacBookPro Early 2015, 2.7GHz Corei5, Mem 8GB 1867MHz DDR3



  • ハッシュするメッセージ:「Hello Qiita!」

  • ループ回数:1,000,000 回(100 万回)

  • 速度:上記ループの 10 回ぶんの平均値

  • 並び順:桁数の少ない順 → 速い順

  • メッセージダイジェストは横スクロールをさけるため 8 桁(4バイト)ごとのブロックに分けています

  • 測定のソースコード @ Paiza.IO


8 桁のハッシュ値

アルゴリズム
バイト長
速度
ハッシュ値

fnv132
4 Byte
0.157887 sec
b04649f6

fnv1a32
4 Byte
0.157962 sec
129b42dc

adler32
4 Byte
0.165301 sec
1bf5042e

crc32
4 Byte
0.169681 sec
dd54ff69

crc32b
4 Byte
0.172050 sec
ad6adc0d

joaat
4 Byte
0.173369 sec
2cbbf315


16 桁のハッシュ値

アルゴリズム
バイト長
速度
ハッシュ値

fnv164
8 Byte
0.168120 sec

97bfaffd 885daad6

fnv1a64
8 Byte
0.176964 sec

07c72cc2 7b5f8b5c


32 桁のハッシュ値

アルゴリズム
バイト長
速度
ハッシュ値

md4
16 Byte
0.284748 sec

e2500f3f 1eb028a4 563ca3d4 35028996

md5
16 Byte
0.337097 sec

7c414ef7 535afff2 1e05a36b 1cfc9000

tiger128,3
16 Byte
0.341727 sec

60bd4df9 e039716f 07c9ecd4 4c203d34

tiger128,4
16 Byte
0.397596 sec

7c20d9b5 d9e79da7 b5241a08 a353018a

ripemd128
16 Byte
0.553369 sec

0ff7eaf1 38540680 8e92e642 28a79243

haval128,3
16 Byte
0.954699 sec

a8fe5c62 4c856077 d07db6bc 9a7f1275

haval128,4
16 Byte
1.027350 sec

b5ee64c0 6a003d55 65108356 08c6a34c

haval128,5
16 Byte
1.197690 sec

ad189ff3 183c9cfe cf5a39e3 45ba95f8

md2
16 Byte
4.762099 sec

8cd3c9c1 f1079b15 639ddab1 2227d400


40 桁のハッシュ値

アルゴリズム
バイト長
速度
ハッシュ値

sha1
20 Byte
0.348829 sec

5d8793ae d96d808a b6af8e47 5ce244e8
a604e478

tiger160,3
20 Byte
0.367638 sec

60bd4df9 e039716f 07c9ecd4 4c203d34
6f07e46a

tiger160,4
20 Byte
0.399170 sec

7c20d9b5 d9e79da7 b5241a08 a353018a
bf178a02

ripemd160
20 Byte
0.694799 sec

99a6c172 52ae4e64 e8d22853 c54ee2ad
44089160

haval160,3
20 Byte
0.900242 sec

aba140dc e20ac7a2 615053de 4336e343
37a49b46

haval160,4
20 Byte
1.033398 sec

6bc4fecd c33d5d21 14c695ff f449d333
58f3030d

haval160,5
20 Byte
1.197252 sec

d87a41cb 73469426 42faf2ae 7d62e81a
eba5dcc6


48 桁のハッシュ値

アルゴリズム
バイト長
速度
ハッシュ値

tiger192,3
24 Byte
0.394713 sec

60bd4df9 e039716f 07c9ecd4 4c203d34
6f07e46a 9c308ef7

tiger192,4
24 Byte
0.410200 sec

7c20d9b5 d9e79da7 b5241a08 a353018a
bf178a02 0a74f3fb

haval192,3
24 Byte
0.874294 sec

e2b0c018 6b1cc119 0eebe1be 9d61953d
2dd78ba4 8136086c

haval192,4
24 Byte
1.031765 sec

7540fa22 a5714124 cf942e1b 31a890b9
bb59d58c e5a61157

haval192,5
24 Byte
1.211350 sec

e4a6b10a d8286eaf 8cb3f225 950c2f93
b6fdab8c 601626c8


56 桁のハッシュ値

アルゴリズム
バイト長
速度
ハッシュ値

sha224
28 Byte
0.713225 sec

d72d6ef7 0a788b3e 7f720b5d 88f20a13
bf161c31 b260fd34 6573094d

sha3-224
28 Byte
0.817025 sec

e833eab3 4fbefbe8 9e44dcf1 d4ea9990
10981761 22f51708 df9cd9d0

sha512/224
28 Byte
0.825188 sec

e205b15d 16eda0ce e195d210 73edca14
a69198e9 0070b9b0 09f7cb16

haval224,3
28 Byte
0.842655 sec

a69049ca 88565098 a6f5e2bc adb22980
e59da983 9a779b63 c214e019

haval224,4
28 Byte
1.045480 sec

090b25d0 e8a0f5ef ecf6b683 5be72fe5
6913b34e 2d086922 3b1ac5d1

haval224,5
28 Byte
1.209415 sec

5343b4b1 a16119c5 dcd7726e 53128841
fecb7607 88e9008f 6c6f2cb6


64 桁のハッシュ値

アルゴリズム
バイト長
速度
ハッシュ値

ripemd256
32 Byte
0.574046 sec

e0fe9c49 b1a59fae 47096909 83e62829
4887b161 5722a62c 2c4187be 816b058d

sha256
32 Byte
0.668654 sec

e863d36c 24ada694 fa77454b 33e8f9b9
545d372a ae251e87 79fc25df 16943fed

sha3-256
32 Byte
0.824698 sec

cedaea23 33478d77 bc9ed3e3 3303f455
85af1917 4a451ce9 3029fedc dd4d1ecb

sha512/256
32 Byte
0.833001 sec

aaa2e875 112de9b6 1744d4a0 ae757e40
cd12008a 0f3948fb 7c42a8cd 48c361b8

haval256,3
32 Byte
0.845439 sec

5f788c8a 5359387b acf7bf60 ff4dd08d
e7176205 a0aae1ce 4f485b40 126c0d2f

haval256,4
32 Byte
1.048196 sec

4ebb9e6f a6c045b0 cbba419e f06ac973
b2fd4914 f746e142 bb6b840f bd836158

haval256,5
32 Byte
1.218753 sec

c99614ae a2985f43 f480d029 bcb7974b
f5aface5 8730c9d6 f3141a67 58270431

gost
32 Byte
1.828385 sec

667f4328 0ff9e0a5 9c15de57 022becf3
cd1a48f8 d37a165c 87576b6f 814fa482

gost-crypto
32 Byte
1.849877 sec

7ebf0f97 0f1246b6 aea110d7 32cbcdfd
b0169cf1 7336bae7 814e99f1 8abfbd21

snefru
32 Byte
2.841073 sec

ad081810 0ab15234 b13b8d09 ad0c519a
35469221 adbf8c5f a71594ca f7dfddc2

snefru256
32 Byte
2.850217 sec

ad081810 0ab15234 b13b8d09 ad0c519a
35469221 adbf8c5f a71594ca f7dfddc2


80 桁のハッシュ値

アルゴリズム
バイト長
速度
ハッシュ値

ripemd320
40 Byte
0.725499 sec

6d152e32 fee2b979 024b8cff e416c898
16032680 779f7c3a 93c9aa26 35441245
8d4a9010 ad8fdfa5


96 桁のハッシュ値

アルゴリズム
バイト長
速度
ハッシュ値

sha384
48 Byte
0.831855 sec

b10497cf 49601678 4d8413a4 662983a8
dc4ac470 039ea755 d5ec985f 1aab04ee
26dc3d67 71bbe404 75ea7d13 5a97ba58

sha3-384
48 Byte
0.835068 sec

e83e54ee 323dafb5 ca2d800f d479e1cc
94502362 93d5ad74 36228519 aa657ea3
d1da8bb6 2d07035d ec1ece2f 428ec8dc


128 桁のハッシュ値

アルゴリズム
バイト長
速度
ハッシュ値

sha3-512
64 Byte
0.851400 sec

9d1aaed0 79bac194 6a5fbafb 4285ec5b
dcf0053a 9e005590 46884a14 8f28fcb9
02441b49 cb3a8277 5834a244 4dd183ed
a36cee90 0f5662f8 2353fae7 e7111740

sha512
64 Byte
0.860255 sec

cac9036c 1dd3652f c550e99a 4ec2b066
d69d6a40 a369bc85 e3078960 e6f26012
4138f5d0 f4e9a6e0 47dfb833 c9dd9b33
76d02d49 be37de26 dd6234d4 e79cc09e

whirlpool
64 Byte
1.041927 sec

488c6cd6 eccb5348 8a7c7617 8c89d514
16b8eb2b 88a30b79 71f1f176 70e27659
fc477cd9 6ade86e4 b6176c5e f2f67068
89606786 4ce15443 eff90733 fd4fcf4c



TS;DR


最速のDBキー検索を求めて with SQLite3


ハッシュ値の衝突は別のアルゴリズムでは衝突しない(限りなく)


衝突のイメージ

// 値が異なる $a と $b

$a = 'xxxxx..1..xxxxx' // 長ったらしい値 a
$b = 'xxxxx..0..xxxxx' // 長ったらしい値 b

hash('md5', $a) === hash('md5', $b) // true, 偶然にも衝突が発生!
hash('md2', $a) === hash('md2', $b) // false, アルゴリズムが異なると衝突しない(可能性が高い)


古くはダウンロード・ページなどでファイルの改ざんや破損がないかを比べるのに使われていたり、身近なところではアクセス・トークンの作成や、みんな大好き Git のコミットID にも使われている「ハッシュ関数」。

近年話題のブロックチェーンなどでは要かなめの関数とも言えるなど、今後もさまざまな場面で活躍が期待される関数です。

ハッシュ関数の基本と特徴



ハッシュ関数には4つの大きな特徴があります。


  1. アルゴリズムと引数が同じ場合は、同じ結果(ハッシュ値)が返ってくる

  2. ハッシュ値から元の値(引数の値)の算出は難しい(逆算できない)

  3. ハッシュ値から元の値(引数の値)の予測は難しい(ちょっとした違いでも結果は大きく異なる ※)

  4. ハッシュ値は固定長の数値で返ってくる(一般的に n 桁の HEX 文字列)

辞書攻撃による予測の場合除く。

つまり、「結果からオリジナルの予測が難しい」のと「同じ結果が得られる」のが一番の特徴です。

以下は "beef" という文字列をハッシュ値にした例です。引数が同じ場合は結果も変わらず、「塩を 1 足す」だけで結果が大きく変わることに注意してください。


ハッシュ・ド・ビーフの例


引数が同じ

$ # 粗挽き牛ミンチ

$ php -r 'echo hash("md5", "beef"), PHP_EOL;'
34902903de8d4fee8e6afe868982f0dd
$
$ # 粗挽き牛ミンチ(コマンドの言語が違っても同じアルゴリズムと引数なら同じミンチ肉)
$ echo -n 'beef' | openssl md5
34902903de8d4fee8e6afe868982f0dd


引数を少し変化させる

$ # 粗挽き牛ミンチ+ 1 の塩入り

$ php -r '$salt=1; echo hash("md5", "beef" . $salt), PHP_EOL;'
30017279d6a5bac241e764eeed261dd8
$
$ # 同じレシピで、違う言語のコマンド(bash)
$ salt=1; echo -n 'beef'$salt | openssl md5
30017279d6a5bac241e764eeed261dd8


アルゴリズムを変えてみる

$ # 絹ごし牛ミンチ

$ php -r 'echo hash("sha512", "beef"), PHP_EOL;'
8cd8bb0cef938ef9cd054c2c2cb965e83310ab5c197cb5fc8f35892a44c1a028bac9e1bcd6248580fa2739cc96074885ea3ee116ef35c2d8f6124270aeff50b7
$
$ # 絹ごし牛ミンチ(コマンドの言語が違っても同じアルゴリズムと引数なら同じミンチ肉)
$ echo -n 'beef' | openssl sha512
8cd8bb0cef938ef9cd054c2c2cb965e83310ab5c197cb5fc8f35892a44c1a028bac9e1bcd6248580fa2739cc96074885ea3ee116ef35c2d8f6124270aeff50b7
$
$ # 絹ごし牛ミンチ+ 1g の塩入り
$ php -r '$salt=1; echo hash("sha512", "beef" . $salt), PHP_EOL;'
a528829f370819123ad3fb04d8066b77ec79ce6eddad07e5b2c925bbd9b2e699e73428d23315875c29b45500b8c767262cf5546e33974e4f7a6102abd1bb045e
$
$ # 絹ごし牛ミンチ+ 1g の塩入り(コックが違っても同じレシピなら同じ味)
$ salt=1; echo -n 'beef'$salt | openssl sha512
a528829f370819123ad3fb04d8066b77ec79ce6eddad07e5b2c925bbd9b2e699e73428d23315875c29b45500b8c767262cf5546e33974e4f7a6102abd1bb045e

この特徴により、パスワードなどハッシュ化して保存することで流出したとしても元のパスワードがわからないといった用途に使われます。

しかし、「引数が同じ場合は戻り値も同じ」という特徴により、別途パスワード・リストなどがあった場合はハッシュ値もわかってしまいます。つまり「辞書攻撃に使える」ということなので「ハッシュ化したから安心」というものではありません

ハッシュ関数や暗号関数を触っていくと「salt」という言葉が出てきます。これは、各々のデータに加えるランダムな数値や文字列のことです。上の例で言えば beef に加えた salt=1 です。

料理でいう「塩加減」のように「同じ具材でも塩の加減1つで味が変わるため、毎回調整が必要で加減も秘伝」と言ったイメージが近いのですが、「塩土化」つまり土地の占領者が「土地を使えないよう土に塩を撒いて使えなくする」から来ている説もあるようです。

そして、「salt」(塩)は基本的に個々のデータに加えるのですが、全体に加える「pepper」(胡椒)と呼ばれる値もあります。

ユーザ名
パスワード

user1
passw0rdA

user2
passw0rdA

上記はプレーンなパスワードの状態。偶然にも user1user2 のパスワードが同じです。上記だと流出時にバレバレなので、以下のような処理をします。

スクリーンショット 2019-09-08 22.46.20.png

ユーザ名
ソルト
パスワード

user1
saltA
7915e17989dcbb1d2132c1d207ef9e1d

user2
saltB
5ee508cb664f91000826933e626cd5df

実際には saltA などの単純な文字列でなくランダムな数値や文字列が使われたり、hash('sha256', hash('sha256', $value)) と言ったような、二重・三重にハッシュ化させたりします。

いずれにしても、引数に $salt$pepper という絶対公開しない値を引数に加えることで、予測を難しくさせているのです。

もちろん salt 値や pepper 値が流出してしまうと意味がありません。シオシオのパーです。つまり、秘密鍵と同じくらい扱いには気をつけないといけないので、「ハッシュ化しても安心できない」とわかると思います。

しかし、データのセキュリティ用途ばかりに目を向けるのではなく、「処理」に目を向けると「数値で返ってくる」という特徴を活かすことができます。

王道の使い方は改ざんの検知です。1バイトでも違いがあるとハッシュ値の結果は大きく変化します。この特徴により、大量の文書(データ)であっても1文字の改ざんでも変化を検知できるのです。逆に言えば、「ハッシュ値が同じであれば、データに変更はない」という使い方にも利用できます。

また、「引数がどれだけ長くても、ハッシュ値は固定長の数値」であることもメリットです。つまり、データがそれ以上増えないということです。

例えば、Web サイトのページ遷移せんいのパターンを固定長の ID にすることもできます。


ページせん移をID化する

$list_url_visited=[

'http://hoge.com/p1',
'http://hoge.com/p6',
'http://hoge.com/p4',
...
];

asort($list_url_visited); //配列をソート
$string = implode(' ', $list_url_visited); //配列を文字列に結合
$id_visited = hash('md5', $string); //文字列をハッシュ化


この行動パターンに ID を振れるメリットは、機械学習における特徴量などにも応用できます。

つまり、ハッシュ関数の特徴をよく理解すれば、アイデア次第でさまざまな活用方法がある関数でもあるのです。




そんな便利なハッシュ関数ですが、「メッセージダイジェストのコリジョン」(異なる入力値なのにハッシュ値が同じという「衝突」)が悩みのタネです。つまり、「改ざんされているのにハッシュ値が変わらない」状態です。

しかし、上記記事のように特定のアルゴリズムでハッシュ値が衝突しても、アルゴリズムを変えると衝突しません

衝突の検証実証(MD5,SHA1)


MD5 の衝突


検証実証withPHP

<?php

// MD5 で衝突するサンプルデータ
$str1 = '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518'
. 'afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2';
// ↑ ↑
$str2 = '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518'
. 'afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2';
// ↑ ↑

// バイナリに変換
$bin1 = hex2bin(trim($str1));
$bin2 = hex2bin(trim($str2));

// 衝突させる
$algo = 'md5';
$md5_1 = hash($algo, $bin1);
$md5_2 = hash($algo, $bin2);
echo ( $md5_1 === $md5_2 ) ? '衝突しました' : '衝突していません', PHP_EOL;

// 別のアルゴリズムで確認
$algo = 'sha1';
$sha1_1 = hash($algo, $bin1);
$sha1_2 = hash($algo, $bin2);
echo ( $sha1_1 === $sha1_2 ) ? '衝突しました' : '衝突していません', PHP_EOL;

/* 出力結果 */
// 衝突しました
// 衝突していません



SHA1 の衝突

SHA1 の衝突はデータサイズが大きすぎるので paiza.IO で動作サンプルを作れませんでした。簡単なスクリプトとローカルで実行してみた結果結果を載せます。


検証スクリプト

<?php

$url_pdf1='https://shattered.io/static/shattered-1.pdf';
$url_pdf2='https://shattered.io/static/shattered-2.pdf';

$algo = 'sha1'; //衝突する
echo hash($algo, file_get_contents($url_pdf1)), PHP_EOL;
echo hash($algo, file_get_contents($url_pdf2)), PHP_EOL;

$algo = 'md5'; //衝突しない
echo hash($algo, file_get_contents($url_pdf1)), PHP_EOL;
echo hash($algo, file_get_contents($url_pdf2)), PHP_EOL;
exit



実行結果

$ php -a

Interactive shell

php > $url_pdf1='https://shattered.io/static/shattered-1.pdf';
php > $url_pdf2='https://shattered.io/static/shattered-2.pdf';
php >
php > $algo = 'sha1'; //衝突する
php > echo hash($algo, file_get_contents($url_pdf1)), PHP_EOL;
38762cf7f55934b34d179ae6a4c80cadccbb7f0a
php > echo hash($algo, file_get_contents($url_pdf2)), PHP_EOL;
38762cf7f55934b34d179ae6a4c80cadccbb7f0a
php >
php > $algo = 'md5'; //衝突しない
php > echo hash($algo, file_get_contents($url_pdf1)), PHP_EOL;
ee4aa52b139d925f8d8884402b0a750c
php > echo hash($algo, file_get_contents($url_pdf2)), PHP_EOL;
5bd9d8cabc46041579a311230539b8d1
php > exit



このことから、「セキュリティの強度」や「同一性の確実度」を高めるには、以下の2点を同時に提供するのが効果的とわかりました。


  1. 複雑な計算が必要な、長いハッシュ値を提供する(SHA256 など)

  2. 異なるアルゴリズムのハッシュ値も提供する(SHA256MD5 など)

OS のイメージ・ダウンロードで SHA-1MD5 などの複数ハッシュ値を提供しているのは「SHA-1 ハッシュが使えない人のため」なのかと思っていましたが、どうやらそれだけではないようです。というのも、SHA-1MD5 の両方といった複数のアルゴリズムのハッシュ結果を「単一の改ざん」で衝突させるのは難しいからです。

「ってか MD2 なんてあったんだ!」と知ったと同時に、「MD2 って MD5 と同じ 16 バイト長(128bit= 32 桁の HEX 文字列)なんだ」と気づきました。

いまや CSV のように小馬鹿にされる MD5 ですが、SHA-1, SHA-256 などのメジャーどころ以外に、どんなアルゴリズムがあるのか気になりました。PHP の hash_algos() 関数 でサポートしているハッシュ・アルゴリズム一覧を出したところ「こんなにハッシュ関数(のアルゴリズム)ってあるの?!」とビックリ。各々のアルゴリズムの仕組みを把握する気力さえ失せる勢い。(失せた)

そこで、各々のアルゴリズムはどれくらいの長さの値を返すのか調べ、一覧にしてみました。(ついでに速度も)


長さを知ったところで何?

ですよねー。実は、私は SQLite31INTEGER PRIMARY KEY フェチなのです。

さらで SQL 文も書けないくせに、「SQLite3」と聞かれれば「主キー♥️」と答えるくらいです。

これは、SQLite3 の場合は DB をキー検索する際に「DB の PRIMARY キーを INTEGER 型にすると最もパフォーマンスが良い」というのを盲信しとるのです。

元々 SQLite3 では rowid で検索するのが一番速いとされます。SQLite における rowid とは DB で行(レコード)を作成すると自動で割り振られる 64 bit/8 byte の行番号(行 ID)です。(HEX 値で max 16桁)


Searching for a record with a specific rowid, or for all records with rowids within a specified range is around twice as fast as a similar search made by specifying any other PRIMARY KEY or indexed value.

(「ROWIDs and the INTEGER PRIMARY KEY | SQL As Understood By SQLite」@ SQLite.org より)

特定の rawid でのレコード検索、もしくは指定範囲内のすべてのレコードを複数の rawid で検索する場合、PRIMARY KEY やインデックスを使った場合に比べて2倍近い速さの速度が得られます。(筆者訳)


この時、テーブルの主キーが rowid と同じであれば、主キーでも同じ速度が得られるのです。

厳密には、テーブル作成時に主キーの列を INTEGER PRIMARY KEY で定義し、テーブルが1次元(1主キー1行構成の DB)だった場合に各行の主キーがrowid のエイリアスとなる仕様を使います。(INTEGER PRIMARY KEY でなく INT PRIMARY KEY で宣言するとダメなので注意)


If a table has the primary key that consists of one column, and that column defined as INTEGER, exactly INTEGER in any cases, such as, INTEGER, integer, etc., then this primary key column becomes an alias for the rowid column.

表(テーブル)の主キーが1つの列で構成され、かつその主キーが大文字・小文字関係なく INTEGERINTEGER, integer, INTteger, etc.)と定義されていた場合、この主キーは rowid 列のエイリアスになります。(筆者訳)


この仕様により「主キー名」から「rowid」への変換ステップが省略され、テーブルの主キーが rowid と同じ扱いになるので速い、という塩梅です。元々はバグだったそうなのですが下位互換のため残され、仕様となったそうです。

となると、SQLite3 で扱えるキー(rawid)の最大長である 8 バイトの数値(64 ビット。文字でいうと 16 文字の HEX 文字列)をいかに作るかが問題になります。

やはり、王道の自動連番が一番楽で、キーの衝突もなく効率的です。基本設計がしっかりしていれば、これが一番だと思います。

しかし、(私の)ユーザにとっては変なバイアスがかかることがわかりました。

というのも、歴史的事情でデータの ID を DB の主キーと同じにしているというダメちん仕様のため、当然の結果として「情報の ID 番号が時系列に並ぶ」、つまり登録順に並ぶのです。すると(私の)ユーザは無意識に内容の優劣を決めてしまうのです。

「ID が小さい → 古参の情報」「ID が大きい → 新参の情報」といった具合です。そのため、(私のようなオッチャン層は特に) ID が小さい方が質が良い・有益であると思い込んでしまうのです。観測すると、実は打ちやすい・覚えやすいだけで、番号に質は無関係だったのですが。

かといって、対オッチャン対策のためにランダムな ID の対応表を別途作るのも面倒なのです。また、すでに現行データの ID は周知されているので入れ替えは容易ではありません。

そこで、近々起こりうるであろうデータの棚卸しに備えてハッシュ関数を使って ID を固定長にできないかと模索をはじめました。


Hash now, don't you cry

PHP の場合、fnv1 系(fnv164 もしくは fnv1a64)のアルゴリズム一発で 8 バイト(64 bit, 16 桁の HEX 文字列)のハッシュが作れます。

そのため、古いキーを単純にハッシュ化して再登録すれば楽に移行できます。

$key_prime_new = hash('fnv164', $key_prime_old);

しかし、現在この記事で話題にしている DB が扱っているデータは登録後の変更はありません。いや、むしろ変更してはいけないものなのです。

しかし、自由度の高い設計であるためか、自分の独断と都合により何故か勝手に値を変えちゃう一部の層(上流やオッチャン層)がありました。その層に弱い上司からコッソリと指示を受けるたび、バックアップから元に戻す作業のイタチごっこが定期的に発生していました。

これではいつかは盛大なポカをやりかねません。仕組みとしてのポカよけが必要と感じ、もう少し工夫をしたいなと思いました。

昨今の行政の改ざん問題でも提案されている文書のハッシュ化を ID として取り入れたいと考えたのです。

つまり、イメージではこういうことです。

// 旧IDでデータ取得

$value = fetchValueFromDB($key_prime_old);
// データ → ハッシュ化(16進)→ 10進 → 整数
$key_prime_new = (integer) hexdec(hash('fnv164', $value));

先の「要オッチャン対策 DB」は「ユーザが測定したデータの値と同じ値のものを DB から探し、関連情報(ヒットした行のデータ)を返す」用途に使われています。ピピピッピッと打つか、ピッとバーコードを読み込むと、ポッとデータが表示されるシンプルなものです。

つまり、ユーザ側(クライアント側)で測定したデータをハッシュ化して渡し、 DB(サーバー側)は受け取ったキーを検索すれば速度改善・改ざん防止・オッチャン対策の良いとこ取りになります。DB もシンプルに実装・構成できます。

ここで、もし1つ前の登録データのキーもハッシュ化してフィールドに内包(列を追加)すれば、ブロックチェーンに近い考え方になりますよね。そもそも SQLite なので、同期されたデータは各クライアント(ユーザ)のローカルにありますし。

さて、この方法でテストしたところ、今のところ1億件ちょっとの既存データで衝突もなく問題なさそうなのですが、1つのアルゴリズムに依存したくないという気持ちもありました。そう、ハッシュ値の衝突が怖いのです。

そもそも、この程度(10 年で 1〜2 億件程度)のデータ量であれば、SQLite3 の 1844京6744兆737億件以上も使える 8 バイト(64ビット)のキーをそのまま使うのはもったいないのです。大は小を兼ねるとは言え、貸し倉庫クラスなのにデズニーランド・クラスのスペースを使うようなものです。

十分な年数に耐えつつ、衝突に関しては鳩の巣原理(鳩の数より巣箱の数が少ないと、1つ以上の巣箱で衝突が起きる原理)は少なくとも網羅できるバイトの長さを検討した結果、最長 4 バイト長(= 42.9 億個)のキーとしました。

そして、先の「衝突しても別のアルゴリズムだと衝突しない(可能性が高い)」屁理屈を取り入れて、「4 バイトの A 型ハッシュ値 + 4 バイトの B 型ハッシュ値 = 8 バイトのキー」を作ってみたいと思いました。

具体的には 4 バイト長のハッシュ・アルゴリズムである crc32fnv132 の2つをあわせて以下のような Primeキーの算出を考えました。

$key_prime_hex = hash('fnv132', $value) . hash('crc32', $value);

(厳密に言うと CRC-32 はハッシュではなくチェックサムなのですが、計算コストをケチってしまいました。crc32, fnv132 @ Wikipedia)

先の fnv164(8 バイト長のアルゴリズム)単体と比べて2倍くらい速くなるのですが、移行のための一括登録のデータ量が 500 万件を越えたあたりから、むしろ遅くなりました。アルゴリズムの組み合わせにもよると思いますが、アルゴリズムによっては初期化に原因がありそうです。

しかし、本番データは一旦ダンプして主キーを整形して、新規挿入するデータとしてあらかじめ用意しておき、一括 INSERT させる予定なので問題はないと思います。

また、実際の用途では新規登録時の速度はさほど必要とされておらず、登録頻度も高くありません。むしろ登録より日々の引き出し時の速度が速くなったことのほうが改善感があって良いと思います。

いまのところ、このアルゴリズムの組み合わせタイプでも手元の2億件弱のサンプル・データで衝突は発生していません。

ただ、確信は持てていないません。近々 Wikipedia のデータをぶっ込んで検証してみたいと思います。

また、上記の測定速度を見てもわかるように PHP7 の場合 100 万回ぶん回して 0.n 秒の差です。PHP8 だとさらに倍近く速くなるので、微々たる差だと思います。

そのため、CRC-32 のチェックサムを使うよりは Git のコミット ID のように SHA-256 や SHA-512 などのハッシュ値の頭 4 バイトを使うのがよろしいかと思われます。(私はそうすることにしました。この仕組みが認められるころには PHP8 もリリースされると思うし。一部で都合が悪いらしく採用されなさげ、ってか仕事も辞めちゃったので実装することもなさげです


イメージとしてはこんな感じ

$len   = 8; //4バイトのHEX文字列長

$value = fetchValueFromDB($key_prime_old);
$hash1 = substr(hash('sha256', $value), 0, $len);
$hash2 = substr(hash('sha512', $value), 0, $len);

// 8バイトの主キー
$key_prine_new = (integer) hexdec($hash1 . $hash2);


(え? 「もう、KVS でいいじゃん」って?ま、まぁ…ねぇ、、、枯れた技術を好むのも歳なんですかねぇ)





  1. SQLite3とは、著作権の発生しないオープンソースのデータベース管理システムです。名前からわかるように SQL の構文でデータにアクセスでき、リレーショナル・データベース(RDBMS)の1つです。
     特徴としては「本体も動作も軽量である」ことと「サーバーを立てずに使えること」があります。サーバー型でないため、複数ユーザーや複数アプリからの同時利用には向かないのですが、アプリごとにデータを保存する場合に威力を発揮するタイプです。
     モバイル・アプリやゲームなどのダウンロードやキャッシュ・データであったり、macOS の場合は標準でインストールされており、Spotlight などの検索用の DB としても使われています。(sqlite3 -help で確認可能)
     リアルタイムに激しく変動するデータでない場合、アプリ起動時に本艦となるサーバーからデータ・ベースをダウンロードしてローカルに保存することで、ネットワークのトラフィックを減らしたり、オフラインで利用させたり、レスポンスの向上に使われたりする便利なプログラムです。
    関連リンク:SQLite @ Wikipedia 日本語