算法说明
Bitmap算法是一种基于位运算的数据结构，用于解决大规模数据的快速查找和统计问题。其基本原理是将一个大数据集合映射到一个二进制向量中，其中每个元素对应于数据集合中的一个元素，向量中的每一位表示该元素是否存在于集合中。
具体来说，Bitmap算法通过使用一个位图（bitmap）来表示一个数据集合，其中每个元素对应一个位。如果某个元素在数据集合中出现，则将其对应的位设置为1，否则将其对应的位设置为0。通过这种方式，可以快速地进行集合操作，如并集、交集和差集等。
Bitmap算法的主要优点在于其空间效率高，可以用较小的空间存储大规模数据集合。另外，Bitmap算法的时间复杂度也非常低，可以快速地进行集合操作。
如何用数组表示一个 bitmap
以 1byte 为例：8位能表示8个元素， 0-7 号对应了 b[0] 下标， 8-15 号对应了 b[1] 下标，以此类推。
因此，数组下标 n 跟bitmap元素序号 bitmapIdx 的关系为：n = bitmapIdx >> 3
值如何映射到 bitmap 数组
当找到了 元素序号 n 在数组中的下标之后，如何给 b[n] 赋值呢？
1 << (bitmapIdx & 7) 等同于 1 << (bitmapIdx % 8)
(bitmapIdx % 8) 找到在了在数组 b[n] 中的第 m 位，然后 1 << m 之后，就相当于给数组赋值，把第 m 位 置为1。
验证
同样以 1byte 为例：借用上述结论，第 24 号元素，对应的数组下标 n 为：n = 24 >> 3 结果为3, b[3]；
1 << (24 % 8) = 1 ， 说明 24 号元素，在 b[3] 的第1位，b[3] = 1；
当 25 号元素加入时，此时 n = 25 >> 3 结果为3，b[3]; 1 << (25 % 8) = 2 , 说明 25 号元素，在 b[3] 的第2位，此时如何赋值呢，b[3] 已经赋值为 1 了; 通过 | 运算就能合并结果：b[3] = 1|2 = 3, 此时就把 24，25 两个元素放到 b[3] 中了；
代码实现
package bitmap
import (
"encoding/json"
"fmt"
"strconv"
)
type BitMap struct {
data []int64
}
func NewBitMap(size int) *BitMap {
return &BitMap{
data: make([]int64, size),
}
}
func ParseFromJsonStr(str string) *BitMap {
bitMap := NewBitMap(0)
err := json.Unmarshal([]byte(str), &bitMap.data)
if err != nil {
_ = fmt.Errorf("parse from json str return error %+v", err)
}
return bitMap
}
func (b *BitMap) set(index uint) {
dataIdx := index >> 5 // index/32
if dataIdx >= uint(len(b.data)) {
b.data = append(b.data, 1<<(index&31)) // index&31 = index%32
} else {
b.data[dataIdx] |= 1 << (index & 31)
}
}
func (b *BitMap) get(index uint) bool {
dataIdx := index >> 5
if len(b.data) <= 0 || uint(len(b.data)) < dataIdx {
return false
}
return b.data[dataIdx]&(1<<(index&31)) > 0
}
func (b *BitMap) String() string {
result := ""
for _, v := range b.data {
result += strconv.FormatInt(v, 10) + "(" + DecToBin(v) + "),"
}
return result
}
func DecToBin(n int64) string {
result := ""
if n == 0 {
return "0"
}
for ; n > 0; n /= 2 {
lsb := n % 2
result = strconv.FormatInt(lsb, 10) + result
}
return result
}
测试结果
func TestNewBitmap(t *testing.T) {
bitMap := NewBitMap(1)
bitMap.set(1)
bitMap.set(2)
bitMap.set(3)
bitMap.set(4)
bitMap.set(0)
fmt.Println(bitMap.String())
bitMap.set(32)
bitMap.set(33)
fmt.Println(bitMap.String())
bitMap.set(89)
fmt.Println(bitMap.String())
}
=== RUN TestNewBitmap
31(11111),
31(11111),3(11),
31(11111),3(11),33554432(10000000000000000000000000),
--- PASS: TestNewBitmap (0.00s)
PASS