大數(shù)據(jù)處理算法

大數(shù)據(jù)處理算法目錄大數(shù)據(jù)處理算法一：Bitmap算法 2大數(shù)據(jù)處理算法二：BloomFilter算法 5大數(shù)據(jù)處理算法三：分而治之/hash映射+hash統(tǒng)計(jì)+堆/快速/歸并排序 11標(biāo)簽：算法,大數(shù)據(jù),編程,面試題,騰訊大數(shù)據(jù)處理算法一：Bitmap算法騰訊面試題：給20億個(gè)不重復(fù)的unsignedint的整數(shù)，沒排過序的，然后再給一個(gè)數(shù)，如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中并且所耗內(nèi)存盡可能的少？解析:bitmap算法就好辦多了所謂bitmap，就是用每一位來存放某種狀態(tài)，適用于大規(guī)模數(shù)據(jù)，但數(shù)據(jù)狀態(tài)又不是很多的情況。通常是用來判斷某個(gè)數(shù)據(jù)存不存在的。例如，要判斷一千萬個(gè)人的狀態(tài)，每個(gè)人只有兩種狀態(tài)：男人，女人，可以用0，1表示。那么就可以開一個(gè)int數(shù)組，一個(gè)int有32個(gè)位，就可以表示32個(gè)人。操作的時(shí)候可以使用位操作。一，申請512M的內(nèi)存一個(gè)bit位代表一個(gè)unsignedint值讀入20億個(gè)數(shù)，設(shè)置相應(yīng)的bit位讀入要查詢的數(shù)，查看相應(yīng)bit位是否為1，為1表示存在，為0表示不存在二、使用位圖法判斷整形數(shù)組是否存在重復(fù)判斷集合中存在重復(fù)是常見編程任務(wù)之一，當(dāng)集合中數(shù)據(jù)量比較大時(shí)我們通常希望少進(jìn)行幾次掃描，這時(shí)雙重循環(huán)法就不可取了。位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創(chuàng)建一個(gè)長度為max+1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上1，如遇到5就給新數(shù)組的第六個(gè)元素置1，這樣下次再遇到5想置位時(shí)發(fā)現(xiàn)新數(shù)組的第六個(gè)元素已經(jīng)是1了，這說明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復(fù)。這種給新數(shù)組初始化時(shí)置零其后置一的做法類似于位圖的處理方法故稱位圖法。它的運(yùn)算次數(shù)最壞的情況為2N。如果已知數(shù)組的最大值即能事先給新數(shù)組定長的話效率還能提高一倍。importjava.util.BitSet;/***大數(shù)據(jù)處理算法一，bitmap算法*@authorJYC506**/publicclassBitmap{byte[]tem;publicBitmap(intlength){this.tem=newbyte[length];}publicvoidadd(intnum){if(num<tem.length){if(tem[num]!=1){tem[num]=1;}}}publicbooleancontain(intnum){if(num<tem.length){if(tem[num]==1){returntrue;}}returnfalse;}publicstaticvoidmain(String[]args){/*運(yùn)行前內(nèi)存*/longbeforeMemory=Runtime.getRuntime().totalMemory();longstart1=System.currentTimeMillis();BitSetset=newBitSet(2000000000);for(inti=0;i<2000000000;i++){/*假設(shè)898989這個(gè)數(shù)不在20億個(gè)數(shù)里面*/if(i!=898989){set.set(i,true);}}/*創(chuàng)建20億個(gè)數(shù)后所占內(nèi)存*/longafterMemory=Runtime.getRuntime().totalMemory();longend1=System.currentTimeMillis();System.out.println("總共內(nèi)存使用:"+(afterMemory-beforeMemory)/1024/1024+"MB");System.out.println("存入內(nèi)存耗時(shí):"+(end1-start1)+"毫秒");longstart2=System.currentTimeMillis();booleanisExit1=set.get(898989);booleanisExit2=set.get(900000);longend2=System.currentTimeMillis();/*輸出在20億個(gè)數(shù)中判斷898989是否包含在里面*/System.out.println(isExit1);System.out.println("20個(gè)億中"+(isExit1?"包含":"不包含")+898989);System.out.println("20個(gè)億中"+(isExit2?"包含":"不包含")+900000);System.out.println("查詢用時(shí):"+(end2-start2)+"毫秒");}}大數(shù)據(jù)處理算法二：BloomFilter算法百度面試題：給定a、b兩個(gè)文件，各存放50億個(gè)url，每個(gè)url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url？BloomFilter是由Bloom在1970年提出的一種多哈希函數(shù)映射的快速查找算法。通常應(yīng)用在一些需要快速判斷某個(gè)元素是否屬于集合，但是并不嚴(yán)格要求100%正確的場合。一.實(shí)例為了說明BloomFilter存在的重要意義，舉一個(gè)實(shí)例：（實(shí)例一）,假設(shè)要你寫一個(gè)網(wǎng)絡(luò)蜘蛛（webcrawler）。由于網(wǎng)絡(luò)間的鏈接錯(cuò)綜復(fù)雜，蜘蛛在網(wǎng)絡(luò)間爬行很可能會(huì)形成“環(huán)”。為了避免形成“環(huán)”，就需要知道蜘蛛已經(jīng)訪問過那些URL。給一個(gè)URL，怎樣知道蜘蛛是否已經(jīng)訪問過呢？稍微想想，（實(shí)例二）給定a、b兩個(gè)文件，各存放50億個(gè)url，每個(gè)url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url？就會(huì)有如下幾種方案：1.將訪問過的URL保存到數(shù)據(jù)庫。2.用HashSet將訪問過的URL保存起來。那只需接近O(1)的代價(jià)就可以查到一個(gè)URL是否被訪問過了。3.URL經(jīng)過MD5或SHA-1等單向哈希后再保存到HashSet或數(shù)據(jù)庫。4.Bit-Map方法。建立一個(gè)BitSet，將每個(gè)URL經(jīng)過一個(gè)哈希函數(shù)映射到某一位。方法1~3都是將訪問過的URL完整保存，方法4則只標(biāo)記URL的一個(gè)映射位。以上方法在數(shù)據(jù)量較小的情況下都能完美解決問題，但是當(dāng)數(shù)據(jù)量變得非常龐大時(shí)問題就來了。方法1的缺點(diǎn)：數(shù)據(jù)量變得非常龐大后關(guān)系型數(shù)據(jù)庫查詢的效率會(huì)變得很低。而且每來一個(gè)URL就啟動(dòng)一次數(shù)據(jù)庫查詢是不是太小題大做了？方法2的缺點(diǎn)：太消耗內(nèi)存。隨著URL的增多，占用的內(nèi)存會(huì)越來越多。就算只有1億個(gè)URL，每個(gè)URL只算50個(gè)字符，就需要5GB內(nèi)存。方法3：由于字符串經(jīng)過MD5處理后的信息摘要長度只有128Bit，SHA-1處理后也只有160Bit，因此方法3比方法2節(jié)省了好幾倍的內(nèi)存。方法4消耗內(nèi)存是相對較少的，但缺點(diǎn)是單一哈希函數(shù)發(fā)生沖突的概率太高。還記得數(shù)據(jù)結(jié)構(gòu)課上學(xué)過的Hash表沖突的各種解決方法么？若要降低沖突發(fā)生的概率到1%，就要將BitSet的長度設(shè)置為URL個(gè)數(shù)的100倍。實(shí)質(zhì)上上面的算法都忽略了一個(gè)重要的隱含條件：允許小概率的出錯(cuò)，不一定要100%準(zhǔn)確！也就是說少量url實(shí)際上沒有沒網(wǎng)絡(luò)蜘蛛訪問，而將它們錯(cuò)判為已訪問的代價(jià)是很小的——大不了少抓幾個(gè)網(wǎng)頁唄。例如有一組字符arr：”哈哈“，”呵呵“字符串：“哈哈”哈希算法1處理后：8哈希算法2處理后：1哈希算法1處理后：3插入BitArray后

