一、概述
MOD(取模)运算配合质数的特性,可以实现一种简单的哈希算法。
二、基于的定理
在理解如何实现mod哈希前应当了解一些数学的定理:
1.x mod y = z ,实际上是x除以y的余数y的意思;
2.假设 x / y = z ,即 x 是被除数,y 是除数,z 是商;
3.除法规定:除数不能为0,但是被除数可以;
4.mod运算与/规则是一致的,只不过最后的结果z,mod是余数;
5.质数是只能被0和自身整除的数;
三、算法
x mod y = z
如果理解用到的基本数学定理,那么这个算法是相当容易理解的;
假设y是一个质数,那么x mod y的结果z,永远都等于+-y,至于y是正数还是负数,则取决于x是正数还是负数;
四、运用
1.可用于简单的哈希表,寻找一个足够大的质数作为除数y,可以实现长度为y的哈希表;
2.可用于简单的负载均衡算法,例如利用访问流量时间戳作为被除数x,可以实现把不同流量分发到不同的负载点;