当需要了解一个哈希函数的分辨能力和冲突概率时,直接的数学分析可能存在一定难度。这个时候,可以通过计算机模拟冲突来评估该哈希函数。
随机选择\(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] | 7 | 0.244444 |
[0,99] | 91 | 0.019192 |
[0,999] | 675 | 0.002915 |
[0,9999] | 979 | 0.001161 |
[0,99999] | 998 | 0.001011 |
[0,999999] | 1000 | 0.001001 |
[0,9999999] | 1000 | 0.001000 |
由此表以及详细分析(包括每种压缩映像元素的冲突概率)可以得出结论:该哈希函数\(sqrt(k)\)与哈希函数\(f(k)=k\,mod\,1000\)是条件等价函数。