【golang】海量數(shù)據(jù)去重-布隆過(guò)濾器

在做域名爆破中，遇到了把一個(gè)300G的子域名json文件進(jìn)行去重，一開(kāi)始是考慮使用字典進(jìn)行去重，但是數(shù)據(jù)量大了，會(huì)造成內(nèi)存泄露?？淳W(wǎng)上資料介紹了一種方案，就是使用布隆過(guò)濾器。

在紅安等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專(zhuān)注、極致的服務(wù)理念，為客戶提供網(wǎng)站制作、做網(wǎng)站 網(wǎng)站設(shè)計(jì)制作按需求定制設(shè)計(jì),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站建設(shè),成都全網(wǎng)營(yíng)銷(xiāo)推廣,成都外貿(mào)網(wǎng)站建設(shè),紅安網(wǎng)站建設(shè)費(fèi)用合理。

布隆過(guò)濾器是一種數(shù)據(jù)結(jié)構(gòu)，概率型數(shù)據(jù)結(jié)構(gòu)，特定是高效插入和查詢，可以用來(lái)告訴你“某一值一定不存在或者kennel存在”。

相比于傳統(tǒng)的map、set等數(shù)據(jù)結(jié)構(gòu)，占用空間更少，但其返回結(jié)果是概率型的，不確定。

布隆過(guò)濾器內(nèi)部維護(hù)一個(gè)bitArray(位數(shù)組)，開(kāi)始所有數(shù)據(jù)為0，當(dāng)一個(gè)元素過(guò)來(lái)時(shí)，能過(guò)多個(gè)哈希函數(shù)（hash1、hash2、hash3）計(jì)算不同的hash值，并通過(guò)hash值找到bitArray的下標(biāo)，將里面的值改為由0變?yōu)?。布隆過(guò)濾器有一個(gè)誤判率，誤判率越低，數(shù)組越長(zhǎng)，所在空間越大，誤判率越高，數(shù)組越小，所占空間越小。

這里貼上一個(gè)技術(shù)大牛的博客地址，里面對(duì)布隆過(guò)濾器用法以及在redis里面處理緩存穿透問(wèn)題的詳細(xì)介紹。

go語(yǔ)言中數(shù)組使用的注意事項(xiàng)和細(xì)節(jié)

1、數(shù)組是多個(gè) 相同類(lèi)型 的數(shù)據(jù)的組合，一個(gè)數(shù)組一旦聲明/定義了，其 長(zhǎng)度是固定的，不能動(dòng)態(tài)變化 。

2、var arr []int? ? 這時(shí)arr就是一個(gè)slice 切片 。

3、數(shù)組中的元素可以是任何數(shù)據(jù)類(lèi)型，包括值類(lèi)型和引用類(lèi)型，但是 不能混用 。

4、數(shù)組創(chuàng)建后，如果沒(méi)有賦值，有默認(rèn)值如下：

? ? 數(shù)值類(lèi)型數(shù)組：????默認(rèn)值為 0

? ? 字符串?dāng)?shù)組：? ? ? ?默認(rèn)值為 ""

? ? bool數(shù)組：? ? ? ? ? ?默認(rèn)值為 false

5、使用數(shù)組的步驟：

? ? (1)聲明數(shù)組并開(kāi)辟空間

? ? (3)給數(shù)組各個(gè)元素賦值

? ? (3)使用數(shù)組

6、數(shù)組的下標(biāo)是從0開(kāi)始的。

7、數(shù)組下標(biāo)必須在指定范圍內(nèi)使用，否則報(bào)panic:數(shù)組越界，比如var arr [5]int的有效下標(biāo)為0~4.

8、Go的數(shù)組屬于 值類(lèi)型 ，在默認(rèn)情況下是 值傳遞 ，因此會(huì)進(jìn)行值拷貝。 數(shù)組間不會(huì)相互影響。

9、如想在其他函數(shù)中去修改原來(lái)的數(shù)組，可以使用 引用傳遞 (指針?lè)绞?。

