大数据处理算法要点.pdf

大数据处理算法 目录 大数据处理算法一： Bitmap 算法 2 大数据处理算法二： Bloom Filter 算法 5 大数据处理算法三：分而治之 /hash 映射 + hash 统计 + 堆 / 快速 / 归并排序 11 标签：算法 ,大数据 ,编程 ,面试题 ,腾讯 1 大数据处理算法一： Bitmap 算法 腾讯面试题：给 20 亿个不重复的 unsigned int 的整数，没排过序的，然后再 给一个数，如何快速判断这个数是否在那 40 亿个数当中并且所耗内存尽可能 的少？ 解析 :bitmap 算法就好办多了 所谓 bitmap ，就是用每一位来存放某种状态，适用于大规模数据，但数据状态 又不是很多的情况。通常是用来判断某个数据存不存在的。 例如，要判断一千万个人的状态，每个人只有两种状态：男人，女人，可以用 0，1 表示。那么就可以开一个 int 数组 ，一个 int 有 32 个位，就可以表示 32 个人。操作的时候可以使用 位操作 。 一，申请 512M的内存 一个 bit 位代表一个 unsigned int 值 读入 20 亿个数，设置相应的 bit 位 读入要查询的数，查看相应 bit 位是否为 1，为 1 表示存在，为 0 表示不存在 二、使用位图法判断整形 数组 是否存在重复 判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常 希望少进行几次扫描，这时双重循环法就不可取了。 位图法比较适合于这种情况，它的做法是按照集合中最大元素 max创建一个长 度为 max+1的新数组 ，然后再次扫描原数组，遇到几就给新数组的第几位置上 1，如遇到 5 就给新数组的第六个元素置 1，这样下次再遇到 5 想置位时发现新 数组的第六个元素已经是 1 了，这说明这次的数据肯定和以前的数据存在着重 复。这种给新 数组 初始化时置零其后置一的做法类似于位图的处理方法故称位 图法。它的运算次数最坏的情况为 2N。如果已知 数组 的最大值即能事先给新数 组定长的话效率还能提高一倍。 1. import java.util.BitSet; 2. /** 3. * 大数据处理算法一， bitmap 算法 4. * @author JYC506 5. * 6. */ 7. public class Bitmap { 2 8. 9. byte[] tem; 10. 11. public Bitmap(int length) { 12. this.tem = new byte[length]; 13. } 14. 15. public void add(int num) { 16. if (num tem.length) { 17. if (tem[num] != 1) { 18. tem[num] = 1; 19. } 20. } 21. } 22. 23. public boolean contain(int num) { 24. if (num tem.length) { 25. if (tem[num] == 1) { 26. return true; 27. } 28. } 29. return false; 30. }