大数据、空间限制
- 布隆过滤器
使用很少的空间就可以将准确率做到很高的程度（网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统等）
有一定的失误率
单个样本的大小不影响布隆过滤器的大小
n个输入、k个hash函数、m范围（布隆过滤器大小）
宁可错杀一千，绝不放过一个，当hash映射的k个bit有一个不为1时，它一定不再制定集合里，反之却不一定在集合里（m大小有限，存在误差）
- 大数据处理技巧（限制空间）
把一个大的集合通过哈希函数分配到多台机器（文件）中。
善于用bitmap数组（可用nbit代表一个数、1bit可判断是否出现过、2bit可查找出现0，1，2，3次的数，以此类推）
很多大数据问题都离不开分流，，要么是哈希函数将大文件内容分配给不同的机器，要么是哈希函数将大文件拆成小文件，然后处理每一个小数量集合（哈希函数的性质决定了同一个输入不可能分给不同的机器）
topK问题：
1. 哈希函数分流、哈希表词频统计
2. 堆结构（大、小根堆插入删除操作）、外排序