五分钟搞懂计算机中的余数以及余数和哈希函数

大家好，欢迎来到IT知识分享网。

请点击输入图片描述（最多18字）

计算机中的余数

说到余数，我想大家肯定不陌生，我们的生活中有很多余数应用的场景。

比如，我们知道一星期一共7天，每年12个月。那为啥12月之后就是1月呢？周天之后就是周一呢？其背后都多余数影子。

再比如，我们经常要对Web信息进行分页。如果你要展示 1123 条数据，每页 10 条，那该怎么计算总共的页数呢？

你肯定是拿 1123 除以 10，最后得到商是 112，余数是 3，所以你的总页数就是 112+1=113，而最后的余数就是多出来，凑不够一页的数据。

我们可以看出来，余数总是在一个固定的范围内。

哈希函数

哈希（Hash）你应该不陌生，Hash（哈希），又称“散列”。

哈希函数（Hash Function）是指能将任意大小的输入（Key）映射到固定大小的哈希值（Hash Value）的函数。Key可以是固定长度如int类型，也可以是任意字符串，甚至可以是经纬度或者高维的向量。

在每个编程语言中，都会有对应的哈希函数。哈希有的时候也会被翻译为散列，简单来说，它就是将任意长度的输入，通过哈希算法，压缩为某一固定长度的输出。这话听着是不是有点耳熟？我们上面的求余过程不就是在做这事儿吗？

举个例子，假如你想要快速读写 100 万条数据记录，要达到高速地存取，最理想的情况当然是开辟一个连续的空间存放这些数据，这样就可以减少寻址的时间。但是由于条件的限制，我们并没有能够容纳 100 万条记录的连续地址空间，这个时候该怎么办呢？

我们可以考察一下，看看系统是否可以提供若干个较小的连续空间，而每个空间又能存放一定数量的记录。比如我们找到了 100 个较小的连续空间，也就是说，这些空间彼此之间是被分隔开来的，但是内部是连续的，并足以容纳 1 万条记录连续存放，那么我们就可以使用余数和同余定理来设计一个散列函数，并实现哈希表的结构。

在这个公式中，x 表示等待被转换的数值，而 size 表示有限存储空间的大小，mod 表示取余操作。通过余数，你就能将任何数值，转换为有限范围内的一个数值，然后根据这个新的数值，来确定将数据存放在何处。

具体来说，我们可以通过记录标号模 100 的余数，指定某条记录存放在哪个空间。这个时候，我们的公式就变成了这样

undefined

假设有两条记录，它们的记录标号分别是 1 和 101。我们把这些模 100 之后余数都是 1 的，存放到第 1 个可用空间里。以此类推，将余数为 2 的 2、102、202 等，存放到第 2 个可用空间，将 100、200、300 等存放到第 100 个可用空间里。

余数和哈希函数的关系

我们知道了余数和哈希函数，余数总是在一个固定的范围内。而哈希函数将任意长度的输入，通过哈希算法，压缩为某一固定长度的输出。

即通过余数，你就能将任何数值，转换为有限范围内的一个数值，然后根据这个新的数值，来确定将数据存放在何处。