模拟评估

当需要了解一个哈希函数的分辨能力和冲突概率时,直接的数学分析可能存在一定难度。这个时候,可以通过计算机模拟冲突来评估该哈希函数。

随机选择\(N\)个不同的给定值\(k\),经过哈希函数映射后,得到\(D^*\)种不同状态的技术统计\(C=\{c_i| i \in [1,{D^*}]\}\)。显然\(N=\sum \limits_{i=1}^{D^*} c_i \)。

\[ {\lambda^*} = \sum_{i=1}^{D^*} (\frac{c_i}{N}\cdot\frac{c_i-1}{N}) \]

此时可以将\(D^*\)认为是该函数的分辨能力, \(\lambda^*\)认为是该函数的冲突概率。当随机选择的给定值\(k\)越多(即\(N\)越大),则模拟评估数值就越逼近目标值。

以之前所定义的哈希函数\(sqrt(k)\)为例,按照上述方法统计模拟分辨能力以及模拟冲突概率。

关键字取值范围分辨能力\(D^*\)冲突概率\(\lambda^*\)
[0,9]70.244444
[0,99]910.019192
[0,999]6750.002915
[0,9999]9790.001161
[0,99999]9980.001011
[0,999999]10000.001001
[0,9999999]10000.001000

由此表以及详细分析(包括每种压缩映像元素的冲突概率)可以得出结论:该哈希函数\(sqrt(k)\)与哈希函数\(f(k)=k\,mod\,1000\)是条件等价函数。