十个海量数据处理方法大总结内阐述

OK，看完上面这么多面试题，你是不是感觉有点头晕了？ 是的，需要一个总结。 接下来，本文将简单总结一些处理海量数据问题的常用方法。 以后这些方法将会在这个BLOG中详细解释。

以下方法均来自博客。 它们是对海量数据处理方法的概括总结。 当然，这些方法可能并不能完全覆盖所有问题，但是其中一些方法基本上可以解决遇到的绝大多数问题。 下面的一些问题基本上都是直接来源于公司的书面面试问题。 该方法不一定是最好的。 如果您有更好的处理方法，欢迎大家讨论。

- ，盛开

适用范围：可以用来实现数据字典，判断数据的权重，或者求集合的交集。

基本原则和要点：

原理很简单，位数组+k个独立的哈希函数。查找时将哈希函数对应的值的位数组设置为1

如果发现哈希函数的对应位全部为1，则说明存在。 显然，这个过程并不能保证搜索结果100%正确。

同时，不支持删除插入的关键字，因为该关键字对应的位会影响其他关键字。 所以一个简单的改进就是Bloom，它使用数组而不是位数组来支持删除。

还有一个更重要的问题，如何根据输入元素的数量n来确定位数组m的大小和哈希函数的数量。

当哈希函数的个数k=(ln2)*(m/n)时，错误率最小。 当错误率不大于E时，m必须至少等于n*lg(1/E)才能表示任意n个元素的集合。 但m应该更大，因为位数组中至少有一半必须为0，那么m应该>=gate 1 g(1/E)*lge，大约是nlg(1/E)倍（lg意味着2是对数的基地）。

例如，如果我们假设错误率为 ，则 m 应约为 n 的 13 倍。 所以k大约是8。

注意这里m和n的单位不同，m是bit的单位，n是元素个数的单位（准确的说是不同元素的个数）。 通常单个元素的长度是很多位。 所以使用bloom通常可以节省内存。

扩展：

Bloom将集合中的元素映射为一个位数组，用k（k为哈希函数的个数）映射位是否全为1来表示。

该元素不在该集合中。 布隆（CBF）将位数组中的每一位扩展为 1，从

并且支持元素的删除操作。 Bloom (SBF) 将其与集合元素出现的次数相关联。 SBF采用

来近似元素的出现频率。

问题示例：给您两个文件 A 和 B，每个文件存储 50 亿个 URL。 每个URL占用64字节，内存限制为4G。 让你找到文件A和B的共同URL。如果有3个甚至n个文件怎么办？

基于这个问题，我们来计算一下内存的使用情况。 4G=2^32大约是40亿*8，也就是340亿左右，n=50亿，比如

。 现在可用的是340亿，差别不大。 这可能会增加错误率。 另外，如果这些URL一一对应，就可以转换成IP，就简单多了。

二，

适用范围：快速查找和删除的基本数据结构，通常可以将所需数据总量放入内存

基本原则和要点：

哈希函数选择，针对字符串、整数、排列，具体对应哈希方法。

碰撞处理，一开