再處理字符串：“呵呵”哈希算法1處理后：2哈希算法2處理后：1哈希算法1處理后：9繼續(xù)插入BitArray后，如果繼續(xù)游字符串，繼續(xù)以這種方式插入判斷”在這些字符串是否包含”嘻嘻“哈希算法1處理后：0哈希算法2處理后：1哈希算法1處理后：7只要判斷下標(biāo)分別為0,1,7位置的值是否都為1，如下圖因?yàn)槲恢?跟位置7的值不為1所以”嘻嘻“不包含在arr中，反之如果都為1怎包含

java代碼實(shí)現(xiàn)如下importjava.util.ArrayList;importjava.util.BitSet;importjava.util.List;/***BloomFilter算法**@authorJYC506**/publicclassBloomFilter{/*哈希函數(shù)*/privateList<IHashFunction>hashFuctionList;/*構(gòu)造方法*/publicBloomFilter(){this.hashFuctionList=newArrayList<IHashFunction>();}/*添加哈希函數(shù)類*/publicvoidaddHashFunction(IHashFunctionhashFunction){this.hashFuctionList.add(hashFunction);}/*刪除hash函數(shù)*/publicvoidremoveHashFunction(IHashFunctionhashFunction){this.hashFuctionList.remove(hashFunction);}/*判斷是否被包含*/publicbooleancontain(BitSetbitSet,Stringstr){for(IHashFunctionhash:hashFuctionList){inthashCode=hash.toHashCode(str);if(hashCode<0){hashCode=-hashCode;}if(bitSet.get(hashCode)==false){returnfalse;}}returntrue;}/*添加到bitSet*/publicvoidtoBitSet(BitSetbitSet,Stringstr){for(IHashFunctionhash:hashFuctionList){inthashCode=hash.toHashCode(str);if(hashCode<0){hashCode=-hashCode;}bitSet.set(hashCode,true);}}publicstaticvoidmain(String[]args){BloomFilterbloomFilter=newBloomFilter();/*添加3個(gè)哈希函數(shù)*/bloomFilter.addHashFunction(newJavaHash());bloomFilter.addHashFunction(newRSHash());bloomFilter.addHashFunction(newSDBMHash());/*長度為2的24次方*/BitSetbitSet=newBitSet(1<<25);/*判斷test1很test2重復(fù)的字符串*/String[]test1=newString[]{"哈哈","我","大家","逗比","有錢人性","小米","Iphone","helloWorld"};for(Stringstr1:test1){bloomFilter.toBitSet(bitSet,str1);}String[]test2=newString[]{"哈哈","我的","大家","逗比","有錢的人性","小米","Iphone6s","helloWorld"};for(Stringstr2:test2){if(bloomFilter.contain(bitSet,str2)){System.out.println("'"+str2+"'是重復(fù)的");}}}}/*哈希函數(shù)接口*/interfaceIHashFunction{inttoHashCode(Stringstr);}classJavaHashimplementsIHashFunction{@OverridepublicinttoHashCode(Stringstr){returnstr.hashCode();}}classRSHashimplementsIHashFunction{@OverridepublicinttoHashCode(Stringstr){intb=378551;inta=63689;inthash=0;for(inti=0;i<str.length();i++){hash=hash*a+str.charAt(i);a=a*b;}returnhash;}}classSDBMHashimplementsIHashFunction{@OverridepublicinttoHashCode(Stringstr){inthash=0;for(inti=0;i<str.length();i++)hash=str.charAt(i)+(hash<<6)+(hash<<16)-hash;returnhash;}}大數(shù)據(jù)處理算法三：分而治之/hash映射+hash統(tǒng)計(jì)+堆/快速/歸并排序百度面試題1、海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個(gè)IP。IP是32位的，最多有個(gè)2^32個(gè)IP。同樣可以采用映射的方法，比如模1000，把整個(gè)大文件映射為1000個(gè)小文件，再找出每個(gè)小文中出現(xiàn)頻率最大的IP（可以采用hash_map進(jìn)行頻率統(tǒng)計(jì)，然后再找出頻率最大的幾個(gè)）及相應(yīng)的頻率。然后再在這1000個(gè)最大的IP中，找出那個(gè)頻率最大的IP，即為所求。百度面試題2、搜索引擎會(huì)通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個(gè)查詢串的長度為1-255字節(jié)。假設(shè)目前有一千萬個(gè)記錄（這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬，但如果除去重復(fù)后，不超過3百萬個(gè)。一個(gè)查詢串的重復(fù)度越高，說明查詢它的用戶越多，也就是越熱門。），請你統(tǒng)計(jì)最熱門的10個(gè)查詢串，要求使用的內(nèi)存不能超過1G。第一步借用hash統(tǒng)計(jì)進(jìn)行預(yù)處理：先對這批海量數(shù)據(jù)預(yù)處理(維護(hù)一個(gè)Key為Query字串，Value為該Query出現(xiàn)次數(shù)，即Hashmap(Query，Value)，每次讀取一個(gè)Query，如果該字串不在Table中，那么加入該字串，并且將Value值設(shè)為1；如果該字串在Table中，那么將該字串的計(jì)數(shù)加一即可。最終我們在O(N)（N為1千萬，因?yàn)橐闅v整個(gè)數(shù)組一遍才能統(tǒng)計(jì)處每個(gè)query出現(xiàn)的次數(shù)）的時(shí)間復(fù)雜度內(nèi)用Hash表完成了統(tǒng)計(jì)；

