认识达内从这里开始

问题一：什么是大数据？

大数据（big data，mega data），或称巨量资料，指的是需要新处理模式才能具有更强的决策力、洞察力和流程优化能力的海量、高增长率和多样化的信息资产。 在维克托·迈尔-舍恩伯格及肯尼斯·库克耶编写的《大数据时代》中大数据指不用随机分析法（抽样调查）这样的捷径，而采用所有数据进行分析处理。大数据的4V特点：Volume（大量）、Velocity（高速）、Variety（多样）、Value（价值）。

问题二：给一个超过100G大小的log file，log中存着IP地址 ，设计算法找到出现次数最多的IP地址？

答：

首先看到100G的日志文件，我们的第一反应肯定是太大了，根本加载不到内存，更别说设计算法了，那么怎么办呢？既然装不下，我们是不是可以将其切分开来，一小部分一小部分轮流进入内存呢，答案当然是肯定的。

在这里要记住一点：但凡是大数据的问题，都可通过切分来解决它。

粗略算一下：如果我们将其分成1000个小文件，每个文件大概就是500M左右的样子，现在计算机肯定轻轻 松松就能装下。

那么，问题又来了，怎样才能保证相同的IP被分到同一个文件中呢？

这里我想到的是哈希切分，使用相同的散列函数（如 BKDRHash）将所有IP地址转换为一个整数key，再利用 index=key%1000就可将相同IP分到同一个文件。

依次将这1000个文件读入内存，出现次数最多的IP进行统计。

最后，在1000个出现次数最多的IP中找出最大的出现次数即为所求。

用到的散列函数：

问题三：与上题条件相同，如何找到TOP K的IP？

答：

这倒题说白了就是找前K个出现次数最多的IP，即降序排列IP出现的次数。

与上题类似，我们用哈希切分对分割的第一个个小文件中出现最多的前K个IP建小堆，

然后读入第二个文件，将其出现次数最多的前K个IP与 堆中数据进行对比，

如果包含大于堆中的IP出现次数，则更新小堆，替换原堆中次数的出现少的数据

再读入第三个文件，以此类推……

直到1000个文件全部读完，堆中出现的K个IP即是出现 次数最多的前K个IP地址。

问题四：给定100亿个整数，设计算法找到只出现一次的整数 ？

答：

看到此题目，我的第一反应就是估算其占用内存的大小：100亿个int，一个int4个字节，100亿*4=400亿字节

又因为42亿字节约等于4G，所以100亿个整数大概占用的内存为40G，一次加载到内存显然是不太现实的。

反过来想，所有整数所能表示的范围为2^32，即16G， 故给出的数据有很多数据是重复的。

解法1：哈希切分

与第一题类似，用哈希切分将这些数据分到100个文件 中，每个文件大约400M，将每一个文件依次加载到内存中，利用哈希表统计出现一次的整数，将100个文件中出现一次的整数汇总起来即为所求。

解法2：位图变形

我们知道，位图是利用每一位来表示一个整数是否存在来节省空间，1表示存在，0表示不存在。

而上题对于所有整数而言，却有三种状态：不存在、 存在一次、存在多次。

故此，我们需要对传统位图进行扩展，用两位来表示一个整数的状态：00表示不存在、01表示存在一次， 10表示存在多次，11表示无效状态。

按照上述表示，两位表示一个整数状态，所有整数只需要1G即可表示其存在与否。

解法3：

众所周知，一个整数占32位，那么我们可对每一位按照0和1将其分为两个文件，直到划分到最低位，如果被分的文件中哪个文件只包含一个数据，那么，此数据即为只出现一次的整数。

如下图：

给两个文件，分别有100亿个整数，我们只有1G内存 ，如何找到两个文件交集？

答：100亿*4字节 = 400亿字节 = 40G

解法1：普通查找

将其中的一个文件分为100个小文件，每一份占400M， 将每一小份轮流加到内存中，与第二个文件中的数据进行对比，找到交集。此种算 法时间复杂度为O（N*N）。

解法2：哈希切分

对两个文件分别进行哈希切分，将其分为100个小文件 ，index=key%100（index为文件下标）。

将两个文件中下标相同的小文件进行对比，找出其交集。将100个文件的交集汇总起来即为所给文件的文件交集 。此种算法时间复杂度为O（N）。