背景故事什么的没有。

Alice

Bloom Filter 布隆过滤器

用于判断集合中是否存在某个值，但有可能误判（将不存在判断为存在）

原理类似 Hash Table，开一个大小为 \(n\) 的 bitset，设计 \(k\) 个 Hash 函数，插入元素时将 bitset 中 Hash 值对应的位设为 \(1\)。查询时若 \(k\) 个位置均为 \(1\) 则认为存在。

优点：内存占用小，时间复杂度稳定 \(O(k)\) 缺点：不能删除（如果需要删除可以将 bitset 改为普通计数数组，但这样内存优势就不大了），存在误判

Bloom Filter Arguments Analysis

考虑插入 \(m\) 个元素后，某个位置为 \(1\) 的概率为

\[p_1 = 1 - p_0 = 1 - (1 - \frac1n)^{mk} \approx 1 - e^{-\frac{mk}{n}}\]

其中用到 \(\lim\limits_{n\rightarrow +\infty}(1 - \frac{1}{n})^{-n} = e\)

此时再插入一个元素，且这个元素本不在集合中，误判（\(k\) 次 Hash 结果对应位均为 \(1\)）的概率为

\[p = p_1^k = (1 - e^{-\frac{mk}{n}})^k\]

可以求导求最小值，也可以稍微变换一下：

\[p = e^{k\ln(1 - e^{-\frac{mk}{n}})} = e^{-\frac{n}{m}\ln a \ln(1 - a)}\]

\[a = e^{-\frac{mk}{n}}\]

当 \(a = 1 - a\)，即 \(k = \frac{n}{m}\ln 2\) 时误判率 \(p = e^{-\frac nm \ln^22}\) 最小

同时也可以解得 \(n = -\frac{m\ln p}{\ln^22}\)，可以根据需求决定 \(n\) 的大小

Bloom Filter Implementation

根据自己的理解简单使用 C++ 实现了一个 std::string 的 Bloom Filter

不是线程安全的，想做的话加锁非常简单

话说我一直在想对于简单的申请数组情况到底该不该用智能指针呢，感觉完全没必要，很麻烦，然而网上又推崇所有指针都用智能指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <functional>
#include <iostream>
#include <memory>
#include <random>
#include <string>
#include <vector>

namespace bloom {

static std::mt19937_64
    randnum_gen_(std::chrono::system_clock::now().time_since_epoch().count());

const size_t kMaxBitmapSize = UINT32_MAX;
const double kDefaultMisProbability = 0.2f;
const double kLn2 = std::log(2);
const size_t kHashBase = 13331;

auto create_hash_function(const size_t seed, const size_t range)
    -> std::function<size_t(const std::string &)> {
  static const auto original_function = [&](const size_t seed,
                                            const size_t range,
                                            const std::string &s) -> size_t {
    size_t result = seed;
    for (const auto c : s) {
      result = result * kHashBase + c;
    }
    return result % range;
  };
  return std::bind(original_function, seed, range, std::placeholders::_1);
}

class Bitmap {
private:
  const size_t size_;

  const size_t len_;

  uint8_t *bitmap_;

public:
  explicit Bitmap(const size_t size) : size_(size), len_((size + 7) >> 3) {
    assert(size > 0);
    bitmap_ = new uint8_t[len_];
    memset(bitmap_, 0, len_);
  }

  ~Bitmap() { delete[] bitmap_; }

  Bitmap(const Bitmap &) = delete;
  Bitmap &operator=(const Bitmap &) = delete;

  auto size() const noexcept -> size_t { return size_; }

  void Set(const size_t pos) {
    assert(pos < size_);
    bitmap_[pos >> 3] |= 1 << (pos & 7);
  }

  auto Get(const size_t pos) const -> int {
    assert(pos < size_);
    return bitmap_[pos >> 3] >> (pos & 7) & 1;
  }
};

class BloomFilter {
private:
  size_t element_size_;

  size_t bitmap_size_;

  size_t hash_num_;

