資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Go語言實現布隆過濾器的程式
布隆過濾器是一種節省空間的資料結構，廣泛應用於各種涉及成員測試的應用中。在本文中，我們將探討如何在 Go 語言中建立布隆過濾器。我們將為此實現編寫兩個不同的示例，第一個示例包括使用 FNV-1a 演算法的雜湊函式，第二個示例將使用一個 []bool 陣列來有效地確定元素的存在。
解釋
布隆過濾器可以被描述為一種機率資料結構，用於檢查集合中是否存在某個元素。它利用多個雜湊函式和一個位數組，使其具有很高的記憶體效率。然而，另一方面，也可能出現假陽性，這意味著它可能會錯誤地指示元素存在，即使它實際上並不存在於集合中。
語法
func NewBloomFilter(m int, k int) *BloomFilter
語法定義了一個名為 NewBloomFilter 的函式，該函式用於建立一個新的布隆過濾器例項，它有兩個引數：整數 `m` 表示大小，`k` 表示雜湊函式的數量，用於建立布隆過濾器例項。
func (bf *BloomFilter) Contains(item []byte) bool
語法定義了一個名為 Contains 的函式，它與布隆過濾器例項 (`bf`) 相關聯，並以位元組陣列 (`item`) 作為輸入，使用預定義的雜湊函式計算輸入的雜湊值，並返回相應的布林值以指示該專案是否存在。
演算法
首先初始化一個大小為 'm' 的位陣列，所有位都設定為 0。
選擇最優的雜湊函式數量，每個函式都有不同的種子。
要新增一個元素，請使用所有選定的函式對其進行雜湊運算，並將陣列中相應的位設定為 1。
要檢查元素的成員資格，請使用相同的選定函式對其進行雜湊運算，並檢查所有相應的位是否都設定為 1。
如果任何位未設定，則該元素肯定不在集合中；否則，它可能在集合中。
示例 1
在此示例中，我們透過一個 []uint64 位陣列在 Go 語言中建立布隆過濾器，以最佳化記憶體效率。我們使用 FNV-1a 演算法的雜湊函式來分配陣列中的元素。NewBloomFilter 函式初始化過濾器，Add 函式用於透過位操作標記元素的存在。Contains 函式檢查元素成員資格。
package main
import (
"fmt"
"hash/fnv"
)
type BloomFilter struct {
bitArray []uint64
hashFunc []func([]byte) uint32
}
func NewBloomFilter(m int, k int) *BloomFilter {
filter := BloomFilter{
bitArray: make([]uint64, (m+63)/64),
hashFunc: make([]func([]byte) uint32, k),
}
for i := 0; i < k; i++ {
seed := uint32(i)
filter.hashFunc[i] = func(data []byte) uint32 {
hash := fnv.New32a()
hash.Write(data)
return (hash.Sum32() + seed) % uint32(m)
}
}
return &filter
}
func (bf *BloomFilter) Add(item []byte) {
for _, hashFn := range bf.hashFunc {
index := hashFn(item)
bf.bitArray[index/64] |= 1 << (index % 64)
}
}
func (bf *BloomFilter) Contains(item []byte) bool {
for _, hashFn := range bf.hashFunc {
index := hashFn(item)
if bf.bitArray[index/64]&(1<<(index%64)) == 0 {
return false
}
}
return true
}
func main() {
filter := NewBloomFilter(160, 3)
fmt.Println("Adding 'apple'")
filter.Add([]byte("apple"))
fmt.Println("\nFinding 'apple': ", filter.Contains([]byte("apple")))
fmt.Println("Finding 'banana': ", filter.Contains([]byte("banana")))
}
輸出
Adding 'apple' Finding 'apple': true Finding 'banana': false
示例 2
在此示例中，我們將使用 []bool 陣列在 Go 語言中建立一個布隆過濾器，以便有效地確定元素的存在。我們還使用 FNV-1a 雜湊函式來分配陣列中的元素。NewBloomFilter 函式定義為初始化過濾器，Add 函式設定新增元素的相應陣列位置。最後，Contains 函式使用陣列位置檢查成員資格。
package main
import (
"fmt"
"hash/fnv"
)
type BloomFilter struct {
bitArray []bool
hashFunc []func([]byte) uint32
}
func NewBloomFilter(m int, k int) *BloomFilter {
filter := BloomFilter{
bitArray: make([]bool, m),
hashFunc: make([]func([]byte) uint32, k),
}
for i := 0; i < k; i++ {
seed := uint32(i)
filter.hashFunc[i] = func(data []byte) uint32 {
hash := fnv.New32a()
hash.Write(data)
return (hash.Sum32() + seed) % uint32(m)
}
}
return &filter
}
func (bf *BloomFilter) Add(item []byte) {
for _, hashFn := range bf.hashFunc {
index := hashFn(item)
bf.bitArray[index] = true
}
}
func (bf *BloomFilter) Contains(item []byte) bool {
for _, hashFn := range bf.hashFunc {
index := hashFn(item)
if !bf.bitArray[index] {
return false
}
}
return true
}
func main() {
filter := NewBloomFilter(20, 3)
fmt.Println("Adding 'apple'")
filter.Add([]byte("apple"))
fmt.Println("\nFinding 'apple': ", filter.Contains([]byte("apple")))
fmt.Println("Finding 'banana': ", filter.Contains([]byte("banana")))
}
輸出
Adding 'apple' Finding 'apple': true Finding 'banana': false
現實生活中的應用
垃圾郵件過濾：使用布隆過濾器可以快速檢查傳入的電子郵件是否為垃圾郵件或非垃圾郵件。一些電子郵件系統維護一個包含已知垃圾郵件關鍵字或短語的布隆過濾器。當收到新的電子郵件時，系統會透過聯絡布隆過濾器來確定某些關鍵字是否存在，從而開始驗證。如果找到這些關鍵字，則該電子郵件很可能被歸類為垃圾郵件。
DNA 序列匹配：在生物資訊學中，使用布隆過濾器可以有效地搜尋大型資料集以進行 DNA 序列匹配。它主要用於識別大型基因組資料庫中某個 DNA 序列的可能匹配項。
結論
布隆過濾器是一種節省空間的資料結構，有助於快速測試集合中的成員資格，但也偶爾會出現假陽性。在本文中，我們探討了在 Go 語言中建立布隆過濾器的兩種方法。第一個示例具有簡潔的實現，在記憶體最佳化和功能效率之間取得了平衡。下一個實現是在記憶體消耗和操作簡單性之間進行了權衡。這些實現演示了雜湊函式和位陣列如何協同作用以最佳化記憶體使用。
201 次檢視
