Golang bitset 基本使用

这篇具有很好参考价值的文章主要介绍了Golang bitset 基本使用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

安装:

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
	}

布隆过滤器-假阳性率计算公式
Golang bitset 基本使用,go,golang,开发语言,后端
可知在哈希函数的个数k一定的情况下:

  • 位数组长度m越大,假阳性率越低;
  • 已插入元素的个数n越大,假阳性率越高。

布隆过滤器

把fmtx删掉就行

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)
}

目录格式
Golang bitset 基本使用,go,golang,开发语言,后端
使用文章来源地址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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Golang】Golang进阶系列教程--为什么 Go 语言 struct 要使用 tags

    在 Go 语言中,struct 是一种常见的数据类型,它可以用来表示复杂的数据结构。在 struct 中,我们可以定义多个字段,每个字段可以有不同的类型和名称。 除了这些基本信息之外,Go 还提供了 struct tags,它可以用来指定 struct 中每个字段的元信息。 在本文中,我们将探讨为什

    2024年02月15日
    浏览(74)
  • 一个golang小白使用vscode搭建Ununtu20.04下的go开发环境

    先交代一下背景,距离正式接触golang这门语言已经有5年时间,平时偶尔也会用go写写工具和功能,但其实充其量就是语言小白,基本上就是按照教程配置好环境,按照需求写写逻辑,能跑起来就行了。golang随着这几年的变化,这门语言的变化还是非常大的,之前写过一篇《

    2024年01月22日
    浏览(73)
  • Golang:Go语言结构

    在我们开始学习 Go 编程语言的基础构建模块前,让我们先来了解 Go 语言最简单程序的结构。 Go 语言的基础组成有以下几个部分: 包声明 引入包 函数 变量 语句 表达式 注释 接下来让我们来看下简单的代码,该代码输出了\\\"Hello World!\\\": 让我们来看下以上程序的各个部分: 第一

    2024年02月10日
    浏览(57)
  • 【Golang】Golang进阶系列教程--Go 语言 map 如何顺序读取?

    Go 语言中的 map 是一种非常强大的数据结构,它允许我们快速地存储和检索键值对。 然而,当我们遍历 map 时,会有一个有趣的现象,那就是输出的键值对顺序是不确定的。 先看一段代码示例: 当我们多执行几次这段代码时,就会发现,输出的顺序是不同的。 首先,Go 语言

    2024年02月14日
    浏览(65)
  • 【Golang】Golang进阶系列教程--Go 语言数组和切片的区别

    在 Go 语言中,数组和切片看起来很像,但其实它们又有很多的不同之处,这篇文章就来说说它们到底有哪些不同。 数组和切片是两个常用的数据结构。它们都可以用于存储一组相同类型的元素,但在底层实现和使用方式上存在一些重要的区别。 Go 中数组的长度是不可改变的

    2024年02月15日
    浏览(57)
  • 【Golang】Golang进阶系列教程--Go 语言切片是如何扩容的?

    在 Go 语言中,有一个很常用的数据结构,那就是切片(Slice)。 切片是一个拥有相同类型元素的可变长度的序列,它是基于数组类型做的一层封装。它非常灵活,支持自动扩容。 切片是一种引用类型,它有三个属性:指针,长度和容量。 底层源码定义如下: 指针: 指向

    2024年02月14日
    浏览(63)
  • golang实现webgis后端开发

    目录 前言 二、实现步骤 1.postgis数据库和model的绑定 2.将pg库中的要素转换为geojson (1)几何定义 (2)将wkb解析为几何类型 (3)定义geojson类型 (4)数据转换 (5)数据返回  2.前端传入的geojson储存到数据库 3、其他功能实现 总结         停更了接近一个月都在研究一门新语言gola

    2024年02月08日
    浏览(49)
  • 【GoLang】MAC安装Go语言环境

    小试牛刀 首先安装VScode软件 或者pycharm mac安装brew软件  brew install go 报了一个错误 不提供这个支持  重新brew install go 之后又重新brew reinstall go 使用go version 可以看到go 的版本 使用go env  可以看到go安装后的配置 配置一个环境变量 vim ~/.zshrc,  

    2024年02月15日
    浏览(56)
  • Go语言(Golang)数据库编程

    要想连接到 SQL 数据库,首先需要加载目标数据库的驱动,驱动里面包含着于该数据库交互的逻辑。 sql.Open() 数据库驱动的名称 数据源名称 得到一个指向 sql.DB 这个 struct 的指针 sql.DB 是用来操作数据库的,它代表了0个或者多个底层连接的池,这些连接由sql 包来维护,sql 包会

    2024年02月03日
    浏览(86)
  • 【Golang】VScode配置Go语言环境

    安装VScode请参考我的上一篇博客:VScode安装_㫪548的博客-CSDN博客 接下来我们直接进入正题: Go语言(又称Golang)是一种开源的编程语言,由Google开发并于2009年首次发布。Go语言具有简洁、高效、可靠和易于阅读的特点,被设计用于解决大型项目的开发需求。它结合了静态类型

    2024年02月03日
    浏览(64)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包