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

五分钟搞懂计算机中的余数以及余数和哈希函数请点击输入图片描述 最多 18 字 计算机中的余数说到余数 我想大家肯定不陌生 我们的生活中有很多余数应用的场景 比如 我们知道一星期一共 7 天 每年 12 个月 那为啥 12 月之后就是 1 月呢 周天之后就是周一呢 其背后都多余数影子 再比如 我们经常要

大家好,欢迎来到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 个可用空间里。

余数和哈希函数的关系

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

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

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/92824.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信