亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

C#實(shí)現(xiàn)從位圖到布隆過濾器的方法

 更新時(shí)間：2022年06月27日 08:30:05   作者：黑洞視界  
布隆過濾器（Bloom filter）是一種特殊的 Hash Table，能夠以較小的存儲空間較快地判斷出數(shù)據(jù)是否存在。常用于允許一定誤判率的數(shù)據(jù)過濾及防止緩存擊穿及等場景,本文將以 C# 語言來實(shí)現(xiàn)一個(gè)簡單的布隆過濾器，為簡化說明，設(shè)計(jì)得很簡單，需要的朋友可以參考下

前言

本文將以 C# 語言來實(shí)現(xiàn)一個(gè)簡單的布隆過濾器，為簡化說明，設(shè)計(jì)得很簡單，僅供學(xué)習(xí)使用。

感謝@時(shí)總百忙之中的指導(dǎo)。

布隆過濾器簡介

布隆過濾器（Bloom filter）是一種特殊的 Hash Table，能夠以較小的存儲空間較快地判斷出數(shù)據(jù)是否存在。常用于允許一定誤判率的數(shù)據(jù)過濾及防止緩存擊穿及等場景。

相較于 .NET 中的 HashSet 這樣傳統(tǒng)的 Hash Table，存在以下的優(yōu)劣勢。

優(yōu)勢：

  1. 占用的存儲空間較小。不需要像 HashSet 一樣存儲 Key 的原始數(shù)據(jù)。

劣勢：

  1. 存在誤判率，過濾器認(rèn)為不存在的數(shù)據(jù)一定不存在，但是認(rèn)為存在的數(shù)據(jù)不一定真的存在。這個(gè)和布隆過濾器的實(shí)現(xiàn)方式有關(guān)。
  2. 不支持?jǐn)?shù)據(jù)的刪除，下文會講為什么不支持刪除。

數(shù)據(jù)的存儲

布隆過濾器的數(shù)據(jù)保存在 位圖（Bitmap）上。Bitmap 簡而言之是二進(jìn)制位（bit）的數(shù)組。Hash Table 保存每個(gè)元素的位置，我們稱之為 桶（bucket）， Bitmap 上的每一位就是布隆過濾器的 bucket。

布隆過濾器的每一個(gè) bucket 只能存儲 0 或 1。數(shù)據(jù)插入時(shí)，布隆過濾器會通過 Hash 函數(shù)計(jì)算出插入的 key 對應(yīng)的 bucket，并將該 bucket 設(shè)置為 1。

查詢時(shí)，再次根據(jù) Hash 函數(shù)計(jì)算出 key 對應(yīng)的 bucket，如果 bucket 的值是 1，則認(rèn)為 key 存在。

Hash 沖突的解決方案

布隆過濾器使用了 Hash 函數(shù)，自然也逃不過 Hash 沖突的問題。對布隆過濾器而言，發(fā)生 Hash 沖突也就意味著會發(fā)生誤判。

傳統(tǒng) Hash 算法解決 Hash 沖突的方式有 開放定址法、鏈表法等。而布隆過濾器解決 Hash 沖突的方式比較特殊，它使用了多個(gè) Hash 函數(shù)來解決沖突問題。

下圖中插入布隆過濾器的 Bar 和 Baz 經(jīng)過 Hash2 計(jì)算出的位置是同一個(gè)，但 Hash3 計(jì)算出的位置是不一樣的，Bar 和 Baz 得以區(qū)分。

即使布隆過濾器使用了這種方式來解決 Hash沖突，沖突的可能性依舊存在，如下圖所示：

由于布隆過濾器不保留插入的 Key 的原始值，Hash 沖突是無法避免的。我們只能通過增加 Hash 函數(shù)的數(shù)量來減少沖突的概率，也就是減少誤判率。

假設(shè)布隆過濾器有 m 個(gè) bucket，包含 k 個(gè)哈希函數(shù)，已經(jīng)插入了 n 個(gè) key。經(jīng)數(shù)學(xué)推導(dǎo)可得誤判率 ε 的公式如下：

具體推斷過程可參考 https://en.wikipedia.org/wiki/Bloom_filter。

布隆過濾器的誤判概率大致和 已經(jīng)插入的 key 的數(shù)量 n 成正比，和 hash函數(shù)數(shù)量 k、bucket 數(shù) m 成反比。為了減少誤判率，我們可以增加 m 或 增加 k，增加 m 意味著過濾器占用存儲空間會增加，增加 k 則意味著插入和查詢時(shí)的效率會降低。

