一.哈希切割
- 哈希切分的基本概念： 是将一个大文件，利用哈希的原理， 将其分为若干个小文件。
【1】给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
- 根据 哈希切分的原理：相同的ip一定会进入同一个小文件中，用 map 统计每个小文件中相同ip出现的次数
二.位图应用
【1】给定100亿个整数，设计算法找到只出现一次的整数？
- 分析：我们可以用两个位图来控制，我们可以这样设计
- 代码展示设计思路如图所示：
template<size_t N> class twobitset { public: void set(size_t x) { // 00 -> 01 if (!_bs1.test(x) && !_bs2.test(x)) { _bs2.set(x); } // 01 -> 10 else if (!_bs1.test(x) && _bs2.test(x)) { _bs1.set(x); _bs2.reset(x); } // 本身10代表出现2次及以上，就不变了 } bool is_once(size_t x) { return !_bs1.test(x) && _bs2.test(x); } private: bitset<N> _bs1; bitset<N> _bs2; };
【2】位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
- 此题的设计思路与上面的【1】基本一致，设计上要稍作改动：
- 代码展示设计思路如图所示：
template<size_t N> class twobitset { public: void set(size_t x) { // 00 -> 01 if (!_bs1.test(x) && !_bs2.test(x)) { _bs2.set(x); //出现一次 } // 01 -> 10 else if (!_bs1.test(x) && _bs2.test(x)) { _bs1.set(x); _bs2.reset(x); //出现两次 }// 10 -> 11 else if (_bs1.test(x) && !_bs2.test(x)) { _bs2.set(x); //出现三次 } // 此外代表出现3次及以上，就不变了 } bool max_two(size_t x) { return (_bs1.test(x) && !_bs2.test(x))||(!_bs1.test(x) && _bs2.test(x)); //10 或者 01 } private: bitset<N> _bs1; bitset<N> _bs2; };
【3】给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
- 分析：
- 第一种思路是：把其中一个文件存入位图，遍历另一个文件元素，将问题转变成"在不在"问题
- 问题缺陷： 这种问题存在去重问题，即多次重复（下图中，交集明明只有一个3，但是会出现多个重复的3交集）
- 分析：
- 第二种思路是：将两个文件映射到两个位图中去（实现去重）
- 如果相对应的位置都是1（满足相＆为1），则此元素就在交集中
三.布隆过滤器
【1】给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法————（哈希切分）
- 我们先有一个内存大小基本概念：1G约为10亿byte，假设一个query平均为30byte，那么100亿query就约为3000亿byte，约为300G
- 哈希切分的基本概念： 是将一个大文件，利用哈希的原理， 将其分为若干个小文件。
- 相同的数据都被分到同一个文件里
- 在此题中，如下图所示，即：A和B中相同的query就会进入相同的小文件中
【2】如何扩展BloomFilter使得它支持删除元素的操作
- 多个位标识同一个值，使用 引用计数
