专业网站建设品牌，十四年专业建站经验，服务6000+客户--广州京杭网络

免费热线：400-683-0016      微信咨询  |  联系我们

• 网站首页
• 网站建设
• 短视频
• 网站推广
• 网站模板
• 客户案例
• 资讯动态
• 关于我们

mysql哈希查询,80亿个整数中找到出现次数最多的数_数据库

当前位置：网站建设 > 技术支持

mysql哈希查询，80亿个整数中找到出现次数最多的数？

需求：

使用2G的内存，找出80亿个数字中出现最多的数字。

假设：

整数为4字节（2^32=4G），即最大40多亿。所有的数字有80亿个。所有数字在硬盘中，本身不会占用内存。所用内存为2G多一些，例如有限的变量。但多出的内存和2G相比可以忽略不计。

设计：

80亿的计数可以用4字节保存（2^32=4G）。因为如果计数超过一半，则表明该数字一定是出现最多的。2G的内存约可以保存5亿多数字的计数（2G/4=512M）。

也就是说，将2G的内存分成单位为4字节的数组，可以一次获得0～5亿多之间出现最多的数字。

步骤：

顺序扫描80亿个数字，忽略0～512M之外的数字，每个数字N的出现个数累加存放在第N个数组元素中。最后将最出现最多的数字及其次数保存起来，出现并列第一时，只保存第一个数字。如果过程中某数字出现个数超过40亿，则直接结束。再次扫描所有数字，此次忽略512M～1G之外的数字。每个数字N的出现个数累加存放在第N-512M个数组元素中。本轮所获得的数字的出现个数和第一轮结果比较，保存较大的那个。由于整数取值范围为4G，所以最多扫描8次后即可获得最终结果。

问题：

如果整数长度为8字节，则需要扫描约300多亿次（2^64/512M=2^40）。所以此算法并不适用于8字节的整数。

讨论：

当数字足够多，且数字取值范围足够大时，以有限内存获取出现次数最多的数字几乎是不可能的。因为数字的取值范围极大，且数字极多，任何哈希或其它分片的算法都有可能出现极端情况，导致分片数据过多而无法一次性导入内存计算。除非我们预先知道部分数字规律，否则考虑到效率，应该只会要求得到近似结果。