為什么布隆過濾器不支持刪除

布隆過濾器通過多個(gè) Hash 函數(shù)來解決沖突的設(shè)計(jì)，也意味著多著插入元素可能會共享同樣的 bucket，刪掉一個(gè)元素的同時(shí)，也會被其他元素的一部分 bucket 給刪掉。因此基于 Bitmap 實(shí)現(xiàn)的布隆過濾器是不支持刪除的。

用 C# 實(shí)現(xiàn) Bitmap

在實(shí)現(xiàn)布隆過濾器之前，我們首先要實(shí)現(xiàn)一個(gè) Bitmap。

在 C# 中，我們并不能直接用 bit 作為最小的數(shù)據(jù)存儲單元，但借助位運(yùn)算的話，我們就可以基于其他數(shù)據(jù)類型來表示，比如 byte。下文用 byte 作為例子來描述 Bitmap 的實(shí)現(xiàn)，但不僅限于 byte，int、long 等等也是可以的。

位運(yùn)算

下面是 C# 中位運(yùn)算的簡單介紹：

符號描述運(yùn)算規(guī)則
&與兩個(gè)位都為1時(shí)，結(jié)果才為1
|或兩個(gè)位都為0時(shí)，結(jié)果才為0
^異或兩個(gè)位相同為0，相異為1
~取反0變1，1變0
<<左移各二進(jìn)位全部左移若干位，低位補(bǔ)0
>>右移各二進(jìn)位全部右移若干位，高位補(bǔ)0

一般來說，我們要進(jìn)行位運(yùn)算計(jì)算的數(shù)據(jù)通常都是由多個(gè)二進(jìn)位組成的。對兩個(gè)數(shù)字使用 &、|、^ 這三個(gè)運(yùn)算符時(shí)，需要對齊兩個(gè)數(shù)字的右邊，一位位地進(jìn)行計(jì)算。

// 0b 代表值用二進(jìn)制表示數(shù)字
short a =                     0b0111111111111001;
byte  b =                            0b011111111;
short c = (short)(a & b);  // 0b0111111111111001
short d = (short)(a | b);  // 0b0111111111111111
short e = (short)(a ^ b);  // 0b0000000000000110
byte  f = (byte)~b;                  0b011111111;
short g = (short)(b << 1); // 0b0000000111111111;
short h = (short)(b >> 1); // 0b0000000001111111;

利用位運(yùn)算創(chuàng)建 Bitmap

借助 byte 實(shí)現(xiàn) Bitmap，也就是要能夠修改和查看 byte 上的每一個(gè) bit 的值，同時(shí)，修改要能夠?qū)崿F(xiàn)冪等。

1.指定位設(shè)置成 1
按前面說的位運(yùn)算的規(guī)則，是不能夠單獨(dú)修改 bit 序列中某一位的。位運(yùn)算需要從右到左一對對計(jì)算。
使用 | 可以實(shí)現(xiàn)這個(gè)功能。假設(shè)我們要改變從右開始下標(biāo)為 3（初始位置0） 的 bit 的值，則需要準(zhǔn)備一個(gè)該位置為 1，其他位置都是 0 的 bit 序列，與要改變的 bit 序列進(jìn)行 | 運(yùn)算。

// 為了將 a 的右邊數(shù)起第 3 位改成 1，需要準(zhǔn)備一個(gè) b
byte a =            0b010100010;
byte b = 1 << 3; // 0b000001000
a |= b;          // 0b010101010

2.指定位設(shè)置成 0
和設(shè)置成 1 正好相反，需要準(zhǔn)備一個(gè)指定位置為 0，其他位置都是 1 的 bit 序列，與要改變的 bit 序列進(jìn)行 & 運(yùn)算。

byte a =            0b010101010;
byte b = 1 << 3; // 0b000001000
b = ~b;          // 0b111110111
a &= b;          // 0b010100010

3.查看指定位的值
利用 & 運(yùn)算符，只要計(jì)算結(jié)果不為 0，就代表指定位置的值為 1。

byte a =            0b010101010;
byte b = 1 << 3; // 0b000001000;
a &= b;          // 0b000001000;

了解了基本的操作之后，我們把數(shù)據(jù)存儲到 byte 數(shù)組上。

class Bitmap
{
    private readonly byte[] _bytes;
    private readonly long _capacity;

