c - C 中的快速布隆过滤器 - 64 位整数，高频初始化/查询/销毁循环

Question

我需要一个布隆过滤器实现，用于大型项目的一部分。整个项目是用 C 编写的(而且只有 C!没有 C++)，不幸的是，我没能找到任何像样的基于 C 的布隆过滤器实现(除了 proof-of-concept 实现)。

我的布隆过滤器要求:
1. 包含布隆过滤器的模块每 50 毫秒运行一次。
整个模块需要在5-6ms内执行完毕，
这意味着整个布隆过滤器代码必须在 3 毫秒内完成。
2. 元素是64位整数
3. 我总共有不到 8k 个元素(包括插入/查询)
常见情况是数百次插入过滤器，以及 1000-1500 次查询。

每隔 50 毫秒，我会收到两组(W，R)64 位整数。我需要找到在这个时期收到的 W 和 R 之间的交集(IOW，布隆过滤器必须在每个时期重新开始)。下面的代码显示了一般的控制流程

sleep(50ms)
...module code..
clear(bloomfilter) /* basically a memset(0) on bloomfilter bitmap */
W = getListW()
for each entry in W
  insert(bloomfilter, entry)
R = getListR()
for each entry in R
   if (present(bloomfilter, entry))
      ..do something with entry..
..rest of module code..

现在，我看到几篇论文声称可以对非常大的数据集进行快速布隆过滤器操作。但是我的要求不一样。我需要快速播种(插入 W)和快速查询。哈希函数是另一个问题。由于时间限制，我买不起像 SHA1 这样的重型哈希函数。

Answer 1

您需要保持简单。由于您处理的是少量元素，并且它们是 64 位整数(在 32 位机器上比较快，在 64 位机器上快如闪电)。作为第一步，我会使用 64K 元素的哈希表。插入时，通过将每个 16 位片段异或在一起以获得表索引，对 64 位 int 进行 16 位“散列”。如果这还不够快，请分析它以找出原因。

这听起来不像使用 bloom 过滤器那样性感。但实际上，您只处理 8K 整数。这是我现在编写的一些代码(没有尝试编译它)。假设插入数字的随机分布可能非常快，如果任何插入为 0，它就不会工作。

uint64_t table[65536] = {0};

void clear()
{
    memset(table, 0, sizeof(table));
}

uint16_t hash(uint64_t val)
{
    assert(ele != 0);
    uint16_t *parts = (uint16_t*)&ele;
    uint16_t h = 0x5AA5;
    h = h * 131 + parts[0];
    h = h * 131 + parts[1];
    h = h * 131 + parts[2];
    h = h * 131 + parts[3];
    return h;
}

void insert(uint64_t ele)
{
    uint16_t h = hash(ele);
    while (table[h])
        ++h;
    table[h] = ele;
}

int find(uint64_t ele) 
{
    int res = 0;
    uint16_t h = hash(ele);
    while (table[h] != ele)
    {
        if (!table[h])
            return 0;
        ++h;
    }
    return 1;
}

如果您的插入不是随机分布的，您将需要更好的冲突解决方案。您还可以想出更好的散列方法。