go語言中bit數(shù)組 go struct 數(shù)組

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

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

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

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

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

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

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

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

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

2、var arr []int? ? 這時arr就是一個slice 切片 。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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ù)組，定義前綴和后綴兩個操作。后綴一般在初始化和更新BIT數(shù)組中使用，前綴是為了求和的時候跳過重復(fù)的元素。

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

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

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

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

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

前綴一般在求和的過程中會用到。

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

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

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

廣告

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