    public Bitmap(long capacity)
    {
        _capacity = capacity;
        _bytes = new byte[_capacity / 8 + 1];
    }

    public long Capacity => _capacity;

    public void Set(long index)
    {
        if (index >= _capacity)
        {
            throw new IndexOutOfRangeException();
        }

        // 計(jì)算出數(shù)據(jù)存在第幾個(gè) byte 上
        long byteIndex = index / 8;
        // 計(jì)算出數(shù)據(jù)存在第幾個(gè) bit 上
        int bitIndex = (int)(index % 8);
        _bytes[byteIndex] |= (byte)(1 << bitIndex);
    }

    public void Remove(long index)
    {
        if (index >= _capacity)
        {
            throw new IndexOutOfRangeException();
        }

        long byteIndex = index / 8;
        int bitIndex = (int)(index % 8);
        _bytes[byteIndex] &= (byte)~(1 << bitIndex);
    }

    public bool Get(long index)
    {
        if (index >= _capacity)
        {
            throw new IndexOutOfRangeException();
        }

        long byteIndex = index / 8;
        int bitIndex = (int)(index % 8);

        return (_bytes[byteIndex] & (byte)(1 << bitIndex)) != 0;
    }
}

用 C# 實(shí)現(xiàn) 布隆過濾器

有了 Bitmap，我們再把 Hash 函數(shù)的實(shí)現(xiàn)準(zhǔn)備好，一個(gè)簡單的布隆過濾器就可以完成了。這里，我們參考 guava 這個(gè) java 庫的實(shí)現(xiàn)。

https://github.com/google/guava/blob/master/guava/src/com/google/common/hash/BloomFilter.java

MurmurHash3 的使用

我們使用和 guava 一樣的 MurmurHash3 作為 Hash 函數(shù)的實(shí)現(xiàn)。

下面是筆者在 github 上找到的一個(gè)可用實(shí)現(xiàn)。

https://github.com/darrenkopp/murmurhash-net

使用這個(gè)庫，我們可以將任意長的 byte 數(shù)組轉(zhuǎn)換成 128 位的二進(jìn)制位，也就是 16 byte。

byte[] data = Guid.NewGuid().ToByteArray(); 
// returns a 128-bit algorithm using "unsafe" code with default seed
HashAlgorithm murmur128 = MurmurHash.Create128(managed: false);
byte[] hash = murmur128.ComputeHash(data);

將任意類型的 key 轉(zhuǎn)換為 byte 數(shù)組

Funnel 與 Sink 的定義

我們需要將各種類型 key 轉(zhuǎn)換成 MurmurHash 能夠直接處理的 byte 數(shù)組。為此我們參考 guava 引入下面兩個(gè)概念：

1.Funnel：將各類數(shù)據(jù)轉(zhuǎn)換成 byte 數(shù)組，包括 int、bool、string 等built-in 類型及自定義的復(fù)雜類型。

2.Sink：Funnel 的核心組件，作為數(shù)據(jù)的緩沖區(qū)。Funnel 在將自定義的復(fù)雜類型實(shí)例轉(zhuǎn)換成 byte 數(shù)組時(shí)，就需要將數(shù)據(jù)拆解分批寫入 sink。

Funnel 可以定義成如下的委托，接受原始值，并將其寫入 sink 中。

delegate void Funnel<in T>(T from, ISink sink);

Sink 將不同類型的數(shù)據(jù)轉(zhuǎn)換成 byte 數(shù)組并匯總到一起。

interface ISink
{
    ISink PutByte(byte b);
    
    ISink PutBytes(byte[] bytes);

    ISink PutBool(bool b);
    
    ISink PutShort(short s);

    ISink PutInt(int i);

    ISink PutString(string s, Encoding encoding);

    ISink PutObject<T>(T obj, Funnel<T> funnel);

    /// ... 其他 built-in 類型，讀者可自行補(bǔ)充
}

簡單的 Funnel 實(shí)現(xiàn)如下所示：

public class Funnels
{
    public static Funnel<string> StringFunnel = (from, sink) =>
        sink.PutString(from, Encoding.UTF8);
    
    public static Funnel<int> IntFunnel = (from, sink) =>
        sink.PutInt(from);
}

自定義復(fù)雜類型的 Funnel 實(shí)現(xiàn)則可以數(shù)據(jù)拆解分批寫入 sink。復(fù)雜類型的實(shí)例成員依舊可能是復(fù)雜類型，因此我們要在 Sink 上實(shí)現(xiàn)一個(gè) PutObject 來提供套娃式拆解。

