【golang】海量数据去重-布隆过滤器

在做域名爆破中，遇到了把一个300G的子域名json文件进行去重，一开始是考虑使用字典进行去重，但是数据量大了，会造成内存泄露。看网上资料介绍了一种方案，就是使用布隆过滤器。

在红安等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供网站制作、做网站 网站设计制作按需求定制设计,公司网站建设,企业网站建设,品牌网站建设,成都全网营销推广,成都外贸网站建设,红安网站建设费用合理。

布隆过滤器是一种数据结构，概率型数据结构，特定是高效插入和查询，可以用来告诉你“某一值一定不存在或者kennel存在”。

相比于传统的map、set等数据结构，占用空间更少，但其返回结果是概率型的，不确定。

布隆过滤器内部维护一个bitArray(位数组)，开始所有数据为0，当一个元素过来时，能过多个哈希函数（hash1、hash2、hash3）计算不同的hash值，并通过hash值找到bitArray的下标，将里面的值改为由0变为1。布隆过滤器有一个误判率，误判率越低，数组越长，所在空间越大，误判率越高，数组越小，所占空间越小。

这里贴上一个技术大牛的博客地址，里面对布隆过滤器用法以及在redis里面处理缓存穿透问题的详细介绍。

go语言中数组使用的注意事项和细节

1、数组是多个 相同类型 的数据的组合，一个数组一旦声明/定义了，其 长度是固定的，不能动态变化 。

2、var arr []int    这时arr就是一个slice 切片 。

3、数组中的元素可以是任何数据类型，包括值类型和引用类型，但是 不能混用 。

4、数组创建后，如果没有赋值，有默认值如下：

    数值类型数组：    默认值为 0

    字符串数组：       默认值为 ""

    bool数组：           默认值为 false

5、使用数组的步骤：

    (1)声明数组并开辟空间

    (3)给数组各个元素赋值

    (3)使用数组

6、数组的下标是从0开始的。

7、数组下标必须在指定范围内使用，否则报panic:数组越界，比如var arr [5]int的有效下标为0~4.

8、Go的数组属于 值类型 ，在默认情况下是 值传递 ，因此会进行值拷贝。 数组间不会相互影响。

9、如想在其他函数中去修改原来的数组，可以使用 引用传递 (指针方式)。

10、长度是数组类型的一部分，在传递函数参数时，需要考虑数组的长度，看以下案例：

题1：编译错误，因为不能把[3]int类型传递给[]int类型，前者是数组，后者是切片；

题2：编译错误，因为不能把[3]int类型传递给[4]int类型；

题3：编译正确，因为[3]int类型传给[3]int类型合法。

BIT数据结构

定义数组array[n]，求数组array[i]到array[j]的和(部分和)。在这种情况下，用一个简单的遍历可以解决问题，复杂度为O(n)。如果这种操作执行了m次，那么复杂度为O(mn)，而树状数组可以把复杂度降至O(m*logn)，适用于更新少但是部分和操作次数多的场景。

树状数组(Binary Indexed Tree)，本质就是一种通过二进制位来维护一个序列前i个和的数据结构，所以在其实更应该直白地翻译为二进制索引树。树状数组的索引都是以1开始，首先看一个例子。

设原始数组为a[8] = {3,4,5,6,7,8,9,2}，那么树状数组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]

为了方便构造和使用树状数组，定义前缀和后缀两个操作。后缀一般在初始化和更新BIT数组中使用，前缀是为了求和的时候跳过重复的元素。

i的后缀为最为靠近i，且二进制末尾连续0的个数比i多的坐标。如e[2(10)]的后缀为e[4(100)]，e[4(100)]的后缀为e[8(1000)]。后缀主要用来 构造和更新树状数组 。

后缀的计算公式为:

可以通过一次完整的扫描即可构造出树状数组，扫描的过程中每次去更新当前值的后缀即可。

如果其中某一项发生改变，只需要更新一下与之相关的后缀的值。

前缀的计算公式为：

前缀一般在求和的过程中会用到。

后缀是为了不重复计算元素，因为在BIT数组中每一项都是原始数组的一个或者多个的和。

本文名称：go语言中bit数组 go struct 数组
分享路径：http://myzitong.com/article/dohpcjo.html