# Knuth's Multiplicative Hash
[[ドナルド・クヌース|ドナルド・クヌース (Donald Ervin Knuth)]] による [[完全ハッシュ関数と最小完全ハッシュ関数#最小完全ハッシュ関数|最小完全ハッシュ関数]]
## 関数
> $
> f(n) = (n \times \rm{PRIME}) \mod \rm{MAX} + 1
> $
^6f8585
- $\rm{PRIME}$ ... 3 以上の素数
- $\rm{MAX}$ ... 2 のべき乗であるような整数
- 集合 $A = \{x \in \mathbb{Z} \mid 1 \leq x \leq \rm{MAX} \}$ とすると
- 関数 $f$ は $A$ から $A$ への変換写像
## Mathematical proof
[Knuth multiplicative hash が最小完全ハッシュ関数であることの証明 | メルカリエンジニアリング](https://engineering.mercari.com/blog/entry/2017-08-29-115047/)
合わせて
[multiplicative hash は完全ではない（証明付） #Python - Qiita](https://qiita.com/epsilon/items/aeefa085417b7134f793#%E3%83%A1%E3%83%AB%E3%82%AB%E3%83%AA%E3%81%AE%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E9%96%A2%E6%95%B0)
- メルカリのハッシュ関数は完全.
- multiplicative hash を実装することにより, 完全ではない（インデックスが衝突する）例を示した.
- multiplicative hash は, その定義に含まれるビットシフト演算と用いる変数の制約が, メルカリのハッシュ関数と異なる.
## Implementation
- [GitHub - denostack/inthash: Efficient integer hashing library using Knuth's multiplicative method for Javascript and Typescript, perfect for obfuscating sequential numbers.](https://github.com/denostack/inthash?tab=readme-ov-file)
- [GitHub - jenssegers/optimus: 🤖 Id obfuscation based on Knuth's multiplicative hashing method for PHP.](https://github.com/jenssegers/optimus)
## Go による実装
^6a307a
```go
package main
import (
"fmt"
)
// 32 ビット環境向けの Knuth 推奨の乗数
const PRIME = 2654435761
// 2^5 = 32
const MAX = 32
// Knuth's multiplicative hash
func f(n int) int {
return (n*PRIME)%MAX + 1
}
func main() {
for n := 0; n < 10; n++ {
fmt.Printf("%d => %d\n", n, f(n))
}
}
```
結果
```
0 => 1
1 => 18
2 => 3
3 => 20
4 => 5
5 => 22
6 => 7
7 => 24
8 => 9
9 => 26
```
ランダムっぽい。
## 逆関数
最小完全ハッシュ関数は全単射なので逆関数が存在する。
> $
> invF(v) = (v - 1) \times \rm PRIME^{-1} \mod MAX
> $
^da67d9
- $\rm PRIME^{-1}$ ^7c8846
- $\rm PRIME$ の $-1$ 乗（逆数）ではなくて、 $\mod \rm MAX$ における逆元
- 呼ぶなら "prime inverse" ?
- $\rm MAX$ は $2$ のべき乗だから、 $\rm PRIME$ と $\rm MAX$ は互いに素
- [[拡張ユークリッドの互除法]] が使える
- 👉 [[mod 逆元を求める]]
- 法 $\rm MAX$ が素数でないので [[フェルマーの小定理]] は使えない
### 求め方
$f(n)$ を $v$ とすると
$
\begin{aligned}
v &= (n \times \rm{PRIME}) \mod \rm{MAX} + 1 \\
v - 1 &= (n \times \rm{PRIME}) \mod \rm{MAX}
\end{aligned}
$
$v - 1$ は任意の整数を $\rm MAX$ で割った余りで、 $n \times \rm PRIME$ を $\rm MAX$ で割った余りと等しい
$
\begin{aligned}
n \times \rm{PRIME} &\equiv v - 1 \pmod{\rm{MAX}} \\
n &\equiv (v - 1) \times \rm{PRIME}^{-1} \pmod{\rm{MAX}}
\end{aligned}
$
ここから上記の逆関数の式になる
### Go による実装
```go
func invF(v int) int {
primeInv := modInv(PRIME, MAX)
n := (v - 1) * primeInv % MAX
return n
}
```
^8a17d8
`modInv` は [[mod 逆元を求める]] を参照
## 全体
```go
package main
import (
"fmt"
)
// 32 ビット環境向けの Knuth 推奨の乗数
const PRIME = 2654435761
// 2^3 = 8
const MAX = 8
// Knuth's Multiplicative Hash
func f(n int) int {
return (n*PRIME)%MAX + 1
}
func invF(v int) int {
primeInv := modInv(PRIME, MAX)
n := (v - 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() {
for n := 0; n < 8; n++ {
v := f(n)
inv := invF(v)
fmt.Printf("%d => %d => %d\n", n, v, inv)
}
}
```
結果
```
0 => 1 => 0
1 => 2 => 1
2 => 3 => 2
3 => 4 => 3
4 => 5 => 4
5 => 6 => 5
6 => 7 => 6
7 => 8 => 7
```
^6959fa