【简单】只用2GB内存在20亿个整数中找到出现次数最多的数－Java

分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.BigDataAndSpaceRestriction; /** * 只用2GB内存在20亿个整数中找到出现次数最多的数 * * 【题目】 * 有一个包含20亿个全是32位整数的大文件在其中找到出现次数最多的数。 * * 【要求】 * 内存限制为2GB。 * * 【难度】 * 简单 * * 【解答】 * 想要在很多整数中找到出现次数最多的数通常的做法是使用哈希表对出现的每一个数做词频统计哈希表的key是某一个整数 * value是这个数出现的次数。就本题来说一共有20亿个数哪怕只是一个数出现了20亿次用32位的整数也可以表示其出现的次数 * 而不会产生溢出所以哈希表的key需要占用4Bvalue也是4B。那么哈希表的一条记录(key,value)需要占用8B当哈希表记录数 * 为2亿个时需要至少1.6GB的内存。 * * 但如果20亿个数中不同的数超过2亿种最极端的情况是20亿个数都不同那么在哈希表中可能需要产生20亿条记录这样内存会不够 * 用所以一次性用哈希表统计20亿个数的办法是有很大风险的。 * * 解决办法是把包含20亿个数的大文件用哈希函数分成16个小文件根据哈希函数的性质同一种数不可能被哈希到不同的小文件上同 * 时每个小文件中不同的数一定不会大于2亿种假设哈希函数足够好。然后对每一个小文件用哈希表来统计其中每种数出现的次数这 * 样我们就得到了16个小文件中各自出现次数最多的数还有各自的次数统计。接下来只要选出这16个小文件各自的第一名中谁出现的次 * 数最多即可。 * * 把一个大的集合通过哈希函数分配到多台机器中或者分配到多个文件里这种技巧是处理大数据面试题时最常用的技巧之一。但是到 * 底分配到多少台机器、分配到多少文件在解题时一定要确定下来。可能是在与面试官沟通的过程中由面试官指定也可能是根据具体 * 的限制来确定比如本题确定分成16个文件就是根据内存限制2GB的条件来确定的。 * * author Created by LiveEveryDay */ public class Only2GBMemIn2BillionIntegers { }