大数据处理算法要点

1大数据处理算法目录大数据处理算法一：Bitmap算法..........................................................................2大数据处理算法二：BloomFilter算法................................................................5大数据处理算法三：分而治之/hash映射+hash统计+堆/快速/归并排序...........11标签：算法,大数据,编程,面试题,腾讯2大数据处理算法一：Bitmap算法腾讯面试题：给20亿个不重复的unsignedint的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中并且所耗内存尽可能的少？解析:bitmap算法就好办多了所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。例如，要判断一千万个人的状态，每个人只有两种状态：男人，女人，可以用0，1表示。那么就可以开一个int数组，一个int有32个位，就可以表示32个人。操作的时候可以使用位操作。一，申请512M的内存一个bit位代表一个unsignedint值读入20亿个数，设置相应的bit位读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在二、使用位图法判断整形数组是否存在重复判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取了。位图法比较适合于这种情况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上1，如遇到5就给新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。1.importjava.util.BitSet;2./**3.*大数据处理算法一，bitmap算法4.*@authorJYC5065.*6.*/7.publicclassBitmap{38.9.byte[]tem;10.11.publicBitmap(intlength){12.this.tem=newbyte[length];13.}14.15.publicvoidadd(intnum){16.if(numtem.length){17.if(tem[num]!=1){18.tem[num]=1;19.}20.}21.}22.23.publicbooleancontain(intnum){24.if(numtem.length){25.if(tem[num]==1){26.returntrue;27.}28.}29.returnfalse;30.}31.32.publicstaticvoidmain(String[]args){33./*运行前内存*/34.longbeforeMemory=Runtime.getRuntime().totalMemory();35.longstart1=System.currentTimeMillis();36.BitSetset=newBitSet(2000000000);37.for(inti=0;i2000000000;i++){38./*假设898989这个数不在20亿个数里面*/39.if(i!=898989){40.set.set(i,true);41.}42.}43./*创建20亿个数后所占内存*/44.longafterMemory=Runtime.getRuntime().totalMemory();45.longend1=System.currentTimeMillis();446.System.out.println(总共内存使用:+(afterMemory-beforeMemory)/1024/1024+MB);47.System.out.println(存入内存耗时:+(end1-start1)+毫秒);48.longstart2=System.currentTimeMillis();49.booleanisExit1=set.get(898989);50.booleanisExit2=set.get(900000);51.52.longend2=System.currentTimeMillis();53./*输出在20亿个数中判断898989是否包含在里面*/54.System.out.println(isExit1);55.System.out.println(20个亿中+(isExit1?包含:不包含)+898989);56.System.out.println(20个亿中+(isExit2?包含:不包含)+900000);57.System.out.println(查询用时:+(end2-start2)+毫秒);58.}59.60.}5大数据处理算法二：BloomFilter算法百度面试题：给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？BloomFilter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求100%正确的场合。一.实例为了说明BloomFilter存在的重要意义，举一个实例：（实例一）,假设要你写一个网络蜘蛛（webcrawler）。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL。给一个URL，怎样知道蜘蛛是否已经访问过呢？稍微想想，（实例二）给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？就会有如下几种方案：1.将访问过的URL保存到数据库。2.用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。3.URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。4.Bit-Map方法。建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。方法1~3都是将访问过的URL完整保存，方法4则只标记URL的一个映射位。以上方法在数据量较小的情况下都能完美解决问题，但是当数据量变得非常庞大时问题就来了。6方法1的缺点：数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了？方法2的缺点：太消耗内存。随着URL的增多，占用的内存会越来越多。就算只有1亿个URL，每个URL只算50个字符，就需要5GB内存。方法3：由于字符串经过MD5处理后的信息摘要长度只有128Bit，SHA-1处理后也只有160Bit，因此方法3比方法2节省了好几倍的内存。方法4消耗内存是相对较少的，但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么？若要降低冲突发生的概率到1%，就要将BitSet的长度设置为URL个数的100倍。实质上上面的算法都忽略了一个重要的隐含条件：允许小概率的出错，不一定要100%准确！也就是说少量url实际上没有没网络蜘蛛访问，而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。例如有一组字符arr：”哈哈“，”呵呵“........字符串：“哈哈”哈希算法1处理后：8哈希算法2处理后：1哈希算法1处理后：3插入BitArray后再处理字符串：“呵呵”哈希算法1处理后：2哈希算法2处理后：1哈希算法1处理后：9继续插入BitArray后，如果继续游字符串，继续以这种方式插入7判断”在这些字符串是否包含”嘻嘻“哈希算法1处理后：0哈希算法2处理后：1哈希算法1处理后：7只要判断下标分别为0,1,7位置的值是否都为1，如下图因为位置0跟位置7的值不为1所以”嘻嘻“不包含在arr中，反之如果都为1怎包含java代码实现如下1.importjava.util.ArrayList;2.importjava.util.BitSet;3.importjava.util.List;4.5./**6.*BloomFilter算法7.*8.*@authorJYC5069.*10.*/11.publicclassBloomFilter{12./*哈希函数*/13.privateListIHashFunctionhashFuctionList;14./*构造方法*/15.publicBloomFilter(){16.this.hashFuctionList=newArrayListIHashFunction();17.}18./*添加哈希函数类*/819.publicvoidaddHashFunction(IHashFunctionhashFunction){20.this.hashFuctionList.add(hashFunction);21.}22./*删除hash函数*/23.publicvoidremoveHashFunction(IHashFunctionhashFunction){24.this.hashFuctionList.remove(hashFunction);25.}26./*判断是否被包含*/27.publicbooleancontain(BitSetbitSet,Stringstr){28.for(IHashFunctionhash:hashFuctionList){29.inthashCode=hash.toHashCode(str);30.if(hashCode0){31.hashCode=-hashCode;32.}33.if(bitSet.get(hashCode)==false){34.returnfalse;35.}36.}37.returntrue;38.}39./*添加到bitSet*/40.publicvoidtoBitSet(BitSetbitSet,Stringstr){41.for(IHashFunctionhash:hashFuctionList){42.inthashCode=hash.toHashCode(str);43.if(hashCode0){44.hashCode=-hashCode;45.}46.bitSet.set(hashCode,true);47.}48.}49.50.publicstaticvoidmain(String[]args){51.BloomFilterbloomFilter=newBloomFilter();52./*添加3个哈希函数*/53.bloomFilter.addHashFunction(newJavaHash());54.bloomFilter.addHashFunction(newRSHash());55.bloomFilter.addHashFunction(newSDBMHash());56./*长度为2的24次方*/957.BitSetbitSet=newBitSet(125);58./*判断test1很test2重复的字符串*/59.String[]test1=newString[]{哈哈,我,大家,逗比,有钱人性,小米,Iphone,helloWorld};60.for(Stringstr1:test1){61.bloomFilter.toBitSet(bitSet,str1);62.}63.String[]test2=newString[]{哈哈,我的,大家,逗比,有钱的人性,小米,Iphone6s,h