slow_wild_backend/internal/utils/bitmap.go

package utils

type BitMap struct {
	bits []byte
	size int
}

func NewBitMap(size int) *BitMap {
	if size == 0 {
		size = 250
	}

	return &BitMap{
		bits: make([]byte, size), // 字节的大小，每个字节中存8个bit
		size: size * 8,           // 整个bitmap的大小
	}
}

func (b *BitMap) Set(id int64) {
	// 计算id在哪个bit
	idx := hash(id) % b.size
	// 计算在哪个byte
	byteIdx := idx / 8
	// 计算byte中的bit位置
	bitIdx := idx % 8

	b.bits[byteIdx] |= 1 << bitIdx
}

func (b *BitMap) IsSet(id int64) bool {
	// 计算id在哪个bit
	idx := hash(id) % b.size
	// 计算在哪个byte
	byteIdx := idx / 8
	// 计算byte中的bit位置
	bitIdx := idx % 8

	return (b.bits[byteIdx] & (1 << bitIdx)) != 0
}

func (b *BitMap) Export() []byte {
	return b.bits
}

func Load(bits []byte) *BitMap {
	if len(bits) == 0 {
		return NewBitMap(0)
	}
	return &BitMap{
		bits: bits,
		size: len(bits) * 8,
	}
}

func hash(id int64) int {
	// 使用BKDR哈希算法
	seed := 131313 // 31 131 1313 13131 131313, etc
	hash := 0

	// 将整数id拆分为每个字节，并使用BKDR哈希算法计算哈希值
	for i := 0; i < 8; i++ {
		hash = hash*seed + int((id>>(i*8))&0xFF)
	}

	return hash & 0x7FFFFFFF
}