Hash Function
- 2023.07.26
- Hash Function Modulo
Modulo
除數（Division）的選擇：質數
為什麼除數藥選擇質數呢？
我們選擇 modulo 作為 hash function
是想藉此將 整數 Z 映射到 [0, 1, 2, …, N – 1] （N 為除數）
假設 被除數 M 和 除數 N 有最大公因數 k
$$ M = km, N = kn; m, n, k \in \mathbb{N} $$
\begin{align}
M \ \% \ N = r & \Rightarrow M = Nq + r \\
& \Rightarrow km = knq + r \\
& \Rightarrow m = nq + \frac{r}{k}
\end{align}
因為 m 和 nq 都是整數
所以 r / k = m – nq 也會是整數
則 r ∈ [0, k, 2 * k, …, (n – 1) * k]
沒辦法平均的映射至整個 [0, 1, 2, …, N – 1]
所以除數才會選擇質數
Last Updated on 2023/08/16 by A1go
