常用大数据量，海量数据处理方法，算法总结

海量数据处理方法总结 本文总结了常用的海量数据处理方法，包括 Bloom filter、Hashing 和 bit-map 等。这些方法可以用来解决大数据量的问题，例如数据字典、判重、集合求交集等问题。 Bloom Filter Bloom filter 是一种空间效率高、查询效率高的数据结构，可以用来实现数据字典、判重、集合求交集等操作。其原理是使用位数组+k 个独立的哈希函数，将哈希函数对应的值的位数组置 1，查找时如果发现所有哈希函数对应位都是 1 则说明存在。Bloom filter 可以用来解决大数据量的问题，但它并不保证查找结果的正确性，并且不支持删除已经插入的关键字。 改进的方法包括 counting Bloom filter，用一个 counter 数组代替位数组，可以支持删除操作。还需要根据输入元素个数 n，确定位数组 m 的大小及哈希函数个数 k，通常情况下，k=(ln2)*(m/n) 时错误率最小。 Hashing Hashing 是一种快速查找、删除的基本数据结构，需要总数据量可以放入内存。Hash 函数的选择取决于数据类型，例如字符串、整数、排列等。碰撞处理有两种方法：open hashing（拉链法）和 closed hashing（开地址法）。 扩展的方法包括 d-left hashing，例如 2-left hashing，将哈希表分成长度相等的两半，分别配备一个哈希函数，用于存储和查找。 bit-map bit-map 是一种使用 bit 数组来表示某些元素是否存在的数据结构，可以用来进行快速查找、判重、删除操作。其适用范围是数据范围是 int 的 10 倍以下。 问题实例 1. 给你 A,B 两个文件，各存放 50 亿条 URL，每条 URL 占用 64 字节，内存限制是 4G，让你找出 A,B 文件共同的 URL。 2. 海量日志数据，提取出某日访问百度次数最多的那个 IP。 3. 如何根据输入元素个数 n，确定位数组 m 的大小及哈希函数个数 k。 这些问题可以使用上述方法来解决，例如使用 Bloom filter 或 Hashing 等方法来查找、判重、删除大数据量的数据。