Funnel<Foo> funnelFoo = (foo, sink) =>
{
    sink.PutString(foo.A, Encoding.UTF8);
    sink.PutInt(foo.B);
    
    Funnel<Bar> funnelBar = (bar, barSink) => barSink.PutBool(bar.C);
    sink.PutObject(foo.Bar, funnelBar);
};

class Foo
{
    public string A { get; set; }

    public int B { get; set; }

    public Bar Bar { get; set; }
}

class Bar
{
    public bool C { get; set; }
}

Sink 的實(shí)現(xiàn)

Sink 的核心是 byte 數(shù)組緩沖區(qū)的實(shí)現(xiàn)，利用 ArrayPool 我們可以很方便的實(shí)現(xiàn)一個(gè) ByteBuffer。

class ByteBuffer : IDisposable
{
    private readonly int _capacity;
    private readonly byte[] _buffer;
    private int _offset;
    private bool _disposed;

    public ByteBuffer(int capacity)
    {
        _capacity = capacity;
        _buffer = ArrayPool<byte>.Shared.Rent(capacity);
    }

    public void Put(byte b)
    {
        CheckInsertable();
        _buffer[_offset] = b;
        _offset++;
    }

    public void Put(byte[] bytes)
    {
        CheckInsertable();
        bytes.CopyTo(_buffer.AsSpan(_offset, bytes.Length));
        _offset += bytes.Length;
    }

    public void PutInt(int i)
    {
        CheckInsertable();
        BinaryPrimitives.WriteInt32BigEndian(GetRemainingAsSpan(), i);
        _offset += sizeof(int);
    }
    
    public void PutShort(short s)
    {
        CheckInsertable();
        BinaryPrimitives.WriteInt32BigEndian(GetRemainingAsSpan(), s);
        _offset += sizeof(short);
    }

    // ... 其他的 primitive type 的實(shí)現(xiàn)

    public Span<byte> GetBuffer() =>
        _buffer.AsSpan(.._offset);

    public bool HasRemaining() => _offset < _capacity;

    public void Dispose()
    {
        _disposed = true;
        ArrayPool<byte>.Shared.Return(_buffer);
    }

    private void CheckInsertable()
    {
        if (_disposed)
        {
            throw new ObjectDisposedException(typeof(ByteBuffer).FullName);
        }

        if (_offset >= _capacity)
        {
            throw new OverflowException("Byte buffer overflow");
        }
    }

    private Span<byte> GetRemainingAsSpan() => _buffer.AsSpan(_offset..);
}

Sink 則是對 ByteBuffer 的進(jìn)一步封裝，來適配當(dāng)前使用場景。

class Sink : ISink, IDisposable
{
    private readonly ByteBuffer _byteBuffer;

    /// <summary>
    /// 創(chuàng)建一個(gè)新的 <see cref="Sink"/> 實(shí)例
    /// </summary>
    /// <param name="expectedInputSize">預(yù)計(jì)輸入的單個(gè)元素的最大大小</param>
    public Sink(int expectedInputSize)
    {
        _byteBuffer = new ByteBuffer(expectedInputSize);
    }

    public ISink PutByte(byte b)
    {
        _byteBuffer.Put(b);
        return this;
    }

    public ISink PutBytes(byte[] bytes)
    {
        _byteBuffer.Put(bytes);
        return this;
    }

    public ISink PutBool(bool b)
    {
        _byteBuffer.Put((byte)(b ? 1 : 0));
        return this;
    }

    public ISink PutShort(short s)
    {
        _byteBuffer.PutShort(s);
        return this;
    }

    public ISink PutInt(int i)
    {
        _byteBuffer.PutInt(i);
        return this;
    }

    public ISink PutString(string s, Encoding encoding)
    {
        _byteBuffer.Put(encoding.GetBytes(s));
        return this;
    }

    public ISink PutObject<T>(T obj, Funnel<T> funnel)
    {
        funnel(obj, this);
        return this;
    }

    public byte[] GetBytes() => _byteBuffer.GetBuffer().ToArray();

    public void Dispose()
    {
        _byteBuffer.Dispose();
    }
}

k 個(gè) Hash 函數(shù)與 布隆過濾器 實(shí)現(xiàn)

