誤判率的推導(dǎo)
- 前提：
- 數(shù)組長(zhǎng)度 m
- 有 k 個(gè) hash 函數(shù)么介，每個(gè) hash 函數(shù)彼此獨(dú)立（老實(shí)說(shuō)，彼此獨(dú)立這個(gè)條件怎么達(dá)到我也不太清楚烫映，以及或許有其他的前提條件我也不太清楚）
- 用 n 個(gè)樣本空間
- 推導(dǎo)過(guò)程
第一部分：
經(jīng)過(guò)一個(gè) hash 函數(shù)以后某一位置為 0 的概率是
經(jīng)過(guò) k 個(gè) hash 函數(shù)以后某一位置為 0 的概率是
經(jīng)過(guò) n 個(gè)樣本以后某一位置為 0 的概率是
因此經(jīng)過(guò) n 個(gè)樣本以后某一位為 1 的概率是
現(xiàn)在再來(lái)一個(gè)新的樣本，全選到 1 的概率是
第二部分，上面先推導(dǎo)到這里接下來(lái)需要推導(dǎo)一個(gè)別的：
- 這是 e 的推導(dǎo)：
- 將 -x 替換 x
我們?cè)購(gòu)牡谝徊糠值牡谖宀嚼^續(xù)向后：
- 變形得：
- 對(duì)于大 m 約等于：
所以針對(duì)大 m酣藻，誤報(bào)率約為：
我們通常要根據(jù) n 和 m 推導(dǎo)合適的 hash 個(gè)數(shù)，為：鳍置。
如果需要根據(jù)誤報(bào)率來(lái)推導(dǎo)辽剧，此時(shí) ，此時(shí)誤報(bào)率
税产∨陆危可以簡(jiǎn)寫(xiě)為：
這導(dǎo)致：
所以 m 和 n 的最佳比值此時(shí)為：
后面的部分我都是摘自 wiki：https://en.wikipedia.org/wiki/Bloom_filter偷崩。根據(jù)這些我們就可以實(shí)現(xiàn)自己的 Bloom filter。
- 參考
https://en.wikipedia.org/wiki/Bloom_filter
實(shí)現(xiàn)
我們?cè)趯?shí)現(xiàn)的時(shí)候前提條件通常是：
- 假陽(yáng)性 p 概率是多少
- 要存的樣本空間多大
要求的就是上面公式里的 k 和 m撞羽。
- m 告訴我們需要多少的 bit 位
- k 告訴我們需要多少個(gè) hash 函數(shù)
按照公式：
大概實(shí)現(xiàn)如下：
// bloom.go
// Copyright 2021 hardcore-os Project Authors
//
// Licensed under the Apache License, Version 2.0 (the "License")
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package utils
import "math"
// Filter is an encoded set of []byte keys.
type Filter []byte
// MayContainKey _
func (f Filter) MayContainKey(k []byte) bool {
return f.MayContain(Hash(k))
}
func (f Filter) K() uint8 {
return f[len(f) - 1]
}
// get 根據(jù) hash 值得到 filter 中某一位的值
func (f Filter) get(h uint32) uint8 {
x, y := posInFilter(h, len(f) - 1)
return uint8((f[x] >> y) & 1)
}
// set 根據(jù) hash 值將某一位置 1
func (f Filter) set(h uint32) {
x, y := posInFilter(h, len(f) - 1)
f[x] = f[x] | 1 << y
}
// MayContain returns whether the filter may contain given key. False positives
// are possible, where it returns true for keys not in the original set.
func (f Filter) MayContain(h uint32) bool {
//Implement me here!!!
//在這里實(shí)現(xiàn)判斷一個(gè)數(shù)據(jù)是否在bloom過(guò)濾器中
//思路大概是經(jīng)過(guò)K個(gè)Hash函數(shù)計(jì)算阐斜，判讀對(duì)應(yīng)位置是否被標(biāo)記為1
delta, k := h >> 17 | h << 15, f.K()
for j := uint8(0); j < k; j ++ {
if f.get(h) == 0 {
return false
}
h += delta
}
return true
}
// posInFilter 根據(jù) hash 值計(jì)算此 hash 在 pos 的哪一個(gè)位置
// h 是 hash 值，filterLen 就是用byte數(shù)組中真正做做filter的長(zhǎng)度
func posInFilter(h uint32, filterLen int) (x, y int) {
nBits := uint32(filterLen * 8)
bitPos := h % nBits
return int(bitPos / 8), int(bitPos % 8)
}
// NewFilter returns a new Bloom filter that encodes a set of []byte keys with
// the given number of bits per key, approximately.
//
// A good bitsPerKey value is 10, which yields a filter with ~ 1% false
// positive rate.
func NewFilter(keys []uint32, bitsPerKey int) Filter {
return appendFilter(keys, bitsPerKey)
}
// BloomBitsPerKey returns the bits per key required by bloomfilter based on
// the false positive rate.
func BloomBitsPerKey(numEntries int, fp float64) int {
//Implement me here!!!
//閱讀bloom論文實(shí)現(xiàn)放吩，并在這里編寫(xiě)公式
//傳入?yún)?shù)numEntries是bloom中存儲(chǔ)的數(shù)據(jù)個(gè)數(shù)智听，fp是false positive假陽(yáng)性率
// 計(jì)算 m/n 根據(jù)：https://en.wikipedia.org/wiki/Bloom_filter
return int(-1.44 * math.Log2(fp) + 1)
}
func appendFilter(keys []uint32, bitsPerKey int) Filter {
//Implement me here!!!
//在這里實(shí)現(xiàn)將多個(gè)Key值放入到bloom過(guò)濾器中
// TODO：系統(tǒng)檢查 bitsPerKey
if bitsPerKey < 0 {
bitsPerKey = 0
}
keyLen := len(keys)
k := uint8(float64(bitsPerKey) * 0.69)
if k < 1 {
k = 1
}
if k > 30 {
k = 30
}
nBits := bitsPerKey * keyLen
// 如果 nBits 太小會(huì)有很高的 false positive
if nBits < 64 {
nBits = 64
}
// TODO：檢查 nBits 的上界
nBytes := (nBits + 7) / 8
// 最后一位
filter := Filter(make([]byte, nBytes + 1))
// 向 filter 中放入所有的 key
for _, h := range keys {
delta := h >> 17 | h << 15
for j := uint8(0); j < k; j ++ {
filter.set(h)
h += delta
}
}
filter[nBytes] = k
return filter
}
// Hash implements a hashing algorithm similar to the Murmur hash.
func Hash(b []byte) uint32 {
const (
seed = 0xbc9f1d34
m = 0xc6a4a793
)
h := uint32(seed) ^ uint32(len(b))*m
for ; len(b) >= 4; b = b[4:] {
h += uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
h *= m
h ^= h >> 16
}
switch len(b) {
case 3:
h += uint32(b[2]) << 16
fallthrough
case 2:
h += uint32(b[1]) << 8
fallthrough
case 1:
h += uint32(b[0])
h *= m
h ^= h >> 24
}
return h
}
// bloom_test.go
// Copyright 2021 hardcore-os Project Authors
//
// Licensed under the Apache License, Version 2.0 (the "License")
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package utils
import (
"testing"
)
func (f Filter) String() string {
s := make([]byte, 8*len(f))
for i, x := range f {
for j := 0; j < 8; j++ {
if x&(1<<uint(j)) != 0 {
s[8*i+j] = '1'
} else {
s[8*i+j] = '.'
}
}
}
return string(s)
}
func TestSmallBloomFilter(t *testing.T) {
var hash []uint32
for _, word := range [][]byte{
[]byte("hello"),
[]byte("world"),
} {
hash = append(hash, Hash(word))
}
f := NewFilter(hash, 10)
got := f.String()
// The magic want string comes from running the C++ leveldb code's bloom_test.cc.
want := "1...1.........1.........1.....1...1...1.....1.........1.....1....11....."
if got != want {
t.Fatalf("bits:\ngot %q\nwant %q", got, want)
}
m := map[string]bool{
"hello": true,
"world": true,
"x": false,
"foo": false,
}
for k, want := range m {
got := f.MayContainKey([]byte(k))
if got != want {
t.Errorf("MayContain: k=%q: got %v, want %v", k, got, want)
}
}
}
func TestBloomFilter(t *testing.T) {
nextLength := func(x int) int {
if x < 10 {
return x + 1
}
if x < 100 {
return x + 10
}
if x < 1000 {
return x + 100
}
return x + 1000
}
le32 := func(i int) []byte {
b := make([]byte, 4)
b[0] = uint8(uint32(i) >> 0)
b[1] = uint8(uint32(i) >> 8)
b[2] = uint8(uint32(i) >> 16)
b[3] = uint8(uint32(i) >> 24)
return b
}
nMediocreFilters, nGoodFilters := 0, 0
loop:
for length := 1; length <= 10000; length = nextLength(length) {
keys := make([][]byte, 0, length)
for i := 0; i < length; i++ {
keys = append(keys, le32(i))
}
var hashes []uint32
for _, key := range keys {
hashes = append(hashes, Hash(key))
}
f := NewFilter(hashes, 10)
if len(f) > (length*10/8)+40 {
t.Errorf("length=%d: len(f)=%d is too large", length, len(f))
continue
}
// All added keys must match.
for _, key := range keys {
if !f.MayContainKey(key) {
t.Errorf("length=%d: did not contain key %q", length, key)
continue loop
}
}
// Check false positive rate.
nFalsePositive := 0
for i := 0; i < 10000; i++ {
if f.MayContainKey(le32(1e9 + i)) {
nFalsePositive++
}
}
if nFalsePositive > 0.02*10000 {
t.Errorf("length=%d: %d false positives in 10000", length, nFalsePositive)
continue
}
if nFalsePositive > 0.0125*10000 {
nMediocreFilters++
} else {
nGoodFilters++
}
}
if nMediocreFilters > nGoodFilters/5 {
t.Errorf("%d mediocre filters but only %d good filters", nMediocreFilters, nGoodFilters)
}
}
func TestHash(t *testing.T) {
// The magic want numbers come from running the C++ leveldb code in hash.cc.
testCases := []struct {
s string
want uint32
}{
{"", 0xbc9f1d34},
{"g", 0xd04a8bda},
{"go", 0x3e0b0745},
{"gop", 0x0c326610},
{"goph", 0x8c9d6390},
{"gophe", 0x9bfd4b0a},
{"gopher", 0xa78edc7c},
{"I had a dream it would end this way.", 0xe14a9db9},
}
for _, tc := range testCases {
if got := Hash([]byte(tc.s)); got != tc.want {
t.Errorf("s=%q: got 0x%08x, want 0x%08x", tc.s, got, tc.want)
}
}
}
- 參考
測(cè)試代碼和實(shí)現(xiàn)代碼的框架來(lái)自：https://github.com/hardcore-os/corekv