第二步借用堆排序找出最熱門的10個(gè)查詢串：時(shí)間復(fù)雜度為N'*logK。維護(hù)一個(gè)K(該題目中是10)大小的小根堆，然后遍歷3百萬個(gè)Query，分別和根元素進(jìn)行對比（對比value的值），找出10個(gè)value值最大的query

最終的時(shí)間復(fù)雜度是：O（N）+N'*O（logK），（N為1000萬，N’為300萬）或者：采用trie樹，關(guān)鍵字域存該查詢串出現(xiàn)的次數(shù)，沒有出現(xiàn)為0。最后用10個(gè)元素的最小推來對出現(xiàn)頻率進(jìn)行排序。我們先看HashMap實(shí)現(xiàn)1.HashMap的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)中有數(shù)組和鏈表來實(shí)現(xiàn)對數(shù)據(jù)的存儲(chǔ)，但這兩者基本上是兩個(gè)極端。數(shù)組數(shù)組存儲(chǔ)區(qū)間是連續(xù)的，占用內(nèi)存嚴(yán)重，故空間復(fù)雜的很大。但數(shù)組的二分查找時(shí)間復(fù)雜度小，為O(1)；數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難；鏈表鏈表存儲(chǔ)區(qū)間離散，占用內(nèi)存比較寬松，故空間復(fù)雜度很小，但時(shí)間復(fù)雜度很大，達(dá)O（N）。鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。哈希表那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)？答案是肯定的，這就是我們要提起的哈希表。哈希表（(Hashtable）既滿足了數(shù)據(jù)的查找方便，同時(shí)不占用太多的內(nèi)容空間，使用也十分方便。哈希表有多種不同的實(shí)現(xiàn)方法，我接下來解釋的是最常用的一種方法——拉鏈法，我們可以理解為“鏈表的數(shù)組”我用java自己實(shí)現(xiàn)了一個(gè)HashMap，當(dāng)然這比較簡點(diǎn)，不過能說明大概原理，改有的功能基本上有了index=hashCode(key)=key％16哈希算法很多，下面我用了java自帶的，當(dāng)然你也可以用別的/***自定義HashMap*@authorJYC506**@param<K>*@param<V>*/publicclassHashMap<K,V>{privatestaticfinalintCAPACTITY=16;transientEntry<K,V>[]table=null;@SuppressWarnings("unchecked")publicHashMap(){super();table=newEntry[CAPACTITY];}/*哈希算法*/privatefinalinttoHashCode(Objectobj){inth=0;if(objinstanceofString){returnStringHash.toHashCode((String)obj);}h^=obj.hashCode();h^=(h>>>20)^(h>>>12);returnh^(h>>>7)^(h>>>4);}/*放入hashMap*/publicvoidput(Kkey,Vvalue){inthashCode=this.toHashCode(key);intindex=hashCode%CAPACTITY;if(table[index]==null){table[index]=newEntry<K,V>(key,value,hashCode);}else{for(Entry<K,V>entry=table[index];entry!=null;entry=entry.nextEntry){if(entry.hashCode==hashCode&&(entry.key==key||key.equals(entry.key))){entry.value=value;return;}}Entry<K,V>entry2=table[index];Entry<K,V>entry3=newEntry<K,V>(key,value,hashCode);entry3.nextEntry=entry2;table[index]=entry3;}}/*獲取值*/publicVget(Kkey){inthashCode=this.toHashCode(key);intindex=hashCode%CAPACTITY;if(table[index]==null){returnnull;}else{for(Entry<K,V>entry=table[index];entry!=null;entry=entry.nextEntry){if(entry.hashCode==hashCode&&(entry.key==key||key.equals(entry.key))){returnentry.value;}}returnnull;}}/*刪除*/publicvoidremove(Kkey){inthashCode=this.