10、長(zhǎng)度是數(shù)組類(lèi)型的一部分，在傳遞函數(shù)參數(shù)時(shí)，需要考慮數(shù)組的長(zhǎng)度，看以下案例：

題1：編譯錯(cuò)誤，因?yàn)椴荒馨裑3]int類(lèi)型傳遞給[]int類(lèi)型，前者是數(shù)組，后者是切片；

題2：編譯錯(cuò)誤，因?yàn)椴荒馨裑3]int類(lèi)型傳遞給[4]int類(lèi)型；

題3：編譯正確，因?yàn)閇3]int類(lèi)型傳給[3]int類(lèi)型合法。

BIT數(shù)據(jù)結(jié)構(gòu)

定義數(shù)組array[n]，求數(shù)組array[i]到array[j]的和(部分和)。在這種情況下，用一個(gè)簡(jiǎn)單的遍歷可以解決問(wèn)題，復(fù)雜度為O(n)。如果這種操作執(zhí)行了m次，那么復(fù)雜度為O(mn)，而樹(shù)狀數(shù)組可以把復(fù)雜度降至O(m*logn)，適用于更新少但是部分和操作次數(shù)多的場(chǎng)景。

樹(shù)狀數(shù)組(Binary Indexed Tree)，本質(zhì)就是一種通過(guò)二進(jìn)制位來(lái)維護(hù)一個(gè)序列前i個(gè)和的數(shù)據(jù)結(jié)構(gòu)，所以在其實(shí)更應(yīng)該直白地翻譯為二進(jìn)制索引樹(shù)。樹(shù)狀數(shù)組的索引都是以1開(kāi)始，首先看一個(gè)例子。

設(shè)原始數(shù)組為a[8] = {3,4,5,6,7,8,9,2}，那么樹(shù)狀數(shù)組e可以通過(guò)如下方式得到：

e[1] = a[1]

e[2] = a[1]+a[2]

e[3] = a[3]

e[4] = a[1]+a[2]+a[3]+a[4]=e[1]+e[2]+e[3]

e[5] = a[5]

e[6] = a[5]+a[6]

e[7] = a[7]

e[8] = a[1]+a[2]+...+a[8]

解釋如下：

例如：e[8(1000)] = a[1]+a[2]+...+a[8]

為了方便構(gòu)造和使用樹(shù)狀數(shù)組，定義前綴和后綴兩個(gè)操作。后綴一般在初始化和更新BIT數(shù)組中使用，前綴是為了求和的時(shí)候跳過(guò)重復(fù)的元素。

i的后綴為最為靠近i，且二進(jìn)制末尾連續(xù)0的個(gè)數(shù)比i多的坐標(biāo)。如e[2(10)]的后綴為e[4(100)]，e[4(100)]的后綴為e[8(1000)]。后綴主要用來(lái) 構(gòu)造和更新樹(shù)狀數(shù)組 。

后綴的計(jì)算公式為:

可以通過(guò)一次完整的掃描即可構(gòu)造出樹(shù)狀數(shù)組，掃描的過(guò)程中每次去更新當(dāng)前值的后綴即可。

如果其中某一項(xiàng)發(fā)生改變，只需要更新一下與之相關(guān)的后綴的值。

前綴的計(jì)算公式為：

前綴一般在求和的過(guò)程中會(huì)用到。

后綴是為了不重復(fù)計(jì)算元素，因?yàn)樵贐IT數(shù)組中每一項(xiàng)都是原始數(shù)組的一個(gè)或者多個(gè)的和。

新聞名稱：go語(yǔ)言中bit數(shù)組 go struct 數(shù)組
瀏覽路徑：http://jinyejixie.com/article20/dohpcjo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶體驗(yàn)、面包屑導(dǎo)航、動(dòng)態(tài)網(wǎng)站、云服務(wù)器、搜索引擎優(yōu)化、App設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)