  // Misjudgement Probability
  double mis_probability_;

  std::vector<std::function<size_t(const std::string &)>> hash_function_;

  Bitmap bitmap_;

public:
  explicit BloomFilter(const size_t element_size, const size_t bitmap_size,
                       const size_t hash_num = 0)
      : element_size_(element_size), bitmap_size_(bitmap_size),
        hash_num_(hash_num),
        mis_probability_(std::exp(-static_cast<double>(bitmap_size) /
                                  element_size * kLn2 * kLn2)),
        bitmap_(bitmap_size) {
    if (hash_num == 0) {
      hash_num_ =
          std::max(1ULL, static_cast<size_t>(static_cast<double>(bitmap_size) /
                                             element_size * kLn2));
    }
    for (size_t i = 0; i < hash_num_; ++i) {
      hash_function_.push_back(
          create_hash_function(randnum_gen_(), bitmap_size));
    }
  }

  ~BloomFilter() {}

  BloomFilter(const BloomFilter &) = delete;
  BloomFilter &operator=(const BloomFilter &) = delete;

  auto element_size() const noexcept -> size_t { return element_size_; }

  auto bitmap_size() const noexcept -> size_t { return bitmap_size_; }

  auto hash_num() const noexcept -> size_t { return hash_num_; }

  auto mis_probability() const noexcept -> double { return mis_probability_; }

  void Insert(const std::string &s) {
    for (const auto &func : hash_function_) {
      bitmap_.Set(func(s));
    }
  }

  auto Contains(const std::string &s) const -> bool {
    for (const auto &func : hash_function_) {
      if (bitmap_.Get(func(s)) == 0) {
        return false;
      }
    }
    return true;
  }
};
} // namespace bloom

int main() {
  bloom::BloomFilter set(10, 100);
  std::cout << set.hash_num() << std::endl;
  // 6
  std::cout << set.mis_probability() << std::endl;
  // 0.00819255

  std::vector<std::string> strs = {
      "Alice", "Bob", "Carol", "Tairitsu", "Hikari", "Mizuki", "A", "B", "C"};
  for (const auto &s : strs) {
    set.Insert(s);
  }

  std::cout << set.Contains("Alice") << std::endl;
  // 1
  std::cout << set.Contains("alice") << std::endl;
  // 0
  return 0;
}

Cuckoo Filter 布谷鸟过滤器

Cuckoo Hashing

在那之前先看看 Cuckoo Hashing 是个什么东西。简单来说，设计了两个（或多个） Hash 函数，分别对应两个表，插入元素时对于两个表中两个位置：

  • 都为空：随机插入一个
  • 一个为空：插入空的那一个
  • 都不为空：随机拿出一个并插入，对拿出的进行递归 Cuckoo Hashing（若次数过多则失败）

Cuckoo Filter

类似 Cuckoo Hashing，Cuckoo Filter 中哈希表（只有一张）每一项变为了一个桶，可以存放多个数据。插入时桶中不存元素，而存相应的指纹 \(f\)（一般是 Hash 值截取几位）

不同于朴素的 Hash，Cuckoo Filter 中的两个 Hash 函数为：

\[p_1 = hash(x)\]

\[p_2 = p_1 \oplus hash(f)\]

这样对于其中一个位置就可以通过异或得到另一个位置

另外可以看出上述 Hash 方法要求哈希表大小为 \(2\) 的次幂，至于为什么要用 \(hash(f)\) 而不是 \(f\) 是因为指纹可能值域太小

查找时计算并遍历找指纹即可

优点：支持删除，查询效率高（只有 \(2\) 次，并且内存连续），要求低错误率时内存小 缺点：（若要支持删除）同一元素不能多次插入，插入效率低，哈希表大小必须为 \(2\) 的次幂，插入可能失败（概率低）

参数的选择不像 Bloom Filter 那样好分析，一种办法是自己写个 Benchmark 测试

至于代码区别和 Bloom Filter 不会很大，就不在这里实现了