go 位图(bitmap)的实现

位图

github地址 https://github.com/xiaomeng79/go-algorithm

概念

在一个结构中，用一个比特位来描述一个数据的状态，这种结构就称为位图。位图实际上是哈希表的一种变形

位图可以干什么

• 大数据滤重
• 数据排序

为什么使用

• 节省内存
• 可以位操作,更快

代码

package bitmap

import "fmt"

//位图
type BitMap struct {
    bits []byte
    max  int
}

//初始化一个BitMap
//一个byte有8位,可代表8个数字,取余后加1为存放最大数所需的容量
func NewBitMap(max int) *BitMap {
    bits := make([]byte, (max>>3)+1)
    return &BitMap{bits: bits, max: max}
}

//添加一个数字到位图
//计算添加数字在数组中的索引index,一个索引可以存放8个数字
//计算存放到索引下的第几个位置,一共0-7个位置
//原索引下的内容与1左移到指定位置后做或运算
func (b *BitMap) Add(num uint) {
    index := num >> 3
    pos := num & 0x07
    b.bits[index] |= 1 << pos
}

//判断一个数字是否在位图
//找到数字所在的位置,然后做与运算
func (b *BitMap) IsExist(num uint) bool {
    index := num >> 3
    pos := num & 0x07
    return b.bits[index]&(1<<pos) != 0
}

//删除一个数字在位图
//找到数字所在的位置取反,然后与索引下的数字做与运算
func (b *BitMap) Remove(num uint) {
    index := num >> 3
    pos := num & 0x07
    b.bits[index] = b.bits[index] & ^(1 << pos)
}

//位图的最大数字
func (b *BitMap) Max() int {
    return b.max
}

func (b *BitMap) String() string {
    return fmt.Sprint(b.bits)
}