在今天这个大数据时代，基本每一个公司都要面临处理大数据的问题，例如天猫的双十一节点击量，腾讯的上亿用户等，那么处理大数据问题就显得尤为重要。这一篇博客将选取几个较为经典的问题详解大数据问题，其中涉及的知识点有搜索树，哈希，堆，位图与布隆过滤器等。
这里只讲解思路以及解决方式，不会具体造轮子。
首先我们看到要找出出现次数最多的，首先想到的肯定是遍历然后统计次数，那么我们就可以将他存在hash里，可是数据量小我们可以存储，100G这种级别一次存储肯定是浪费空间而且机器不方便，所以我们提出了哈希分割这种方式，根据需要将给的文件大小切分为份，在每一份中查找计数即可。 我们重新整理下思路 （1）利用哈希分割将文件分割成1000份，相同的文件必定会进入同一份。 （2）在每一份中进行统计，每出现一次就让该位置的数据加一，最后找出出现次数最多的即可。
我们首先承接上一题的思路，我们得到了100G的数据时首先进行哈希分割，分割成1000份，保证相同的文件进入同一份，然后统计次数，得到每一个文件出现的次数，接下来我们要找到TOPK无疑是需要排序，我们可以在每一份下建立一个小堆，这样可以找出每一份中最大的K个文件，然后拿出1000份中的前K个在进行建小堆排序即可。
首先看到这道题说的是整数，整数是有范围的，固定42亿9千万。所以我们就可以用位图将他存起来然后查找，可是有一个新问题，位图只能表示存在状态，不存在为0，存在为1，那么我们怎么直到这是否只出现过一次呢？我们发散思维想一想，位图是用二进制表示的，一位二进制只可以表示一个状态，可是二位二进制就可以表示四个状态，这样我们可以做一个每一个位置有两位二进制的位图来表示，当不存在数据的时候为00，只存在一次的时候为01，存在两次为10，存在三次以及三次以上为11，接下来找出所有状态为01的位置即可。我们做一个存所有整数的位图需要512MB，这个位图只存了一位二进制，当我们需要两位二进制的时候所需要的空间就是一个GB大小。
首先看到题目给了一个GB内存我们可以通过上一道题联想,有可能是让我们开一个二位二进制的位图,不过由于是两个不同的文件都有100亿个整数,所以也有可能是开两个一位二进制的位图. 我们首先按照第一种想法继续想下去,开一个两位二进制的位图,那么我们可以让第一个位表示这个数在第一个文件的存在状态,第二个位表示在第二个文件的存在状态,这样的话如果这个数在两个文件都存在的话,那么他在位图中的位置所表示的两位二进制为11,我们只要找出所有为11的即可. 第二种方式我们需要建立两个一位二进制的位图,两个位图分别表示两个文件中整数的存在状态,接着我们让两个位图按位与即可,如果两个位置皆为1的话那么按位与结果也必定为1,这样就可以找出两个文件的交集. 我们可以将此题拓展,不只是找出文件的交集,还可以找出并集,利用第一种办法我们找出存在状态为01,10,11的即可,按照第二种方式我们让两个位图按位或即可.
这题算是第三题的拓展,题目明确给了一个G的内存,恰好够我们建立一个两位二进制的位图,我们在这个两位二进制的位图中用00表示一次也不出现,用01表示只出现一次,用10表示出现两次,用11表示三次以及三次以上,接着寻找我们需要的状态即可.
首先为了便于讲解,我们可以将query看作字符串. 由于处理的是字符串,那我们肯定不能用位图了,位图只能用于整数,字符串我们用布隆过滤器处理,不过布隆过滤器不够精确,如果数据存在那么在布隆过滤器中一定存在,可是当数据不存在时,布隆过滤器中也有可能存在,所以我们可以开两个 半个G的布隆过滤器处理文件,再找他的交集即可. 精确算法我们可以让一个布隆过滤器有多个映射方式(一般是4.5左右)这样基本可以保证精确.
首先我们要知道,精确的布隆过滤器是不支持删除元素的,因为要是你删除了这个位置的数据可能导致其他字符串找不到映射,所以我们这里讨论的是近似的范围. 那么怎么才可以让它支持计数与删除操作呢,原来我们是给他映射到了一个位来表示,这里我们可以给他映射到足够的n个位来操作,每当他出现一次我们可以给这个位中的数值加一,这样就支持了计数,要是想要删除数据,我们可以让它计数减一即可.
看完了上述七个问题我们会发现哈希是最常用的方式,当我们拿到海量数据时,第一时间先将他根据特点进行哈希分割,在每一份中进行操作,然后研究他需要的特点,如果没有特殊要求我们可以只开一位二进制表示状态,如果需要计数等操作我们给每一个映射多开几个位即可.
