c# - 对于具有 +128 位 key 的布隆过滤器，我应该使用什么哈希函数？

Question

https://github.com/joeyrobert/bloomfilter使用 Random 类作为哈希函数，它是 performance killer .
我想要做的是用 byte[]s 而不是通用参数 (T) 输入类并摆脱

    private int Hash(T item) {
        return item.GetHashCode();
    }

我知道这会带来巨大的性能优势，但我不知道如何在此处替换 _random.Next(_bitSize):

#region Public Methods
/// <summary>
/// Adds an item to the bloom filter.
/// </summary>
/// <param name="item">Item to be added</param>
public void Add(T item)
{
    _random = new Random(Hash(item));

    for (int i = 0; i < _numberOfHashes; i++)
        _bitArray[_random.Next(_bitSize)] = true;
}

使用一些非延迟代码行，每个位不占用数千个 CPU 周期。

我知道代码还有很多其他问题可以使它更快/更安全。我已经(大部分)修复了它们，只是在推送我的更改之前卡在了最后一个问题上。
非常感谢任何帮助。

Answer 1

我不明白您为什么要在这里使用随机数生成器...但是，我可以帮助您加快速度。

布隆过滤器基本上是一个位向量，您可以在其中设置位。如果您想弄清楚某个项目是否存在，如果该项目可能存在，布隆过滤器会给您一个 true，如果该项目肯定不存在，则会给您一个 false .

(我在一个简单的文本编辑器中执行此操作，因此代码中可能存在一些错误)

我将假设您的哈希空间可以使用 32 位整数计算；如果您有一个非常大的 bloom 表，您可能希望使用 64 位整数。

布隆过滤器最简单(也可能是最快)的实现是:

byte[] bloomFilter = new byte[MyBloomFilterSize];

foreach (var item in myItems) 
{
    int hash = Hash(item) & 0x7FFFFFFF;
    int bit = 1 << (hash & 7); // you have 8 bits
    int index = (hash >> 3) % MyBloomFilterSize;
    bloomFilter[hash % MyBloomFilterSize] |= bit;
}

您可以尝试将 byte[] 更改为 uint[] 或 ulong[]；我不确定这是否有所作为。

如果你想检查一个项目是否存在，你计算相同的索引和位，并得到结果。

public bool PossiblyExists(MyItem item)
{
    int hash = Hash(item) & 0x7FFFFFFF;

    int bit = 1 << (hash & 7); // you have 8 bits
    int index = (hash >> 3) % MyBloomFilterSize;
    return (bloomFilter[hash % MyBloomFilterSize] & bit) != 0;
}

这里唯一剩下的就是计算哈希值的速度。如果您使用的是整数，我会简单地将它乘以一个大素数；如果您使用的是 SHA256 固定长度 byte[](您似乎正在这样做)，则需要将其设为整数(或长整数)。

我在这里使用 Buffer.BlockCopy 的小技巧来转换类型。为了安全起见，我更喜欢使用数据中的几个字节，但由于 SHA256 应该已经是随机的，所以一个简单的 BitConverter.ToInt32(data, [0..28]) 也应该可以解决问题。

public int CalculateHash(byte[] data) 
{
    // Data = >128 bits = >16 bytes -- which is the same as >4 integers

    int[] tmp = new int[4];
    Buffer.BlockCopy(data, 0, tmp, 0, data.Length);
    return tmp[0] ^ tmp[1] ^ tmp[2] ^ tmp[3];
}

应该这样做。