Go 中祕而不宣的數據結構 BitVec：位向量 125MB 存儲 10 億個數據
位圖 (bitmap) 是一種優雅而高效的數據結構, 它巧妙地利用了計算機最底層的位運算能力。你可以把它想象成一個巨大的開關陣列, 每個開關只有打開和關閉兩種狀態 —— 這就是位圖的本質。每一位都可以獨立控制, 卻又可以通過位運算實現羣體操作。
在實際應用中, 位圖的威力令人驚歎。設想你需要在海量數據中查找重複的數字, 傳統的哈希表或數組都會佔用大量內存。而位圖卻能巧妙地用一個比特位標記一個數字的出現情況, 極大地壓縮了存儲空間。在處理 10 億個不重複的整數時, 位圖僅需要 125MB 內存, 相比其他數據結構動輒需要幾個 GB, 效率提升顯著。
位圖的運用也體現在我們日常使用的數據庫系統中。數據庫會用位圖索引來加速查詢, 尤其是對於性別、狀態這樣的枚舉字段, 一個位圖就能快速定位滿足條件的記錄。比如在電商系統中, 快速篩選出 "在售且有庫存" 的商品, 位圖索引可以通過簡單的位與運算瞬間得出結果。
在大規模系統的權限控制中, 位圖也顯示出其獨特魅力。用戶的各項權限可以編碼到不同的位上, 判斷權限時只需一條位運算指令, 既高效又直觀。比如一個 CMS 系統, 可以用一個 32 位的整數表示用戶的全部權限狀態, 包括讀、寫、管理等多個維度。
布隆過濾器更是位圖思想的精妙應用。它用多個哈希函數在位圖上標記數據, 能夠以極小的內存代價判斷一個元素是否可能存在。這在網頁爬蟲、垃圾郵件過濾等場景下廣泛應用。雖然可能有小概率的誤判, 但在實際應用中往往是可以接受的權衡。
正是由於以上特點, 位圖在處理海量數據、狀態標記、數據壓縮、快速統計等場景中表現出色。它用最簡單的方式解決了最複雜的問題, 這正是計算機科學之美的體現。
BitVec 和 BitMap 類似，只是關注點有些不同。BitVec 更像是位操作的抽象數據類型, 它強調的是向量化的位運算操作。比如在 Rust 語言中, bitvec[1] 提供了一系列方便的接口來進行位操作。而 Bitmap 則更強調其作爲 "圖" 的特性, 通常用固定大小的位數組來表示集合中元素的存在性。
BitVec 具有以下的優勢：
-
空間效率高 - 每個比特位只佔用 1 位 (bit) 空間, 可以表示 0 或 1 兩種狀態
-
快速的位運算 - 支持 AND、OR、XOR 等位運算操作, 性能很高，甚至可以利用 SIMD 加速
-
隨機訪問快 - 可以 O(1) 時間定位到任意位置的比特位
-
緊湊存儲 - 一個字節 (byte) 可以存儲 8 個比特位的信息
-
內存佔用小 - 對於數據量大但狀態簡單的場景很節省內存
Go 內部實現的 BitVec
在 Go 運行時的內部， cmd/compile/internal/bitvec[2] 實現了一個位向量數據結構 BitVec，在 ssa 活躍性分析中使用 (bvecSet 封裝了 BitVec)。在 runtime/stack.go[3] 中實現了 bitvector 並在內存管理中使用。
我們重點看 BitVec, 它的方法比較全。
BitVec 的結構體定義如下：
type BitVec struct {
N int32 // 這個向量中包含的bit數
B []uint32 // 保存這些bit所需的數組
}
func New(n int32) BitVec {
nword := (n + wordBits - 1) / wordBits // 計算保存這些bit所需的最少的數組
return BitVec{n, make([]uint32, nword)}
}然後定義了一批位操作的方法：
-
func (dst BitVec) And(src1, src2 BitVec)[4] ：對兩個位向量進行與操作，結果放入到 dst 位向量中
-
func (dst BitVec) AndNot(src1, src2 BitVec)[5]
-
func (bv BitVec) Clear()[6]
-
func (dst BitVec) Copy(src BitVec)[7]
-
func (bv BitVec) Count() int[8]
-
func (bv1 BitVec) Eq(bv2 BitVec) bool[9]
-
func (bv BitVec) Get(i int32) bool[10]
-
func (bv BitVec) IsEmpty() bool[11]
-
func (bv BitVec) Next(i int32) int32[12]
-
func (bv BitVec) Not()[13]
-
func (dst BitVec) Or(src1, src2 BitVec)[14]
-
func (bv BitVec) Set(i int32)[15]
-
func (bv BitVec) String() string[16]
-
func (bv BitVec) Unset(i int32)[17]
這裏可以看到 Go 內部實現也有一些 "不規範" 的方法，這些 Receiver 的名字不一致，叫做了 dst、bv、bv 1 三種名稱，看起來是有深意的。dst 代表操作最後存儲的位向量。不過 bv 1 就有點說不過去了，雖然也能理解，爲了和參數中的 bv 2 保持一致。
我們可以挑幾個方法看它的實現。
比如 And 方法:
func (dst BitVec) And(src1, src2 BitVec) {
if len(src1.B) == 0 {
return
}
_, _ = dst.B[len(src1.B)-1], src2.B[len(src1.B)-1] // hoist bounds checks out of the loop
for i, x := range src1.B {
dst.B[i] = x & src2.B[i]
}
}就是求兩個位向量的交集，這裏用到了位運算 &。逐個元素進行位與操作，然後存儲到 dst 中。
可以看到如果使用 SIMD 指令，這裏的性能會有很大的提升。
再比如Not方法:
func (bv BitVec) Not() {
for i, x := range bv.B {
bv.B[i] = ^x
}
if bv.N%wordBits != 0 {
bv.B[len(bv.B)-1] &= 1<<uint(bv.N%wordBits) - 1 // clear bits past N in the last word
}
}這裏是對位向量取反，用到了位運算 ^。然後對最後一個元素進行了特殊處理，清除了多餘的位。這裏這一句bv.B[len(bv.B)-1] &= 1<<uint(bv.N%wordBits) - 1可能難以理解，其實是爲了清除最後一個元素中多餘的位，這裏的 1<<uint(bv.N%wordBits) - 1 就是一個掩碼，用來清除多餘的位。
再比如Count方法:
func (bv BitVec) Count() int {
n := 0
for _, x := range bv.B {
n += bits.OnesCount32(x)
}
return n
}這裏是統計位向量中 1 的個數，用到了 bits.OnesCount32 方法，這個方法是一個快速計算 Uint32 中 bit 爲 1 的個數的方法。
這裏的實現都是比較簡單的，但是在實際應用中，位向量的操作是非常高效的，可以用來解決很多問題。
如果你的項目中有這種需求，比如你要實現一個布隆過濾器 / 布穀鳥過濾器，或者你要實現一個高效的權限控制系統，那麼位向量是一個非常好的選擇。
參考資料
[1]
bitvec: https://crates.io/crates/bitvec
[2]
cmd/compile/internal/bitvec: https://github.com/golang/go/blob/989eed28497cde7145958985f50bb3dd6ab698b6/src/cmd/compile/internal/bitvec/bv.go#L21
[3]
runtime/stack.go: https://github.com/golang/go/blob/master/src/runtime/stack.go#L595
[4]
func (dst BitVec) And(src1, src2 BitVec): https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.And
[5]
func (dst BitVec) AndNot(src1, src2 BitVec): https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.AndNot
[6]
func (bv BitVec) Clear(): https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.Clear
[7]
func (dst BitVec) Copy(src BitVec): https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.Copy
[8]
func (bv BitVec) Count() int: https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.Count
[9]
func (bv1 BitVec) Eq(bv2 BitVec) bool: https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.Eq
[10]
func (bv BitVec) Get(i int32) bool: https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.Get
[11]
func (bv BitVec) IsEmpty() bool: https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.IsEmpty
[12]
func (bv BitVec) Next(i int32) int32: https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.Next
[13]
func (bv BitVec) Not(): https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.Not
[14]
func (dst BitVec) Or(src1, src2 BitVec): https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.Or
[15]
func (bv BitVec) Set(i int32): https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.Set
[16]
func (bv BitVec) String() string: https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.String
[17]
func (bv BitVec) Unset(i int32): https://pkg.go.dev/cmd/compile/internal/bitvec@go1.23.2#BitVec.Unset
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/mtyHsHkgZ6shymsQnRbeMw