# 数値をランダムっぽい桁数固定の文字列に可逆変換する
## 要件
- `id` の代わりに `code` を使いたい
- `id` は auto increment
- URL に含めるので推測を困難にしたい
- 推測不可能である必要はない
- `code`
- ユニークな値
- ランダムっぽい文字列
- ユーザーが紙に記載またはシステムに入力する可能性がある
- 見分けにくい文字を除外する
- 除外する文字
- `I` , `O` , `0` , `1`
- 使える文字（32 文字）
- `ABCDEFGHJKLMNPQRSTUVWXYZ23456789`
- 桁数固定
- とりあえず 4 桁を想定
- プライバシーへの配慮は不要
- `code` で対象のデータを取得したい
- パフォーマンスを重視したい
## 一般的な解法
### UUID を利用する
- `123e4567-e89b-12d3-a456-426614174000`
- 重複の可能性はないものとして扱える
- 4 桁という要件に合わない
### がんばって生成する
- ランダムな文字列を生成
- 重複した場合は再生成
- データが増えるにつれパフォーマンスが悪化する
## Knuth's Multiplicative Hash の利用
最小完全ハッシュ関数を使ってみるというアイデア。
👉 [[Knuth's Multiplicative Hash]]
👉 [[完全ハッシュ関数と最小完全ハッシュ関数]]
### 完全ハッシュ関数
![[完全ハッシュ関数と最小完全ハッシュ関数#完全ハッシュ関数]]
### 最小完全ハッシュ関数
![[完全ハッシュ関数と最小完全ハッシュ関数#^b525c9]]
![[Hash_table_4_1_0_0_0_0_0_LL.svg|400]]
## Knuth's Multiplicative Hash
[[ドナルド・クヌース|ドナルド・クヌース (Donald Ervin Knuth)]] による最小完全ハッシュ関数。
![[Knuth's Multiplicative Hash#関数]]
- 大昔に近いことをやった時にはここのアイデアがなかった
- 今（2024 年）調べたらメルカリでこのアプローチを使っていた
- [Knuth multiplicative hash が最小完全ハッシュ関数であることの証明 | メルカリエンジニアリング](https://engineering.mercari.com/blog/entry/2017-08-29-115047/)
- 2017 年の記事
- 正しくは Knuth's Multiplicative Hash だと思う
- 情報セキュリティの用途では使えない
- [暗号学的ハッシュ関数](https://ja.wikipedia.org/wiki/暗号学的ハッシュ関数) を使うこと
👉 [[Knuth's Multiplicative Hash]]
## 定義と実装
### 定義
![[Knuth's Multiplicative Hash#^6f8585]]
### Go による実装
とりあえず、 $\rm MAX$ は $2$ のべき乗にしておく。
![[Knuth's Multiplicative Hash#Go による実装]]
## 逆関数
生成結果から元の数値に戻したい。
最小完全ハッシュ関数は全単射なので逆関数が存在する。
### 定義
![[Knuth's Multiplicative Hash#^da67d9]]
![[Knuth's Multiplicative Hash#^7c8846]]
### 求め方（初心者 ver）
![[Knuth's Multiplicative Hash#求め方]]
### 拡張ユークリッドの互除法
$\rm PRIME$ と $\rm MAX$ は互いに素なので、拡張ユークリッドの互助法を利用して $\mathrm{PRIME}$ の逆元を求める。
まずは、拡張ユークリッドの互助法についての説明。
👉 [[拡張ユークリッドの互除法]]
![[拡張ユークリッドの互除法#定義]]
Go による実装（再帰 ver）
![[拡張ユークリッドの互除法#再帰 ver]]
### 逆元を求める
`extGCD` を利用して逆元を求める。
![[拡張ユークリッドの互除法#逆元を求める]]
`x` が負数になったら法（この例では `13`）を足して正数にするのがポイント。
### Go による逆関数の実装
上記を踏まえて、Knuth's Multiplicative Hash の逆関数を実装する。
👉 [[mod 逆元を求める]]
![[Knuth's Multiplicative Hash#^8a17d8]]
`PRIME` の逆元 `primeInv` を求めるために `modInv` を実装する。
- 下記の`movInv` は非再帰 ver （ループで処理）
- Go は再帰が遅い
- Goランタイムはスタックサイズのデフォルトが小さい
- スタックサイズの最適化を行わない
- ちなみに、末尾最適化もない
- Stack Overflow が発生する
![[mod 逆元を求める#非再帰 ver]]
出力してみる。
```go
func main() {
for n := 0; n < 10; n++ {
v := f(n)
inv := invF(v)
fmt.Printf("%d => %2d => %d\n", n, v, inv)
}
}
```
```
0 => 1 => 0
1 => 18 => 1
2 => 3 => 2
3 => 20 => 3
4 => 5 => 4
5 => 22 => 5
6 => 7 => 6
7 => 24 => 7
8 => 9 => 8
9 => 26 => 9
```
元の値を取得できている。
## 利点
- auto increment された id から即座に `code` を生成できる
- データ量に応じて桁数を自由に指定できる
- 可逆変換を実現しつつランダムっぽい文字列になる
- 連番を比較しても気付かれない
- `code` から `id` に戻せるので、 `id` を primary key とした通常運用ができる
- `code` から `id` へは外部（ DB など）へのアクセスなしに変換できる
## 注意点
秘密情報なしに復号できてしまうので、情報セキュリティの用途では使えない。
## RDBMS での利用
### 問題
INSERT 文を発行して auto increment された `id` を取得後に `code` を UPDATE する必要がある。
- 新規登録時にクエリを 2 回発行する必要がある
- `code` に `NOT NULL` 制約を付けられない
### 解決案
- `PRIME` は固定
- 桁数が決まっていれば `MAX` は事前計算できる
- `MAX` が事前計算できれば `PRIME` の逆元も事前計算できる
`encode` と `decode` をストアドファンクションとして用意しておくことが可能。
ロジックが分散されるので、web 開発ではストアドファンクションの利用が避けられるが、この場合はドメインロジックというよりも汎用ユーティリティ関数なので OK でお願いします！
（強いて言えば、使える文字種がドメイン依存と言えなくはないけど…）
例えば、MySQL の場合
- `CREATE FUNCTION` で `encode` と `decode` のストアドファンクションを作成しておく
- ネーミングはよく考えて
- 案
- ストアドプロシージャーで INSERT と `code` の UPDATE をまとめる
- クエリは 2 回分だけど、アプリケーションから DB へのアクセスは 1 回
- AWS Lambda や Cloud Function と RDBMS の組み合わせに優しい
- こうなるとストアドプロシージャーのパラメーターがドメイン依存になるのでつらい
- AFTER INSERT のトリガーを使う
- これはこれでつらい
- どちらにせよ、`code` に `NOT NULL` 制約を付けられない…
- ちなみに、 CREATE TABLE で DEFAULT にストアドファンクションは指定できない
- 組み込みのファンクションは使える
何の成果も！！得られませんでした！！
`id` と `code` の相互変換ができるので、そもそも `code` を保存する必要はないのだけど、トラブル対応の時を考えると保存しておきたい気持ち。
（一手間の差ではあるけれど）
なので、ガンガン新規作成されるようなテーブルでの利用ははばかられる。
（NoSQL の出番？）
## N を超えない 2 のべき乗の計算
最後に、 `MAX` の値を決定するために必要となる計算について。
👉 [[N を超えない 2 のべき乗の計算]]
![[N を超えない 2 のべき乗の計算#N を超えない 2 のべき乗の計算]]
## コード全体
ここまでの材料を組み合わせて
```go
package main
import (
"fmt"
"math/bits"
"strings"
)
// 32 ビット環境向けの Knuth 推奨の乗数
const prime = 2654435761
type Encoder struct {
chars []string
digit int
min int
max int // 2 の累乗
}
func NewEncoder(digit int) *Encoder {
return &Encoder{
// 見分けがつきにくいのでI, O, 1, 0 を除外した 32 文字
chars: strings.Split("ABCDEFGHJKLMNPQRSTUVWXYZ23456789", ""),
digit: digit,
min: min(digit), // 4 桁の場合は 32768
max: max(digit), // 4 桁の場合は 524288
}
}
func (enc *Encoder) Max() int {
return enc.max
}
func (enc *Encoder) Encode(n int) string {
if enc.max <= n { // max と同じでもダメなはず
panic("out of range")
}
// 桁数が足りるように min を足す
h := hash(n, enc.max) + enc.min
str := ""
for 0 < h {
str = enc.chars[h%32] + str
h /= 32
}
// 桁が逆順になってるけど本質的な問題ではないので気にしない
return str
}
func (enc *Encoder) Decode(str string) int {
chars := strings.Join(enc.chars, "")
h := 0
for _, c := range str {
// Encode 時に桁が逆順になってるので注意
h = h*32 + strings.Index(chars, string(c))
}
return unhash(h-enc.min, enc.max)
}
func min(digit int) int {
// 32 は 5bit
return int(1 << (5 * (digit - 1)))
}
// digit が決まっていれば事前計算できる
func max(digit int) int {
// 32 は 5bit
// 桁数未満になる min を除く
m := int(1<<(5*(digit))-1) - min(digit)
// m を超えない 2 の累乗
return largestPowerOfTwoLessThanOrEqual(m)
}
// n を超えない最大の 2 の累乗を計算する
func largestPowerOfTwoLessThanOrEqual(n int) int {
if n == 0 {
return 0
}
// 最も高いビットの位置を見つける
pos := bits.Len(uint(n)) - 1
// その位置にあるビットが表す 2 の累乗を計算する
return 1 << int(pos)
}
// Knuth's Multiplicative Hash
func hash(n int, max int) int {
return (n*prime)%max + 1
}
// Knuth's Multiplicative Hash の逆関数
func unhash(h int, max int) int {
primeInv := modInv(prime, max) // 事前計算できる（4 桁の場合は 208721）
n := (h - 1) * primeInv % max
return n
}
// 法 m での a の逆元を求める関数
// 拡張ユークリッドの互除法を利用
func modInv(a int, m int) int {
var b, u, v = m, 1, 0
for b != 0 {
t := a / b
a -= t * b
a, b = b, a
u -= t * v
u, v = v, u
}
u %= m
if u < 0 {
u += m
}
return u
}
func main() {
// 4 桁のランダムっぽい文字列を生成したいとする
enc := NewEncoder(4)
var n int
for n = 0; n < 100; n++ {
code := enc.Encode(n)
hashValue := hash(n, enc.max) + enc.min
decorded := enc.Decode(code)
fmt.Printf("%2d => %s (%6d) => %2d\n", n, code, hashValue, decorded)
}
}
```
桁が決まっていれば事前計算できる値もある。
結果
```
0 => BAAB ( 32769) => 0
1 => R8PU (522674) => 1
2 => Q65D (488291) => 2
3 => P5JW (453908) => 3
4 => N3YF (419525) => 4
5 => M2DY (385142) => 5
6 => LYTH (350759) => 6
7 => KW82 (316376) => 7
8 => JVNK (281993) => 8
9 => HT34 (247610) => 9
10 => GSHM (213227) => 10
11 => FQW6 (178844) => 11
12 => EPCP (144461) => 12
13 => DMR8 (110078) => 13
14 => CK7R ( 75695) => 14
15 => BJMA ( 41312) => 15
16 => SG2T (531217) => 16
17 => RFGC (496834) => 17
18 => QDVV (462451) => 18
19 => PCBE (428068) => 19
20 => NAQX (393685) => 20
21 => L86G (359302) => 21
22 => K7KZ (324919) => 22
23 => J5ZJ (290536) => 23
24 => H4E3 (256153) => 24
25 => G2UL (221770) => 25
26 => FY95 (187387) => 26
27 => EXPN (153004) => 27
28 => DV47 (118621) => 28
29 => CUJQ ( 84238) => 29
30 => BSX9 ( 49855) => 30
31 => SRDS (539760) => 31
32 => RPTB (505377) => 32
33 => QM8U (470994) => 33
34 => PLND (436611) => 34
35 => NJ3W (402228) => 35
36 => MHHF (367845) => 36
37 => LFWY (333462) => 37
38 => KECH (299079) => 38
39 => JCR2 (264696) => 39
40 => HA7K (230313) => 40
41 => F9L4 (195930) => 41
42 => E72M (161547) => 42
43 => D6F6 (127164) => 43
44 => C4VP ( 92781) => 44
45 => B3A8 ( 58398) => 45
46 => SZQR (548303) => 46
47 => RX6A (513920) => 47
48 => QWKT (479537) => 48
49 => PUZC (445154) => 49
50 => NTEV (410771) => 50
51 => MRUE (376388) => 51
52 => LP9X (342005) => 52
53 => KNPG (307622) => 53
54 => JL4Z (273239) => 54
55 => HKJJ (238856) => 55
56 => GHX3 (204473) => 56
57 => FGDL (170090) => 57
58 => EES5 (135707) => 58
59 => DC8N (101324) => 59
60 => CBM7 ( 66941) => 60
61 => S93Q (556846) => 61
62 => R8G9 (522463) => 62
63 => Q6WS (488080) => 63
64 => P5CB (453697) => 64
65 => N3RU (419314) => 65
66 => MZ7D (384931) => 66
67 => LYLW (350548) => 67
68 => KW2F (316165) => 68
69 => JVFY (281782) => 69
70 => HTVH (247399) => 70
71 => GSA2 (213016) => 71
72 => FQQK (178633) => 72
73 => EN54 (144250) => 73
74 => DMKM (109867) => 74
75 => CKY6 ( 75484) => 75
76 => BJEP ( 41101) => 76
77 => SGT8 (531006) => 77
78 => RE9R (496623) => 78
79 => QDPA (462240) => 79
80 => PB4T (427857) => 80
81 => NAJC (393474) => 81
82 => L8XV (359091) => 82
83 => K7DE (324708) => 83
84 => J5SX (290325) => 84
85 => H38G (255942) => 85
86 => G2MZ (221559) => 86
87 => FY3J (187176) => 87
88 => EXG3 (152793) => 88
89 => DVWL (118410) => 89
90 => CUB5 ( 84027) => 90
91 => BSRN ( 49644) => 91
92 => SQ67 (539549) => 92
93 => RPLQ (505166) => 93
94 => QMZ9 (470783) => 94
95 => PLFS (436400) => 95
96 => NJVB (402017) => 96
97 => MHAU (367634) => 97
98 => LFQD (333251) => 98
99 => KD5W (298868) => 99
```