位图 一个数组的每个数据的每个二进制位表示一个数据 0–不存在，1–存在 这样并不能存储数据的值，只能存储数据的存在状态。所以，位图的优点是显而易见的。 位图可以节省空间，处理海量数据，可用于在大量数据中查找某个数据是否存在。 布隆过滤器
九章算法第七讲——大数据 1）给⼀一个超过100G⼤大⼩小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？! 2）与上题条件相同，如何找到top K的IP？如何直接⽤用Linux系统命令实现？! 3）给定100亿个整数，设计算法找到只出现⼀一次的整数! 4）给两个⽂文件，分别有100亿个整数，我们只有1G内存，如何找到两个⽂文件交集! 5）1个⽂文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数! 6）给两个⽂文件，分别有100亿个query，我们只有1G内存，如何找到两个⽂文件交集？分别给出精确 算法和近似算法! 7）如何扩展BloomFilter使得它⽀支持删除元素的操作？! 8）如何扩展BloomFilter使得它⽀支持计数操作？! 9）给上千个⽂文件，每个⽂文件⼤大⼩小为1K—100M。给n个词，设计算法对每个词找到所有包含它的⽂文 件，你只有100K内存! 10）有⼀一个词典，包含N个英⽂文单词，现在任意给⼀一个字符串，设计算法找出包含这个字符串的所 有英⽂文单词!
