安装:
go get github.com/bits-and-blooms/bitset
下面代码把fmtx换成fmt就行
//------------基本操作------------
//构建一个64bit长度的bitset
b := bitset.New(64)
//放入一个数
b.Set(10)
fmtx.Println("add-10:", b.DumpAsBits()) // 0000000000000000000000000000000000000000000000000000010000000000
//删除一个值
b.Set(12)
b.Clear(10)
fmtx.Println("del-10:", b.DumpAsBits()) //0000000000000000000000000000000000000000000000000001000000000000
//测试
b.Set(2).Set(6)
fmtx.Println("add-2-6:", b.DumpAsBits()) //0000000000000000000000000000000000000000000000000001000001000100
fmtx.Println("test2:", b.Test(2), " test5:", b.Test(5)) //[test2: true test5: false]
b.Set(2) //重复设置
fmtx.Println("test2:", b.Test(2), " adds2:", b.DumpAsBits()) //[test2: true adds2: 0000000000000000000000000000000000000000000000000001000001000100.]
//----------------指定位置操作---------------
//指定位置操作
a := &bitset.BitSet{}
a.Set(3)
//在指定位置插入0
a.InsertAt(3)
fmtx.Println("指定位置插入0:", a.DumpAsBits()) //0000000000000000000000000000000000000000000000000000000000010000
//在指定位置需改
a.SetTo(4, false)
fmtx.Println("指定位置4修改false:", a.DumpAsBits()) //0000000000000000000000000000000000000000000000000000000000000000
a.Set(63)
fmtx.Println("指定位置63修改true:", a.DumpAsBits()) //1000000000000000000000000000000000000000000000000000000000000000
a.Set(3).DeleteAt(3) //删除了就全都往右移了
fmtx.Println("指定位置3删除:", a.DumpAsBits()) //0100000000000000000000000000000000000000000000000000000000000000
a.Set(63)
fmtx.Println("再指定位置63:", a.DumpAsBits()) //1100000000000000000000000000000000000000000000000000000000000000
//---------------两个bitsets交互----------------
k := &bitset.BitSet{}
j := &bitset.BitSet{}
k.Set(1).Set(3).Set(5)
j.Set(7).Set(3).Set(5)
//交集
fmtx.Println(k.Intersection(j)) //{3,5}
//并集
fmtx.Println(k.Union(j)) //{1,3,5,7}
//差集
fmtx.Println(k.Difference(j)) //{1}
//全等
fmtx.Println(k.Equal(j)) // false
//遍历
arr := bitset.New(64)
arr.Set(1).Set(3).Set(5).Set(7)
for i, e := arr.NextSet(0); e; i, e = arr.NextSet(i + 1) {
fmtx.Println(i) // 1 3 5 7
}
布隆过滤器-假阳性率计算公式
可知在哈希函数的个数k一定的情况下:
- 位数组长度m越大,假阳性率越低;
- 已插入元素的个数n越大,假阳性率越高。
布隆过滤器
把fmtx删掉就行文章来源:https://www.toymoban.com/news/detail-645878.html
package filter
import (
"crypto/hmac"
"crypto/rand"
"crypto/sha1"
"demo/pkg/fmtx"
"encoding/binary"
"github.com/bits-and-blooms/bitset"
"math"
"math/big"
)
// CalBloomSize a
// elemNum 元素个数
// errorRate 误判率
// 布隆过滤器的位图大小计算公式为:m = -(n * log(p)) / (log(2))^2,其中m是位数组的大小,n是期望插入元素的数量,p是允许的误报率。
func CalBloomSize(elemNum uint64, errRate float64) uint64 {
var bloomBitsSize = float64(elemNum) * math.Log(errRate) / (math.Log(2) * math.Log(2)) * (-1)
fmtx.Println("bloomBitsSize:", bloomBitsSize)
return uint64(math.Ceil(bloomBitsSize))
}
// CalHashFuncNum 计算需要的哈希函数数量
// elemNum 元素个数
// bloomSize 布隆过滤器位图大小
// 哈希函数数量计算公式为:k = -m/n * log(p) 哈希函数的数量不能过多,否则会增加计算时间和空间消耗。
func CalHashFuncNum(elemNum, bloomSize uint64) uint64 {
var k = math.Log(2) * float64(bloomSize) / float64(elemNum)
fmtx.Println("k:", k)
return uint64(math.Ceil(k))
}
// Filter
type Filter struct {
ElemNum uint64 //元素个数
BloomSize uint64 //布隆过滤器位图大小
HashFuncNum uint64 //计算需要的哈希函数数量
ErrRate float64 //误判率
bitMap *bitset.BitSet
keys map[uint32]bool
}
// NewFilter NewFilter
func NewFilter(elemNum, bloomSize, hashFuncNum uint64, errRate float64) *Filter {
return &Filter{ElemNum: elemNum, BloomSize: bloomSize, HashFuncNum: hashFuncNum, ErrRate: errRate}
}
// Init 初始化布隆过滤器
func (f *Filter) Init() {
fmtx.Println("Filter-Init:")
// 分配布隆过滤器位图
f.bitMap = bitset.New(uint(f.BloomSize))
// 初始化哈希函数
// 是否是类似HMAC-SHA256那种通过改变passphase值形成不同的哈希函数
f.keys = make(map[uint32]bool)
for uint64(len(f.keys)) < f.HashFuncNum {
randNum, err := rand.Int(rand.Reader, new(big.Int).SetUint64(math.MaxUint32))
if err != nil {
panic(err)
}
f.keys[uint32(randNum.Uint64())] = true
}
fmtx.Println(f.keys)
}
// Add Add
func (f *Filter) Add(elem []byte) {
var buf [4]byte
for k := range f.keys {
binary.LittleEndian.PutUint32(buf[:], k)
fmtx.Println("hmac:", HMACWithSHA128(elem, buf[:]), HMACWithSHA128(elem, buf[:]))
hashResult := new(big.Int).SetBytes(HMACWithSHA128(elem, buf[:]))
result := hashResult.Mod(hashResult, big.NewInt(int64(f.BloomSize)))
// 把result对应的bit置1
f.bitMap.Set(uint(result.Uint64()))
}
}
// IsContain 判断元素是否在集合里面
func (f *Filter) IsContain(elem []byte) bool {
var buf [4]byte
for k := range f.keys {
binary.LittleEndian.PutUint32(buf[:], k)
hashResult := new(big.Int).SetBytes(HMACWithSHA128(elem, buf[:]))
result := hashResult.Mod(hashResult, big.NewInt(int64(f.BloomSize)))
// 查询result对应的bit是否被置1
if !f.bitMap.Test(uint(result.Uint64())) {
return false
}
}
return true
}
// HMACWithSHA128 通过加盐生成不同的hash值
func HMACWithSHA128(seed []byte, key []byte) []byte {
hmac512 := hmac.New(sha1.New, key)
hmac512.Write(seed)
return hmac512.Sum(nil)
}
目录格式
使用文章来源地址https://www.toymoban.com/news/detail-645878.html
elemNum := uint64(100000000) //元素个数
errorRate := 0.00001 //假阳率
bloomSize := filter.CalBloomSize(elemNum, errorRate) //布隆过滤器位图大小
hashFuncNum := filter.CalHashFuncNum(elemNum, bloomSize) //哈希函数数量
fmtx.Println("bloomSize:", bloomSize, "hashFuncNum:", hashFuncNum)
bl := filter.NewFilter(elemNum, bloomSize, hashFuncNum, errorRate)
bl.Init()
ha := "haha"
bl.Add([]byte(ha))
if bl.IsContain([]byte(ha)) {
fmtx.Println(ha, "ok")
}
到了这里,关于Golang bitset 基本使用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!