从40亿中产生一个不存在的数

问题描述

给定一个文件，包含40亿个非负整数，请你设计一个算法，产生一个不在该文件中的数字。假设你只有1GB内存。

问题分析

40亿整数,在java中，用int存储的话，大概需要40亿✖️4B,大约16G。现在只有1GB，很明显是不够的，可以考虑位存储，可以减少到原空间的1/32，大约0.5G,满足题目给定的内存要求

实现思路

使用位存储，使用整数对应位置的bit位为1,代表元素存在，为0,代表元素不存在。遍历这40亿个数，将存在的数对应的bit设置为1。对bit数组再次进行遍历，返回为0的第一个下标的对应数字即是40亿中不存在的数。

问题进阶

给定一个文件，包含40亿个非负整数，请你设计一个算法，产生一个不在该文件中的数字。假设你只有10MB内存。

问题分析

只有10MB来存储，很明显使用位存储是不够的。位存储需要0.5GB=500MB的空间。我们可以采用分块思想。一共需要500MB空间，我们只有10MB空间，可以分成50个块，一般向上取整至2的整数次幂，即64个块，40亿大概是4G，即4*2^ 30,总共2的32次方个数，分成64个块，每块2^32/64 = 2 ^26个数，我们可以通过两次遍历来找到不存在的数。

实现思路

首先，我们申请一个长度为64的整形数组，用于统计64个块中元素的个数。遍历这40亿个数，，判断其属于哪个块，可以通过数值大小%64来实现，统计结束后，找到一个数组元素小于2 ^26的对应块。在申请存储一个块元素所需要的bit空间，即2 ^ 26*4B/32 = 2 ^23B =8MB，小于10MB可以实现，遍历40亿个数，将属于该块的元素对应的bit为设置为1。对bit数组再次进行遍历，返回为0的第一个下标的对应数字即是40亿中不存在的数。

20亿个整数中找到出现次数最多的数

问题描述

在20亿个整数中找到出现次数最多的数，假设你只有2GB内存。

问题分析

20亿整数大概是2G=22^30 = 2 ^31，int类型可以存储，不会溢出。可以使map计数，键表示数字，值表示数字出现的次数，这样一个键值对需要8B的存储空间。20亿个数字需要大概2G8B=16GB。只有2GB的情况下，可以进行分块，分为8个块，依次进行处理。

实现思路

将20亿个数字映射为8个块，可以使用哈希函数(模8)来实现。统计每个块中元素的数量，找出最大值，比较八个块的最大值，找到20亿个数中的最大值返回。

总结

海量数据的处理方法通常只有三种，首先是特殊情况，让我们寻找海量数据中的最值，或者前几个最值，可以使用堆来实现，之后可以考虑bit位存储，整数存储对应下标，可以节省到1/32的存储空间，如果内存依旧不够，可以考虑分块，具体的分多少块，可以取需要内存和现有内存的比值，分块可以采用顺序分块，也可以采用哈希分块。