上文提到了 布隆過濾器 通過 k 個(gè) hash 函數(shù)來解決 hash 沖突問題。實(shí)踐中，我們可以把一次 murmur hash 的計(jì)算結(jié)果（16 byte）拆分為兩部分并轉(zhuǎn)換為 long 類型（一個(gè) long 是 8 byte）。

這兩部分結(jié)果分別保存到 hash2 和 hash3，第 k 個(gè) hash 函數(shù)是對 hash2 和 hash3 的重新組合。

hash(k) = hash2 + (k-1) * hash3

public class BloomFilter<T>
{
    private readonly int _hashFunctions;
    private readonly Funnel<T> _funnel;
    private readonly int _expectedInputSize;
    private readonly Bitmap _bitmap;
    private readonly HashAlgorithm _murmur128;

    /// <summary>
    /// 創(chuàng)建一個(gè)新的 <see cref="BloomFilter"/> 實(shí)例
    /// </summary>
    /// <param name="funnel">與插入元素類型相關(guān)的<see cref="Funnel"/>的實(shí)現(xiàn)</param>
    /// <param name="buckets">BloomFilter 內(nèi)部 Bitmap 的 bucket 數(shù)量，越大，誤判率越低</param>
    /// <param name="hashFunctions">hash 函數(shù)的數(shù)量，越多，誤判率越低</param>
    /// <param name="expectedInputSize">預(yù)計(jì)插入的單個(gè)元素的最大大小</param>
    public BloomFilter(Funnel<T> funnel, int buckets, int hashFunctions = 2, int expectedInputSize = 128)
    {
        _hashFunctions = hashFunctions;
        _funnel = funnel;
        _expectedInputSize = expectedInputSize;

        _bitmap = new Bitmap(buckets);
        _murmur128 = MurmurHash.Create128(managed: false);
    }

    public void Add(T item)
    {
        long bitSize = _bitmap.Capacity;

        var (hash1, hash2) = Hash(item);

        long combinedHash = hash1;
        for (int i = 0; i < _hashFunctions; i++)
        {
            _bitmap.Set((combinedHash & long.MaxValue) % bitSize);
            combinedHash += hash2;
        }
    }


    public bool MightContains(T item)
    {
        long bitSize = _bitmap.Capacity;

        var (hash1, hash2) = Hash(item);

        long combinedHash = hash1;
        for (int i = 0; i < _hashFunctions; i++)
        {
            if (!_bitmap.Get((combinedHash & long.MaxValue) % bitSize))
            {
                return false;
            }

            combinedHash += hash2;
        }

        return true;
    }


    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private (long Hash1, long Hash2) Hash(T item)
    {
        byte[] inputBytes;
        using (var sink = new Sink(_expectedInputSize))
        {
            sink.PutObject(item, _funnel);
            inputBytes = sink.GetBytes();
        }

        var hashSpan = _murmur128.ComputeHash(inputBytes).AsSpan();

        long lowerEight = BinaryPrimitives.ReadInt64LittleEndian(hashSpan.Slice(0,8));
        long upperEight = BinaryPrimitives.ReadInt64LittleEndian(hashSpan.Slice(8,8));
        return (lowerEight, upperEight);
    }
}

擴(kuò)展

帶計(jì)數(shù)器的布隆過濾器

上文講到基于 Bitmap 實(shí)現(xiàn)的布隆過濾器不支持刪除，但如果把 Bitmap 這個(gè) bit 數(shù)組換成 n 個(gè) bit 作為一個(gè)bucket的數(shù)組，那單個(gè) bucket 就具備了計(jì)數(shù)能力。這樣刪掉一個(gè)元素的時(shí)候，就是在這個(gè)計(jì)數(shù)器上減一，借此能夠在有限的范圍內(nèi)實(shí)現(xiàn)帶刪除功能的布隆過濾器，代價(jià)是，存儲空間會變成原來的 n 倍。

分布式布隆過濾器實(shí)現(xiàn)方案

如果你有布隆過濾器的實(shí)際使用需求，并且是在分布式環(huán)境，筆者推薦下面這個(gè)庫，它是作為 redis 的插件提供的，詳情點(diǎn)擊下方鏈接。https://github.com/RedisBloom/RedisBloom 

代碼地址

為方便學(xué)習(xí)，本文所有的代碼均已整理在 github：https://github.com/eventhorizon-cli/EventHorizon.BloomFilter

到此這篇關(guān)于C#實(shí)現(xiàn)從位圖到布隆過濾器的方法的文章就介紹到這了,更多相關(guān)C#位圖到布隆過濾器內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評論