海量數(shù)據(jù)處理：

1.top k問題

海量數(shù)據(jù)中找出最大的前k個數(shù)（或者最小的前k個數(shù)）
一般的套路是：
hash分割數(shù)據(jù)集+trie樹/hash統(tǒng)計出詞頻+小頂堆
（1）使用hash的方法將數(shù)據(jù)集分成多個小的數(shù)據(jù)集
（2）使用tire樹或者h(yuǎn)ash統(tǒng)計出每個小數(shù)據(jù)集中的詞頻
（3）之后用小頂堆求出數(shù)據(jù)集中頻率最高k個數(shù)，最后在所有的top k中求出最中的top k

• 看常見案例：1億個浮點(diǎn)數(shù)，如何找出其中最大的1000個數(shù)？
  （1）直接排序法
  （2）局部淘汰：用一個長度為1000的數(shù)組，逐個遍歷所有的數(shù)據(jù)，將最大的1000個放入數(shù)組中，時間復(fù)雜度O （n+m^2）
  ————————————————————————————————————
  前兩種不是很好的解決方案，面試官不會喜歡的
  （3）分治法 ，將大文件劃分成若干個小文件，找出每份中最大的1000個，再從所有的最大1000個中找出最大的1000個；
  - 從文件中找出最大的1000個，利用快排的思想，將浮點(diǎn)數(shù)一分為二，不斷的一分為二，直到左側(cè)是最大的1000個數(shù)為止
  （4）最小堆法：讀入1000個數(shù)構(gòu)建小頂堆（O(mlogm)）,然后，便利剩余的數(shù)，比堆頂數(shù)字大則替換掉堆頂?shù)臄?shù)字然后重新調(diào)整最小堆。然后中序遍歷一下，得到最大的1000個數(shù)。O（nmlogm），空間復(fù)雜度是常數(shù)。
  ps：可以用hash法預(yù)處理一下，將重復(fù)的數(shù)字去掉，如果重復(fù)的數(shù)字很多的話，可以節(jié)省大量的運(yùn)算內(nèi)存空間。去重完畢后，再使用分治法和最小堆法處理。

當(dāng)然，實(shí)際問題中，還是需要根據(jù)到內(nèi)存大小和數(shù)據(jù)量來選擇處理方法。

topk還有其應(yīng)用場景：
例如 統(tǒng)計搜索熱度最高的前10的詞。
思路：（1）分治，將文件分成很多小文件（2）用hash的方法統(tǒng)計出每個小文件中詞的頻率（3）建容量為10 的小頂堆：首先輸入前位數(shù)，遍歷剩余的文件，比堆頂大則替換，最終得到最大的10個數(shù)。（4）合并結(jié)果后再用最小堆找出前十的詞。

2.重復(fù)問題

找出大數(shù)據(jù)量下的重復(fù)元素或者去重的需求，一般用位圖（bitmap）的方式實(shí)現(xiàn)。

如題：一個文件，里面存儲了大量的電話號碼，每個號碼都是8位的數(shù)字，請統(tǒng)計不同號碼的個數(shù)。

解：8位數(shù)字能表示最大的數(shù)字是99999999,如果每個數(shù)字對應(yīng)位圖中的一位，需要申請99999999位即約99Mbit的內(nèi)存，折合99/8MB的內(nèi)存。
（2）遍歷號碼，在對應(yīng)的數(shù)組下標(biāo)置為1，遍歷完文件后；位圖上置為1的下標(biāo)就表示該號碼存在。輸出置為1的個數(shù)即可。

類似問題：
1）10億個整數(shù)，只有一個數(shù)重復(fù)出現(xiàn)過，O（n）的時間復(fù)雜度內(nèi)找出這個數(shù)
思路：
1.bitmap法：申請一個長度為Int最大值的bit數(shù)組，按行讀文件，若該位置已經(jīng)是1了，你則說明重復(fù)了。
2.分治法，使用hash份成1000份小文件，重復(fù)的數(shù)肯定會分在一個文件里。分別用hashMap處理每個小文件。

