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

java代碼實現(xiàn)如下importjava.util.ArrayList;importjava.util.BitSet;importjava.util.List;/***BloomFilter算法**@authorJYC506**/publicclassBloomFilter{/*哈希函數(shù)*/privateList<IHashFunction>hashFuctionList;/*構造方法*/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個哈希函數(shù)*/bloomFilter.addHashFunction(newJavaHash());bloomFilter.addHashFunction(newRSHash());bloomFilter.addHashFunction(newSDBMHash());/*長度為2的24次方*/BitSetbitSet=newBitSet(1<<25);/*判斷test1很test2重復的字符串*/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+"'是重復的");}}}}/*哈希函數(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)計+堆/快速/歸并排序百度面試題1、海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個IP。IP是32位的，最多有個2^32個IP。同樣可以采用映射的方法，比如模1000，把整個大文件映射為1000個小文件，再找出每個小文中出現(xiàn)頻率最大的IP（可以采用hash_map進行頻率統(tǒng)計，然后再找出頻率最大的幾個）及相應的頻率。然后再在這1000個最大的IP中，找出那個頻率最大的IP，即為所求。百度面試題2、搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節(jié)。假設目前有一千萬個記錄（這些查詢串的重復度比較高，雖然總數(shù)是1千萬，但如果除去重復后，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門。），請你統(tǒng)計最熱門的10個查詢串，要求使用的內(nèi)存不能超過1G。第一步借用hash統(tǒng)計進行預處理：先對這批海量數(shù)據(jù)預處理(維護一個Key為Query字串，Value為該Query出現(xiàn)次數(shù)，即Hashmap(Query，Value)，每次讀取一個Query，如果該字串不在Table中，那么加入該字串，并且將Value值設為1；如果該字串在Table中，那么將該字串的計數(shù)加一即可。最終我們在O(N)（N為1千萬，因為要遍歷整個數(shù)組一遍才能統(tǒng)計處每個query出現(xiàn)的次數(shù)）的時間復雜度內(nèi)用Hash表完成了統(tǒng)計；

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

最終的時間復雜度是：O（N）+N'*O（logK），（N為1000萬，N’為300萬）或者：采用trie樹，關鍵字域存該查詢串出現(xiàn)的次數(shù)，沒有出現(xiàn)為0。最后用10個元素的最小推來對出現(xiàn)頻率進行排序。我們先看HashMap實現(xiàn)1.HashMap的數(shù)據(jù)結構數(shù)據(jù)結構中有數(shù)組和鏈表來實現(xiàn)對數(shù)據(jù)的存儲，但這兩者基本上是兩個極端。數(shù)組數(shù)組存儲區(qū)間是連續(xù)的，占用內(nèi)存嚴重，故空間復雜的很大。但數(shù)組的二分查找時間復雜度小，為O(1)；數(shù)組的特點是：尋址容易，插入和刪除困難；鏈表鏈表存儲區(qū)間離散，占用內(nèi)存比較寬松，故空間復雜度很小，但時間復雜度很大，達O（N）。鏈表的特點是：尋址困難，插入和刪除容易。哈希表那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數(shù)據(jù)結構？答案是肯定的，這就是我們要提起的哈希表。哈希表（(Hashtable）既滿足了數(shù)據(jù)的查找方便，同時不占用太多的內(nèi)容空間，使用也十分方便。哈希表有多種不同的實現(xiàn)方法，我接下來解釋的是最常用的一種方法——拉鏈法，我們可以理解為“鏈表的數(shù)組”我用java自己實現(xiàn)了一個HashMap，當然這比較簡點，不過能說明大概原理，改有的功能基本上有了index=hashCode(key)=key％16哈希算法很多，下面我用了java自帶的，當然你也可以用別的/***自定義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.