現(xiàn)在需要對(duì)數(shù)據(jù)按用戶分析，但當(dāng)中有大量的重復(fù)數(shù)據(jù)，僅用數(shù)據(jù)庫的等值去重明顯不可行。

對(duì)數(shù)據(jù)內(nèi)容求MD5值

• MD5值的特點(diǎn)：
  1.壓縮性：任意長度的數(shù)據(jù)，算出的MD5值長度都是固定的。
  2.容易計(jì)算：從原數(shù)據(jù)計(jì)算出MD5值很容易。
  3.抗修改性：對(duì)原數(shù)據(jù)進(jìn)行任何改動(dòng)，哪怕只修改1個(gè)字節(jié)，所得到的MD5值都有很大區(qū)別。
  4.強(qiáng)抗碰撞：已知原數(shù)據(jù)和其MD5值，想找到一個(gè)具有相同MD5值的數(shù)據(jù)（即偽造數(shù)據(jù)）是非常困難的。

根據(jù)MD5值的特點(diǎn)，對(duì)每條記錄的維度數(shù)據(jù)內(nèi)容計(jì)算MD5值，然后根據(jù)MD5值判斷重復(fù)記錄。

對(duì)數(shù)據(jù)入庫之后利用sql直接查出重復(fù)數(shù)據(jù)，然后將重復(fù)數(shù)據(jù)移除或者標(biāo)記。

至少在現(xiàn)階段內(nèi)存和CPU的執(zhí)行效率在固定時(shí)間內(nèi)是有限的，大量的數(shù)據(jù)的查重和去重處理不可能同時(shí)在內(nèi)存中進(jìn)行。就像外部排序算法和內(nèi)部排序算法差別很大，遇到此類大量數(shù)據(jù)查重問題對(duì)算法進(jìn)行設(shè)計(jì)是有必要的。

布隆過濾器

布隆過濾器是一種采用hash法進(jìn)行查重的工具。它將每一條數(shù)據(jù)進(jìn)行n次獨(dú)立的hash處理，每次處理得到一個(gè)整數(shù)，總共得到n個(gè)整數(shù)。使用一個(gè)很長的數(shù)組表示不同的整數(shù)，每一次插入操作把這n個(gè)整數(shù)對(duì)應(yīng)的位置的0設(shè)置為1（如果已經(jīng)被設(shè)置為1則不變）。下次查找的時(shí)候經(jīng)過同樣的計(jì)算，如果這幾個(gè)位置都是1則說明已經(jīng)存在。

布隆過濾器的優(yōu)點(diǎn)是使用方便，因?yàn)椴⒉粚ey存放進(jìn)內(nèi)存所以十分節(jié)省空間，多個(gè)hash算法無關(guān)，可以并發(fā)執(zhí)行效率高。缺點(diǎn)也是顯而易見的，這種算法是可能出現(xiàn)錯(cuò)誤，有誤判率這種概念。通過hash的次數(shù)我們可以降低誤判率，但是不能保證沒有誤判的情況。

BitMap　

比如有2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)。 

一個(gè)數(shù)字的狀態(tài)只有三種，分別為不存在，只有一個(gè)，有重復(fù)。因此，我們只需要2bits就可以對(duì)一個(gè)數(shù)字的狀態(tài)進(jìn)行存儲(chǔ)了，假設(shè)我們?cè)O(shè)定一個(gè)數(shù)字不存在為00，存在一次01，存在兩次及其以上為11。那我們大概需要存儲(chǔ)空間幾十兆左右。接下來的任務(wù)就是遍歷一次這2.5億個(gè)數(shù)字，如果對(duì)應(yīng)的狀態(tài)位為00，則將其變?yōu)?1；如果對(duì)應(yīng)的狀態(tài)位為01，則將其變?yōu)?1；如果為11，,對(duì)應(yīng)的轉(zhuǎn)態(tài)位保持不變。

最后，我們將狀態(tài)位為01的進(jìn)行統(tǒng)計(jì)，就得到了不重復(fù)的數(shù)字個(gè)數(shù)，時(shí)間復(fù)雜度為O(n)。

hash分組

如果有兩份50G的數(shù)據(jù)，要查重，內(nèi)存4G，怎么查？

想法是先將50G的數(shù)據(jù)分別做hash%1000，分成1000個(gè)文件，理論上hash做得好那么這1000個(gè)文件的大小是差不多接近的。如果有重復(fù)，那么A和B的重復(fù)數(shù)據(jù)一定在相對(duì)同一個(gè)文件內(nèi)，因?yàn)閔ash結(jié)果是一樣的。將1000個(gè)文件分別加載進(jìn)來，一一比對(duì)是否有hash重復(fù)。這種想法是先把所有數(shù)據(jù)按照相關(guān)性進(jìn)行分組，相關(guān)的數(shù)據(jù)會(huì)處于同樣或者接近的位置中，再將小文件進(jìn)行對(duì)比。

有1千萬條短信，找出重復(fù)出現(xiàn)最多的前10條？

可以用哈希表的方法對(duì)1千萬條分成若干組進(jìn)行邊掃描邊建散列表。第一次掃描，取首字節(jié)，尾字節(jié)，中間隨便兩字節(jié)作為Hash Code，插入到hash table中。并記錄其地址和信息長度和重復(fù)次數(shù)，1千萬條信息，記錄這幾個(gè)信息還放得下。同Hash Code且等長就疑似相同，比較一下。相同記錄只加1次進(jìn)hash table，但將重復(fù)次數(shù)加1。一次掃描以后，已經(jīng)記錄各自的重復(fù)次數(shù)，進(jìn)行第二次hash table的處理。用線性時(shí)間選擇可在O（n）的級(jí)別上完成前10條的尋找。分組后每份中的top10必須保證各不相同，可hash來保證，也可直接按hash值的大小來分類。

使用數(shù)據(jù)庫建立關(guān)鍵字段（一個(gè)或者多個(gè)）建立索引進(jìn)行去重

根據(jù)url地址進(jìn)行去重

使用場(chǎng)景：url地址對(duì)應(yīng)的數(shù)據(jù)不會(huì)變的情況，url地址能夠唯一判別一條數(shù)據(jù)的情況

思路：

　　url存在Redis中

　　拿到url地址，判斷url在Redis的集合中是否存在

　　　　存在：說明url地址已經(jīng)被請(qǐng)求過了，不在請(qǐng)求

　　　　不存在：說明url地址沒有被請(qǐng)求過，請(qǐng)求，把該url地址存入Redis的集合中

布隆過濾器：

　　使用多個(gè)加密算法加密url地址，得到多個(gè)值

　　往對(duì)應(yīng)值的位置把結(jié)果設(shè)置為1

　　新來的一個(gè)url地址，一樣通過加密算法生成多個(gè)值

　　　　如果對(duì)應(yīng)位置的值全為1，說明這個(gè)url地址已經(jīng)被抓取過了

　　　　否則沒有被抓取過，就把對(duì)應(yīng)的位置的值設(shè)置為1

根據(jù)數(shù)據(jù)本身進(jìn)行去重：

　　選擇特定的字段（能夠唯一標(biāo)識(shí)數(shù)據(jù)的字段），使用加密算法（MD5，sha1）將字段進(jìn)行加密，生成字符串，存入Redis的集合中

　　后續(xù)新來一條數(shù)據(jù)，同樣的方式進(jìn)行加密，

　　　　如果得到的字符串在Redis中存在，說明數(shù)據(jù)存在，對(duì)數(shù)據(jù)進(jìn)行更新，

　　　　否則說明數(shù)據(jù)不存在，對(duì)數(shù)據(jù)進(jìn)行插入。