程序员的数学基础课 余数（自我提升第7天）
菜鸟今天补第三天没看完的，感觉这个程序员的数学基础课，到目前为止都写得还不错，那么话不多说，直接上
程序员的数学基础课
基础思想二知识点：
余数
没错，这一节主要就是讲余数，那么可能有人就会问，这小学就知道的余数，难道很神奇？
1、余数因为除数，而被规定在一定的范围
就拿我们平时的星期来说，不管今天是多少年多少月多少号，你只要知道一个固定的年月日是星期几，就可以通过相隔天数除以7，推断出今天是星期几，而得到的结果一直都在0~6之间，这就是余数在日常生活中的应用。
2、同余定理就是用于将数据分类
就像不管是多少年多少月多少号，只要是星期一，都表示我们该上班了（这里不考虑节假日）；还有就是奇数和偶数的分类，就是将一个数除以2，看其余数。而这就是同余定理，即相同的余数在数学世界里，代表了他们属于同一类。
说到这里，大家又会有疑惑，这和程序有什么关系？我怎么没感觉我程序里用到了余数？其实这就是，当局者迷的一种感觉，其实我们写的代码很多时候都会用到余数，不信？那我就举两个例子！
1、数据库的分页，或者你自己获取到的数据库内容，进行分页显示
例如：你现在从后台获取到了67条数据，如果你同时渲染这67条数据（含较大的图片），那我感觉，可能别人等个10几秒，估计就直接把你的网站给X了，这时余数的作用来了，比如，你一次只渲染10条，那么你肯定会毫不犹豫的67/10=6…7，那么你的数据就会分6次加载，而最后7条则是凑一页不够多出来的数据，会再渲染一次，但是只加7条，如果没有余数，你是怎么知道最后一页该加还是不该加？是加多少？而且你可以完全肯定最后一页的渲染时间一定比前面短（如果数据完全一样大），因为余数的范围被限定在了小于10大于-1之间。
2、哈希（hash）
[这里菜鸟就直接拿极客时间的老师的话了，因为菜鸟这个算法和数据结构，咳咳咳，一言难尽，反正就是不太会，所以在补中，大家可以关注我的拼客专栏，全部都会讲的]
哈希（Hash）你应该不陌生，在每个编程语言中，都会有对应的哈希函数。哈希有的时候也会被翻译为散列，简单来说，它就是将任意长度的输入，通过哈希算法，压缩为某一固定长度的输出。这话听着是不是有点耳熟？我们上面的求余过程不就是在做这事儿吗？
举个例子，假如你想要快速读写 100 万条数据记录，要达到高速地存取，最理想的情况当然是开辟一个连续的空间存放这些数据，这样就可以减少寻址的时间。但是由于条件的限制，我们并没有能够容纳 100 万条记录的连续地址空间，这个时候该怎么办呢？
我们可以考察一下，看看系统是否可以提供若干个较小的连续空间，而每个空间又能存放一定数量的记录。比如我们找到了 100 个较小的连续空间，也就是说，这些空间彼此之间是被分隔开来的，但是内部是连续的，并足以容纳 1 万条记录连续存放，那么我们就可以使用余数和同余定理来设计一个散列函数，并实现哈希表的结构。
下面是我想到的一种方法：
在这个公式中，x 表示等待被转换的数值，而 size 表示有限存储空间的大小，mod 表示取余操作。通过余数，你就能将任何数值，转换为有限范围内的一个数值，然后根据这个新的数值，来确定将数据存放在何处。
具体来说，我们可以通过记录标号模 100 的余数，指定某条记录存放在哪个空间。这个时候，我们的公式就变成了这样：
假设有两条记录，它们的记录标号分别是 1 和 101。我们把这些模 100 之后余数都是 1的，存放到第 1 个可用空间里。以此类推，将余数为 2 的 2、102、202 等，存放到第 2个可用空间，将 100、200、300 等存放到第 100 个可用空间里。
这样，我们就可以根据求余的快速数字变化，对数据进行分组，并把它们存放到不同的地址空间里。而求余操作本身非常简单，因此几乎不会增加寻址时间。
除此之外，为了增加数据散列的随机程度，我们还可以在公式中加入一个较大的随机数MAX，于是，上面的公式就可以写成这样：
我们假设随机数 MAX 是 590199，那么我们针对标号为 1 的记录进行重新计算，最后的计算结果就是 0，而针对标号 101 的记录，如果随机数 MAX 取 627901，对应的结果应该是2。这样先前被分配到空间 1 的两条记录，在新的计算公式作用下，就会被分配到不同的可用空间中。
你可以尝试记录 2 和 102，或者记录 100 和 200，最后应该也是同样的情况。你会发现，使用了 MAX 这个随机数之后，被分配到同一个空间中的记录就更加“随机”，更适合需要将数据重新洗牌的应用场景，比如加密算法、MapReduce 中的数据分发、记录的高速查询和定位等等。
让我以加密算法为例，在这里面引入 MAX 随机数就可以增强加密算法的保密程度，是不是很厉害？举个例子，比如说我们要加密一组三位数，那我们设定一个这样的加密规则：
- 先对每个三位数的个、十和百位数，都加上一个较大的随机数。
- 然后将每位上的数都除以 7，用所得的余数代替原有的个、十、百位数；
- 最后将第一位和第三位交换。
这就是一个基本的加密变换过程。
假如说，我们要加密数字 625，根据刚才的规则，我们来试试。假设随机数我选择590127。那百、十和个位分别加上这个随机数，就变成了 590133，590129，590132。然后，三位分别除以 7 求余后得到 5，1，4。最终，我们可以得到加密后的数字就是415。因为加密的人知道加密的规则、求余所用的除数 7、除法的商、以及所引入的随机数590127，所以当拿到 415 的时候，加密者就可以算出原始的数据是 625。