大数据处理的思路一般是这样的：把一个内存中放不下的文件按照一定的方法切分成小文件，再看是否有合适的数据结构能解决这个问题。当然，有时候不用切分，用位图也可以解决，根据具体问题而定。接下来我们看看下面几道大数据的面试题，这种题一般面试官也只是需要一个思路。
1）给一个超过100G大小的log file,log中存着IP地址,设计算法找到出现次数最多的IP地址？
问题分析：
100G普通机器内存中肯定是放不下的，目前使用的IP地址相当于一个32位的字符串，所以，这么大的文件，我们考虑切分，但是仅仅切分还不行，假设有1G可用的内存，那我们切分成100份，那还得把这100个文件全部遍历一遍，把每一个出现的IP都统计一下次数，最后找到出现次数最多的IP，这是一种解法，不过效率不高。
解决方案：
把这32位的IP通过字符串哈希函数转化成对应的整形，把100G文件分成1000个，从硬盘中读取这些IP，转化成整形后对文件个数取余，余数是多少就放进哪个文件里，这样就保证相同的IP一定是在同一个文件里。这种方法也叫做Hash分桶法。分好之后去统计每个文件里出现次数最多的，问题就转化成找这1000个IP出现次数最多的一个。
（2）与上题条件相同，如何找到top K的IP？
问题分析：
上一题是找出现次数最多的1个，这个是最多的前K个，很容易想到的是像刚才一样，找出每个文件里次数最多的，出来再找前K个，然而这样实际上是不对的。为啥呢？因为不能保证某个文件里的最大的就一定比另一个文件里最小的大。比如文件1里出现次数最多是10次，而文件2里出现次数最少的是100次。
解决方案：
跟第一题一样先采用Hash分桶法分好，然后找出每个文件里的top K，最后top K 进行汇总。如何找出top k 呢?这里完全可以考虑建立一个K个数据的小堆，最后堆里保留的就是k个最大的数，为啥要建立小堆？正常想着不是应该建立大堆吗？可以参考我之前写的关于堆的博客，最后有说到：http://blog.csdn.net/pointer_y/article/details/52791518
（3）给定100亿个整数，设计算法找到只出现一次的整数。
问题分析：
首先，100亿整数内存肯定放不下，其次，整数范围是到42亿多，所以，这100亿里一定有很多重复的数字。一般首先想到的就是切分，切到内存中能放下，然后遍历去找。太慢了，它找只出现一次的，可以考虑用位图。
解决方案：
位图一般是用1个位来表示数存在或者不存在，这里它找只出现1次的，所以用两个位来表示，两个位就是4个状态，我们只使用3个状态就好，分别是不存在，出现1次，出现多次，具体多次我们不管，这里只管出现1次的。用两个位表示一个数，42亿个数大概需要开1个G大的位图就ok。
（4）给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
问题分析：
内存放不下，我们首先想到了切割，把A文件切分成100份，拿B文件去比对。缺点依然是慢，效率不高。
解决方案：
( 5）1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。
问题分析：
解决方案：
( 6）给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确 算法和近似算法。
问题分析：
这又是一个找交集的问题，所以可以考虑用哈希分桶法解决，那么近似的算法是什么呢？把字符串转化成整形，当一个元素被加入集合时，通过 K 个Hash 函数将这个元素映射成一个位阵列（Bit array）中的 K 个点，把它们置为 1。检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了：
画图示意：
解决方案：
精确算法用哈希分桶法，和前面的题很类似，近似的用布隆过滤器，得到的结果是近似的。
( 7）如何扩展BloomFilter（ 布隆过滤器）使得它支持删除元素的操作？
问题分析：
因为一个字符串是用多个位表示的，其他字符串很可能与要删除的字符串占用了相同的位（如上图），所以，不能直接删除，影响了其他字符状态的表示。
解决方案：
采用引用计数，不过因为字符串出现的次数可能比较大，一个char是不行的，我们用size_t，但是这样就失去了布隆过滤器省空间的优势，这也是没办法的，如果文件太大，那就只能先进行切分了。采用引用计数就不用再拿一个位来表示存在不存在了，直接拿引用计数来表示，为0代表不存在。我在这里实现了一个支持删除的布隆。
源码：
#include<iostream>
#include<vector>
#include<string>
using namespace std;
struct HashFunc1
{
size_t operator()(const char* str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = hash * 131 + ch; // 也可以乘以31、131、1313、13131、131313..
}
return hash;
}
};
struct HashFunc2
{
size_t operator()(const char* str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = 65599 * hash + ch;
//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
};
struct HashFunc3
{
size_t operator()(const char* str)
{
register size_t hash = 0;
size_t magic = 63689;
while (size_t ch = (size_t)*str++)
{
hash = hash * magic + ch;
magic *= 378551;
}
return hash;
}
};
struct HashFunc4
{
size_t operator()(const char* str)
{
register size_t hash = 0;
size_t ch;
for (long i = 0; ch = (size_t)*str++; i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
}
}
return hash;
}
};
struct HashFunc5
{
size_t operator()(const char* str)
{
if (!*str)
return 0;
register size_t hash = 1315423911;
while (size_t ch = (size_t)*str++)
{
hash ^= ((hash << 5) + ch + (hash >> 2));
}
return hash;
}
};
//一个字符串类型的布隆过滤器
template<class T=string,class _HashFunc1=HashFunc1,class _HashFunc2=HashFunc2,class _HashFunc3=HashFunc3,class _HashFunc4=HashFunc4,class _HashFunc5=HashFunc5>
class BloomFilter
{
public:
BloomFilter(int num)
:_range(num * 5)
{
_RefBloomfilter.resize(_range);
}
void Set(const char* str)
{
//分别通过5个字符串hash函数得到5个对应的位置
size_t hash1 = HashFunc1()(str) %_range;
size_t hash2 = HashFunc2()(str) % _range;
size_t hash3 = HashFunc3()(str) % _range;
size_t hash4 = HashFunc4()(str) % _range;
size_t hash5 = HashFunc5()(str) % _range;
_RefBloomfilter[hash1]++;
_RefBloomfilter[hash2]++;
_RefBloomfilter[hash3]++;
_RefBloomfilter[hash4]++;
_RefBloomfilter[hash5]++;
printf("%d,%d,%d",hash1,hash2,hash3,hash4,hash5); //可以输出5个位置看一看
cout << endl;
}
bool ReSet(const char* str) //删除
{
size_t hash1 = HashFunc1()(str) % _range;
size_t hash2 = HashFunc2()(str) % _range;
size_t hash3 = HashFunc3()(str) % _range;
size_t hash4 = HashFunc4()(str) % _range;
size_t hash5 = HashFunc5()(str) % _range;
if (_RefBloomfilter[hash1] == 0 || _RefBloomfilter[hash2] == 0
|| _RefBloomfilter[hash3] == 0 || _RefBloomfilter[hash4] == 0
|| _RefBloomfilter[hash5] == 0)
return false;
_RefBloomfilter[hash1]--;
_RefBloomfilter[hash2]--;
_RefBloomfilter[hash3]--;
_RefBloomfilter[hash4]--;
_RefBloomfilter[hash5]--;
return true;
}
bool Test(const char* str) //查找
{
size_t hash1 = HashFunc1()(str) % _range;
size_t hash2 = HashFunc2()(str) % _range;
size_t hash3 = HashFunc3()(str) % _range;
size_t hash4 = HashFunc4()(str) % _range;
size_t hash5 = HashFunc5()(str) % _range;
if (_RefBloomfilter[hash1]&&
_RefBloomfilter[hash2] &&
_RefBloomfilter[hash3] &&
_RefBloomfilter[hash4] &&
_RefBloomfilter[hash5])//都不为0则存在
return true;
else
return false;
}
protected:
vector<size_t> _RefBloomfilter; //为了支持删除，直接使用一个size_t 的vector来做引用计数
size_t _range;
};
void TestBloomfilter()
{
BloomFilter<> bf(100);
string url1("http://write.blog.csdn.net/postedit/53088473");
string url2("http://blog.csdn.net/pointer_y/article/details/52926334");
string url3("http://blog.csdn.net/pointer_y/article/details/52776595");
bf.Set(url1.c_str());
bf.Set(url2.c_str());
bf.Set(url3.c_str());
cout << bf.Test(url1.c_str()) << endl;
bf.ReSet(url1.c_str());
cout << bf.Test(url1.c_str())<<endl;
}
结果分析：我只用了3个字符串测试了一下，这三个字符串所占用的位置并没有重复。没有删除前查找字符串1结果是找到了，删除后结果为0没有找到。这是一个支持删除的布隆过滤器，一般的布隆是用位图来实现的，存在还是不存在用多个位来表示就好，很省空间，而要它支持删除就不行了。
前面多次提到位图的概念，那位图是什么呢？即用一个位来表示对应的数据存在还是不存在，STL中也存在位图，我自己实现了一个，只包含了常用的set，reset，test 3个方法。
#pragma once
#include<iostream>
#include<vector>
using namespace std;
class BitMap
{
public:
BitMap(size_t size)
{
_bitMap.resize((size>>5)+1);
}
void Set(const int& x)
{
int index = x >> 5; //除效率不高，所以这里用右移5位表示除以32，得到x所在的数据个数
int bit = x % 32; //得到x的位
_bitMap[index] |= (1 << bit);
}
void ReSet(const int& x)
{
int index = x >> 5;
int bit = x % 32;
_bitMap[index] &= (~(1 << bit));
}
bool Test(const int& x)
{
int index = x >> 5;
int bit = x % 32;
return _bitMap[index] & (1 << bit);
}
private:
vector<size_t> _bitMap;
};
void TestBitMap()
{
BitMap bm(40);
bm.Set(10);
bm.Test(10);
bm.Test(20);
}这是我对于大数据问题的一些看法，分享出来，如上述问题有更优的解决方案，请不吝赐教~