怎样做网站软件,网站开发面试都会问什么问题,好多钱网站,国家城乡住房建设部网站首页引言
为什么散列函数采用取模运算#xff1f;又为什么取模运算的被取模数最好是素数#xff1f;素数是如何在取模运算中很好的规避冲突的#xff1f;
这些问题可能困扰诸多程序员很久了。我们总是说素数可以更好的避免冲突#xff0c;但总是对各种长篇大论的分析望而却步…引言
为什么散列函数采用取模运算又为什么取模运算的被取模数最好是素数素数是如何在取模运算中很好的规避冲突的
这些问题可能困扰诸多程序员很久了。我们总是说素数可以更好的避免冲突但总是对各种长篇大论的分析望而却步。
这篇文章是我在学习散列时针对素数在哈希函数中的如何成功避免大量冲突的原因总结。
尽可能言简意赅地描述为什么素数那么香。
一、结论
素数能够在取模运算中避免冲突并不是一个数学定律而且能够避免冲突也不是绝对的。
从规律上来看如果待存储的数列间隔恰好是是被取模数的因子大小那么合数要比素数更容易呈现周期性的取模重复。
这仅仅是一个规律目前数学家也无法对这一规律进行严格定义毕竟这个规律也并不是绝对的。
二、演示
我们通过一个简单的例子来印证一下上面的这个规律 从规律上来看如果待存储的数列间隔恰好是是被取模数的因子大小那么合数要比素数更容易呈现周期性的取模重复。 这个规律不是绝对的。下面选取了一个合数和一个素数待存储的数列间隔为 2 或 3请仔细观察规律
1 数列间隔 3 (3是12的因子) 数列3437404346495255582mod 11 14710258033mod 12 1014710147104mod 13 811147100365mod 14 6912147101326 数列间隔 2 (2是12、14的因子) 数列6769717375777981837mod 11 1357902468mod 12 791113579119mod 13 2468101213510mod 14 1113135791113
上图中数列代表待存储的整型数据一般在很多散列表如HashMap中都是通过对关键字进行某种变换得到一个整型数字比如如果key是字符串那么可以通过计算字符编码得到一个整数值。
mod 11 代表对11取模mod 12 代表对 12 取模依此类推。
我们分别选取了比较普通的两组数列分别对合数12、14和素数11、13进行取模运算可以看到取模结果重复的已经使用红色标记。
当数列间隔为 3 时由于 3 是 12 的因子因此可以看到表中 mod 12 的结果呈现了周期性的模冲突。而其他的 11、13、14并没有发现明显的冲突问题而是很好地分散了取模结果。
当数列间隔为 2 时由于 2 是 12、14 的因子因此可以看到表中 mod 12 和 mod 14 的结果都呈现了周期性的模冲突而 11、13 两个素数并没有发现明显的冲突问题而是很好地分散了取模结果。
总结
从实验结果可以清晰的看到素数要比合数更适合取模运算。在不知道数列间隔的情况下拥有较少因子的素数可以有效的避免规律性的取模冲突。
大家如果对我的结论感兴趣可以通过对比试验来尝试寻找数列间隔与因子之间的关系。
