掘金 后端 ( ) • 2024-03-15 14:10
什么是位数组/位图/BitMap，他们能用来干什么？附简易版实现
位图/BitMap 附简易版 位数 组

位数组（Bit Array），也被称为位图（BitMap）、位向量（Bit Vector）或位集（BitSet），是一种特殊的数组，用于紧凑地存储信息中的位数据。不同于常规数组，每个元素通常存储一个字节或更多，位数组的每个元素只存储一位（0或1）。这种数据结构极大地提高了空间效率，使其在处理大量布尔值（是/否）时非常有用。

使用场景

内存高效存储：当需要存储大量的开/关、是/否这样的布尔值时，位数组提供了一种极为节省空间的方法。相比于使用一个完整的byte来存储每个布尔值，位数组能显著减少内存占用。

快速访问：位数组允许对单个位的快速访问和修改，这使得它在需要高效检索和更新大量二元状态时非常有用。

集合操作：位数组非常适合进行集合操作，如并集（Union）、交集（Intersection）和差集（Difference）。这些操作可以通过简单的位运算（如AND、OR和XOR）高效完成。

示例场景：

  • 数据库索引：数据库系统中，位数组可以用来高效地表示和查询行的状态，例如，标记某些行是否满足特定的查询条件。
  • 网络爬虫：网络爬虫使用位数组来高效地标记哪些网页已经被访问过，避免重复爬取。
  • 权限控制：在权限控制系统中，位数组可用来紧凑地存储和检查用户的权限标志，每一位代表一种权限的有无。

总的来说，位数组是处理大量二进制状态信息时的高效工具，特别是在空间和速度都是关键因素的场景中。

实现原理

位数组通过一个或多个整数来实现。由于每个整数由固定数量的位组成（例如，一个int类型在许多系统中是32位或64位），可以使用这些位来表示布尔值。具体来说：

  • 设置位（Set）：将指定位置的位设置为1。这通常通过将该位置对应的位与1进行“或”（OR）操作实现。
  • 清除位（Clear）：将指定位置的位设置为0。这可以通过将该位置对应的位与1的补码进行“与”（AND）操作实现。
  • 测试位（Test）：检查指定位置的位是0还是1。这通过将位数组的相应整数与该位置对应的位进行“与”（AND）操作后比较结果是否为0来实现。

位数组为什么不叫布尔数组？

位数组（Bit Array）和布尔数组（Boolean Array）都可以用来表示一系列的布尔值（true/false或者是/否）。尽管它们在概念上相似，主要区别在于它们的存储效率和实现方式。

  1. 存储效率：

    • 位数组：每个元素仅占用一个位（bit）。这意味着在相同的存储空间中，位数组能够存储比布尔数组更多的布尔值，因为布尔数组的每个元素至少占用一个字节（byte，等于8位）。这使得位数组在需要存储大量布尔值时非常空间高效。
    • 布尔数组：在大多数编程语言中，布尔类型的数组的每个元素通常占用一个字节或更多的空间，而不是仅占用一个位。这是因为编程语言和计算机硬件通常按字节进行数据的寻址和处理。

  2. 实现方式：

    • 位数组：实现位数组通常需要对位进行直接操作，如使用位运算（AND、OR、NOT等）来设置、清除或检查值。这需要一定的位操作知识，但允许高度的空间效率。
    • 布尔数组：布尔数组的实现更直接，每个数组元素直接对应一个布尔值。这种方式更简单、更直观，但在存储大量布尔值时空间效率较低。

  3. 命名原因：

    • 为什么不叫布尔数组：虽然位数组在逻辑上存储的是布尔值，但称其为“位数组”是为了强调其通过位操作实现的高空间效率的特点。"位数组"这个名字强调了其内部结构和实现机制，即直接使用位来存储信息，而非布尔变量。

总结来说，位数组之所以不被称为布尔数组，是因为它们在实现机制和存储效率上的根本区别。位数组通过每个位的直接操作来实现极高的空间效率，而这种效率是普通布尔数组所无法比拟的。这种命名方式有助于区分这两种数据结构的用途和特点。

简易版go实现

下面是一个使用Go语言实现的简易位数组的示例。这个实现使用uint64数组作为底层存储，以支持大量的位操作。这种实现方式提供了基本的功能，包括设置位、清除位、测试位是否设置，以及计算位数组的大小。

package main

import (
    "fmt"
)

// BitArray 结构体，表示位数组
type BitArray struct {
    bits []uint64
    size int
}

// NewBitArray 创建一个新的位数组
func NewBitArray(size int) *BitArray {
    return &BitArray{
        bits: make([]uint64, (size+63)/64), // 64位对齐
        size: size,
    }
}

// Set 设置位数组中指定位置的位为1
func (ba *BitArray) Set(pos int) {
    if pos < 0 || pos >= ba.size {
        return // 超出范围
    }
    ba.bits[pos/64] |= 1 << (pos % 64) // 位操作设置位
}

// Clear 清除位数组中指定位置的位（设置为0）
func (ba *BitArray) Clear(pos int) {
    if pos < 0 || pos >= ba.size {
        return // 超出范围
    }
    ba.bits[pos/64] &^= 1 << (pos % 64) // 位操作清除位
}

// IsSet 检查位数组中指定位置的位是否为1
func (ba *BitArray) IsSet(pos int) bool {
    if pos < 0 || pos >= ba.size {
        return false // 超出范围
    }
    return ba.bits[pos/64]&(1<<(pos%64)) != 0 // 位操作检查位
}

// Size 返回位数组的大小
func (ba *BitArray) Size() int {
    return ba.size
}

func main() {
    ba := NewBitArray(128) // 创建一个大小为128的位数组

    ba.Set(10)  // 在位置10设置位
    ba.Set(75)  // 在位置75设置位

    fmt.Println("Is position 10 set?", ba.IsSet(10)) // 检查位置10是否被设置
    fmt.Println("Is position 75 set?", ba.IsSet(75)) // 检查位置75是否被设置
    fmt.Println("Is position 20 set?", ba.IsSet(20)) // 检查位置20是否被设置

    ba.Clear(10) // 清除位置10的位
    fmt.Println("Is position 10 set after clearing?", ba.IsSet(10)) // 再次检查位置10
}

这个简单的位数组实现提供了位设置、清除和检查的基本操作。在实际应用中，可能还需要添加更多的功能，比如扩展数组大小、遍历设置了的位等。此外，注意这个实现没有进行错误检查，如在实际项目中使用时，应该添加适当的错误处理逻辑。