数据结构与算法：位图

位图（Bitmap） 是一种数据结构，使用位（bit）来标记值的存在或状态。每个元素的状态由一个位表示（0或1），从而可以高效地进行存储和操作。位图常用于需要快速判断某个值是否存在或需要节省存储空间的场景。

位图的优点

1. 节省空间：位图通过使用位（而不是字节或更大的数据类型）表示数据，占用的存储空间非常小。例如，一个32位整数可以表示32个状态（0或1），而不是仅表示一个数值。
2. 快速操作
   • 查找：判断某个值是否存在只需要一次位运算，时间复杂度为 𝑂(1)。
   • 插入和删除：只需对对应的位进行设置或清除操作，效率高。
   • 交集、并集等操作：可以通过按位与、或操作快速实现集合运算。
3. 适合大规模数据：对于范围较大的离散数据（如整数集合），位图可以有效避免存储全部数据所需的开销。
4. 易于扩展：位图可以通过简单地扩展位数组的长度来支持更大的范围。

位图的缺点

1. 无法直接存储非整数数据：位图只能处理整数数据，如果需要处理字符串或浮点数等其他类型的数据，需要先进行哈希映射，可能引入冲突问题。
2. 浪费空间（低密度数据）：如果存储的数据范围非常大，而实际使用的数据很少，位图会浪费大量未使用的位。例如，需要表示 1 到 10亿范围内的整数，但只有少量数值存在时，位图的效率会下降。
3. 不支持动态数据范围：位图需要在初始化时指定固定的范围（最大值和最小值），超出范围的数据无法表示。
4. 缺乏直接排序能力：位图只能记录数据是否存在，不能直接存储数据的顺序或频率。

位图的应用场景

1. 大数据去重：在处理大规模数据时，用位图快速判断某个值是否已经出现过。
2. 集合操作：位图可以高效地进行集合的并集、交集、差集等操作，适用于布隆过滤器等场景。
3. 快速排序：对一个范围内的整数进行排序时，可以使用位图标记所有出现的数值，然后按位图的顺序输出。
4. 位向量算法：位图是实现布隆过滤器、稀疏矩阵等算法和数据结构的重要基础。
5. 内存敏感系统：在存储受限的嵌入式系统或数据库索引中，位图是一种高效的解决方案。

代码示例

func NewBitMap(size int32) *BitMap {

	b := new(BitMap)
	b.array = make([]int, (size+31)/32)
	return b
}

type BitMap struct {
	array []int
}

func (b *BitMap) Set(num int32) {

	b.array[num/32] |= 1 << (num % 32)
}

func (b *BitMap) Remove(num int32) {
	b.array[num/32] &= ^(1 << (num % 32))
}

func (b *BitMap) Test(num int32) bool {
	return (b.array[num/32] & (1 << (num % 32))) != 0
}