2）給兩個文件，每個文件存了50億的url，每個url占64Byte，在O（n）時間里找出兩個文件相同的url
思路：（1）將每個urlhashcode % 1000，切割成很多小文件；（2）hash后，相同的url肯定都落到了相同的小文件中。（3）遍歷a0文件，存入hashMap，再遍歷b文件，如果hashmap中存在的，則表示有相同的url。

3）給40億個無符號整數(shù)，給定一個數(shù)，快速判斷這個數(shù)是不是在這些數(shù)字里？
思路1:bitmap法
思路2:
（1）無符號整數(shù)最大是32位，也就是40億的數(shù)字都可以表示成32位二進(jìn)制的串，將給定的數(shù)字用32位二進(jìn)制表示，得到一個0、1串
（2）將首位位0和首位為1的數(shù)字分成兩個文件；在首位與給定數(shù)一致的文件里再分次位為0和次位為1兩個文件，直到最后找到這個數(shù)為止 （O（lgn））

3.排序問題

示例：9億個不重復(fù)的8位數(shù)，請排序：
思路：最大數(shù)位99999999 ，位圖法，申請一個可以包含8位整數(shù)個的數(shù)組，長度為1億的bit數(shù)組，挨個讀文件，讀出數(shù)字，在對應(yīng)的位上置為1。遍歷整個數(shù)組，將bit為1的下標(biāo)存入文件，最終得到了排序的結(jié)果。

布隆過濾器：

思想：
準(zhǔn)備條件：
1.長度為m的bit數(shù)組
2.k個hash算法黑名單字符串集合
構(gòu)建布隆過濾器
1.遍歷黑名單集合
2.每一條數(shù)據(jù)計算k個hash函數(shù)，hashcode取m模后落到數(shù)組的某一位置為1
3.循環(huán)遍歷集合后m長度的數(shù)組中就有若干為置為了1
檢測字符串str
1.一次計算k個hash函數(shù)，對m取模
2.如果沒有落到值為1的位置，則肯定不是黑詞
3.如果每個結(jié)果都落到了值為1的位置，則有可能是黑詞。（對于結(jié)果不準(zhǔn)的情況，可以將可能的值再精確匹配一次）

image.png

幾個實(shí)例：

• 1.一個8g的文件，每一行是一個整型數(shù)字，服務(wù)器的內(nèi)存是2g，怎么得到文件里重復(fù)出現(xiàn)的數(shù)字
  思路1：位圖法，申請一個長度為最大整數(shù)的bit數(shù)組，挨個讀取文件，將對應(yīng)數(shù)字下標(biāo)的數(shù)組標(biāo)記為1，如果遇到該位置已經(jīng)是1的，輸出下標(biāo)到文件中。這就是重復(fù)了的數(shù)字。
  思路2:分治法，將數(shù)字取模%1000，分為1000個小文件，每個文件處理，將數(shù)字存入hashmap，輸出重復(fù)的數(shù)字到文件中。因?yàn)槭侨∧２僮?，所以重?fù)的數(shù)字肯定是落到了同一個文件中的。

• 思路拓展

• （1）很多數(shù)，超過了整數(shù)的界限，其中有一個數(shù)出現(xiàn)過一次，其余都是出現(xiàn)過兩次，找出這個數(shù)？
  思路：遍歷，將所有的數(shù)做異或，遍歷結(jié)束后，出現(xiàn)兩次的數(shù)都抵消了，剩下的數(shù)就是自己了。（自己與自己做異或運(yùn)算是0）
  case：舉個栗子：2 3 4 2 3
  所有數(shù)字依次異或運(yùn)算：2 xor 3 xor 4 xor 2 xor 3 = (2 xor 2) xor (3 xor 3) xor 4= 0 xor 0 xor 4 = 4

• （2）一年的全國高考考生人數(shù)為500 萬，分?jǐn)?shù)使用標(biāo)準(zhǔn)分，最低100 ，最高900 ，沒有小數(shù)，要求對這500 萬元素的數(shù)組進(jìn)行排序。
  思路：桶排序，因?yàn)榉謹(jǐn)?shù)分布在100～900之間，創(chuàng)建801個桶并編號，遍歷500個數(shù)，丟入到對應(yīng)的桶中，這樣就可以排出所有人的分?jǐn)?shù)了。
  注：與位圖法有點(diǎn)類似，就是：下標(biāo)=數(shù)字值。