关键词：剩余，同余定理，数论，hash
参考：
杨迎球，中国剩余定理与同余式组，[D]安顺学院数学与计算机科学系，2009.02.15
谈数论中的同余及其应用，衡水师专学报[D]，2002.03.1
同余理论的一些简单应用，肇庆学院学报，2013.03.28
《程序员的数学课》——极客时间
百度百科
历史
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？——《孙子算经》卷下二十六
释义：
有一堆东西不知道有多少数量。三件三件地数，就会剩下两件；五件五件地数，剩下三件；七件七件地数，剩下两件。问：这堆东西共有多少件？
解题如下：
条件：除3余2，除7余2，
公倍数=3*7=21
21*1+2=23
证：
23/5=4余3
日常应用：
今天星期5，30天后星期几？
30/7余2
周五+2天=周日
那么问题来了！某个数尽除7，余数会大于或等于7吗？
答案是当然不会！
故而我们提炼出：余数在除数的范围内
同余定理
再思考一个问题：今天是本月1日，周日，本月30天，那么有几个星期日呢？
每7天（加上本天基础天1+7），是一个周循环
8、15、22、29
8/7余1
15/7余1
22/7余1
29/7余1
以上这种情况被前人归纳为，同余定理
哈希(Hash)
在现在“区块链”泛滥的时代，你应该不陌生这种加密算法吧；
哈希本质是“将任意⻓度的输入，通过哈希算法，压缩为某一固定⻓度的输出”
发现没？和求余是一样一样的
比个喻：
问：有30W条数据，想快速读写，一个物理储存空间放不下。怎么办？
答：放多个物理空间
问：但数据是连续的，则需要对空间进行关联
答：我们可以设计一个散列函数，并实现哈希表的结构
散列函数：本质就是个检索和关联；
f（x）=y mod size
在这个公式中，Y表示等待被转换的数值，而size表示有限存储空间的大小，mod表示取余操作。通过余数，你就能将任何数值，转换为有限范围内的一个数值，然后根据这个新的数值，来确定将数据存放在何处。
具像说明：
我们可以通过记录标号模30的余数，指定某条数据存放在哪个空间。这个时候，我们的公式
就变成了这样:
f（x）=y mod 30
然后我们就可以把 1、31、61、91、121这些数放在第1个空间中，以此类推，30、60、90、120…放在第30个空间中
这样 我们就能在30的范围内检索出30w条数据。
网友评论