CMU 15-445 Project 0 Primer: Several Probabilistic Data Structures

2026-06-07

关于 CMU 15-445 Project 0 Primer，记录几个概率性数据结构。

最近一直在看 CMU 15-445 的 YT 课程视频（B站中文精翻）和完成 BusTub 项目。我觉得课程很好，但视频内容经常需要辅助 AI 具体了解才能看懂，Bustub 项目也非常有挑战性好难。总体上是我太菜，课程非常好。

Andy Pavlo 和他的助教们，每年都会更新 BusTub 的内容（因为 BusTub 是公开的，大概是为了避免抄袭、以及提前完成？），按 Git History 是秋季（暑假）更新 BusTub，春季基本不会动。

BusTub Contributors

以下实现了 2025 和 2024 的 Project 0 Primer 的数据结构：

以及最基础的 Bloom Filter 和可扩展的 Scalable Bloom Filter。

由于 Trie 和 Skip List 感觉会比较麻烦，今天先不写。

Bloom Filter

布隆过滤器可用于检索一个元素是否在一个集合中，具有空间效率高和查询速度快的特点，但存在一定的假阳率，取决于哈希函数的数量和过滤器占用空间的大小。

若用哈希表，可以精确的判断，原因在于会处理冲突的情况。但如果不处理冲突，只要有一个元素映射到某个位置，就设置这个位置被占用，那么其他映射到相同位置的，不存在的元素就会被误判，这就是假阳率的来源。

那么进一步改进，则可以使用多个哈希函数，只有当所有对应位置都被占用时，才认为元素存在，以降低假阳率。

插入和查询的时间复杂度都是 $O(k)$ ，可惜缺陷在于无法删除元素，以及假阳率的存在（但这是不可避免的，Andy 也总是在课程里面说没有免费的午餐）。

对于一个实际不存在的元素，当其每个对应的 $k$ 个位置全部都刚好被置为了 1 时，就会被误判为存在，又因为假设哈希函数是均匀分布的，所以可以独立考虑每个位置被置为 1 的概率。

其中 $m$ 是 Bloom Filter 的位数组大小， $n$ 是插入的元素数量， $k$ 是哈希函数的数量。

插入一个元素时，对于一个特定位置，被单一哈希函数选中的概率是，

\frac{1}{m}

没有选中的概率则是

1 - \frac{1}{m}

插入一个元素需要经过 $k$ 个哈希函数的置 1，所以某个位置仍然为 0 的概率是

(1 - \frac{1}{m})^k

那么插入 $n$ 个元素后，某个位依然为 0 的概率是

P_0 = \left(1 - \frac{1}{m}\right)^{kn}

根据重要极限，

\lim_{m \to \infty} \left(1 - \frac{1}{m}\right)^{m} = e^{-1}

所以对于较大的 $m$ 可以近似为（在指数补一个 $1/m$ ）：

P_0 \approx e^{-\frac{kn}{m}}

所以某个位置被置为 1 的概率是

P_1 = 1 - P_0 \approx 1 - e^{-\frac{kn}{m}}

则误判时， $k$ 个位置都被置为 1 的概率是

P_{fp} = P_1^k \approx \left(1 - e^{-\frac{kn}{m}}\right)^k

一般来说，预期元素数量 $n$ 和位数组大小 $m$ 是给定的，那么应该向最小化 $P_{fp}$ 的方向找出 $k$ 的最优解。

\ln P_{fp} = k \ln \left(1 - e^{-\frac{kn}{m}}\right)

取 $x = e^{-\frac{kn}{m}}$ ，则 $k = -\frac{m}{n} \ln x$ ，代入上式：

\ln P_{fp} = -\frac{m}{n} \ln x \cdot \ln (1 - x)

实质上是求 $f(x) = \ln x \cdot \ln (1 - x)$ 的最大值，使得 $P_{fp}$ 最小。

易得 $f(x)$ 在 $x = 0.5$ 处取得最大值，此时 $k = -\frac{m}{n} \ln 0.5 = \frac{m}{n} \ln 2$ 。

所以

k^* = \frac{m}{n} \ln 2

当然在实际应用中， $k$ 只能取整数

Bloom Filter 无法自动拓展，随着元素数量的增加，假阳率会逐渐升高。为了解决这个问题，可以使用 Scalable Bloom Filter，它通过维护多个 Bloom Filter 来实现动态扩展。

Bloom filter false positive probability

当一个 Bloom Filter 的容量达到预设的阈值时，Scalable Bloom Filter 会创建一个新的 Bloom Filter，并将新元素插入到新的 Bloom Filter 中。

查询时，Scalable Bloom Filter 会依次查询所有 Bloom Filter，只要其中一个 Bloom Filter 返回存在，就认为元素存在。

创建新 Bloom Filter 时，可以设置一个缩放因子 $r$ ，每次创建新 Bloom Filter 时，其大小是前一个 Bloom Filter 的 $r$ 倍（以免 filters 数量线性增长，查询时要遍历检查的 filter 太多）。

以下是 Bloom Filter 的实现（完整见 Bloom Filter Gist）：

template <typename T>
class BloomFilter {
public:
    BloomFilter(const int filter_size, const int hash_count)
        : filter_size_(filter_size), hash_count_(hash_count), inserted_count(0) {
        bits_.assign(filter_size_, false);
    }

    void Insert(const T &value) {
        for (int i = 0; i < hash_count_; i++) {
            const auto idx = double_hash<T>(value, i, filter_size_);
            bits_[idx] = true;
        }
        inserted_count++;
    }

    auto Lookup(const T &value) -> bool {
        for (int i = 0; i < hash_count_; i++) {
            const auto idx = double_hash<T>(value, i, filter_size_);
            if (!bits_[idx]) {
                return false;
            }
        }
        return true;
    }

    auto GetCapacity() const -> int {
        return static_cast<int>(filter_size_ * 0.693 / hash_count_);
    }

    auto GetFilterSize() const -> int {
        return filter_size_;
    }

    auto GetHashCount() const -> int {
        return hash_count_;
    }

    auto GetInsertedCount() const -> int {
        return inserted_count;
    }

private:
    int filter_size_;
    int hash_count_;
    int inserted_count;
    std::vector<bool> bits_;
};

template <typename T>
class ScalableBloomFilter {
public:
    ScalableBloomFilter(const double capacity_threshold = 0.8) : capacity_threshold_(capacity_threshold) {
        filters_.emplace_back(base_filter_size_, base_hash_count_);
    }

    void Insert(const T &value) {
        const int capacity = filters_.back().GetCapacity();
        const int items_in_current_filter_ = filters_.back().GetInsertedCount();
        const int current_filter_size_ = filters_.back().GetFilterSize();
        const int current_hash_count_ = filters_.back().GetHashCount();

        if (items_in_current_filter_ >= capacity * capacity_threshold_) {
            filters_.emplace_back(current_filter_size_ * 2, current_hash_count_ + 1);
        }

        filters_.back().Insert(value);
    }

    auto Lookup(const T &value) -> bool {
        for (auto &filter: filters_) {
            if (filter.Lookup(value)) {
                return true;
            }
        }
        return false;
    }

    auto GetFilterCount() const -> int {
        return filters_.size();
    }

private:
    std::vector<BloomFilter<T>> filters_;
    int base_filter_size_{1024};
    int base_hash_count_{8};
    double capacity_threshold_;
};

可以参考 Wikipedia Bloom filter

Count-min Sketch

上面的 Bloom Filter 是用来判断元素是否存在的，而 Count-min Sketch 则是用来估计元素出现的次数的。

CMU 15-445 的课程视频里面提到的一个例子是网站 IP 访问量估计，其他情况类似。

Count-min Sketch 使用一个二维数组来存储计数器。

假设二维数组的行数为 $d$ ，有 $d$ 个哈希函数，每个哈希函数对应一行；列数为 $w$ ，哈希值取模 $w$ 。

每个元素添加时，计算 $d$ 个哈希函数映射到不同的行，取其计算出来的列索引，在对应位置的计数器 +1。（总共更新 $d$ 个计数器）

查询元素时，如上找到 $d$ 个计数器，取其中的最小值作为元素添加的次数估计。

很显然，由于不同元素可能更新同一个计数器，计数器的值必然是等于或者高估的，所以取所有计数器的最小值作为估计值，是最接近真实值的。

直觉上，二维数组的大小直接决定误差大小。准确的来说，CM Sketch 的误差由两个参数来描述：精度误差 $\epsilon$ 和错误概率 $\delta$ 。

精度误差指的是估计值与真实值之间的允许误差比例，例如 $\epsilon = 0.01$ 表示估计值与真实值之间的误差不超过 1%。

错误概率 $\delta$ 则是指估计值超过精度误差的概率，例如 $\delta = 0.05$ 表示有 5% 的概率估计值会超过精度误差。

宽度 $w = \lceil \frac{e}{\epsilon} \rceil$
深度 $d = \lceil \ln(\frac{1}{\delta}) \rceil$

此处不讨论 $w$ 和 $d$ 的公式哪来的，~~看不懂~~

以下是 Count-min Sketch 的实现（完整见 Count-min sketch Gist）：

基于 Primer 改的，有 TopK 的功能，以及 thread-safe 实现 Insert

#include "count_min_sketch.h"

#include <algorithm>
#include <atomic>
#include <stdexcept>
#include <string>

/**
 * Constructor for the count-min sketch.
 *
 * @param width The width of the sketch matrix.
 * @param depth The depth of the sketch matrix.
 * @throws std::invalid_argument if width or depth are zero.
 */
template <typename KeyType>
CountMinSketch<KeyType>::CountMinSketch(uint32_t width, uint32_t depth)
    : width_(width), depth_(depth), sketch_(std::make_unique<std::atomic<size_t>[]>(width * depth)) {
  if (width == 0 || depth == 0) {
    throw std::invalid_argument("Width and depth must be greater than zero.");
  }
  for (size_t i = 0; i < depth_ * width_; ++i) {
    sketch_[i].store(0, std::memory_order_relaxed);
  }
  // Initialize seeded hash functions
  hash_functions_.reserve(depth_);
  for (size_t i = 0; i < depth_; i++) {
    hash_functions_.push_back(this->HashFunction(i));
  }
}

template <typename KeyType>
CountMinSketch<KeyType>::CountMinSketch(CountMinSketch &&other) noexcept : width_(other.width_), depth_(other.depth_) {
  sketch_ = std::move(other.sketch_);
  hash_functions_ = std::move(other.hash_functions_);
}

template <typename KeyType>
auto CountMinSketch<KeyType>::operator=(CountMinSketch &&other) noexcept -> CountMinSketch & {
  for (size_t i = 0; i < depth_ * width_; ++i) {
    sketch_[i].store(other.sketch_[i].load(std::memory_order_relaxed), std::memory_order_relaxed);
  }
  hash_functions_ = std::move(other.hash_functions_);
  return *this;
}

template <typename KeyType>
void CountMinSketch<KeyType>::Insert(const KeyType &item) {
  for (size_t row_index = 0; row_index < depth_; row_index++) {
    size_t col_index = hash_functions_[row_index](item);
    sketch_[row_index * width_ + col_index].fetch_add(1, std::memory_order_relaxed);
  }
}

template <typename KeyType>
void CountMinSketch<KeyType>::Merge(const CountMinSketch<KeyType> &other) {
  if (width_ != other.width_ || depth_ != other.depth_) {
    throw std::invalid_argument("Incompatible CountMinSketch dimensions for merge.");
  }
  for (size_t i = 0; i < depth_ * width_; ++i) {
    sketch_[i].fetch_add(other.sketch_[i].load(std::memory_order_relaxed), std::memory_order_relaxed);
  }
}

template <typename KeyType>
auto CountMinSketch<KeyType>::Count(const KeyType &item) const -> uint32_t {
  size_t min_count = SIZE_MAX;
  for (size_t row_index = 0; row_index < depth_; row_index++) {
    size_t col_index = hash_functions_[row_index](item);
    size_t value = sketch_[row_index * width_ + col_index].load(std::memory_order_relaxed);
    min_count = std::min(min_count, value);
  }
  return static_cast<uint32_t>(min_count);
}

template <typename KeyType>
void CountMinSketch<KeyType>::Clear() {
  for (size_t i = 0; i < depth_ * width_; ++i) {
    sketch_[i].store(0, std::memory_order_relaxed);
  }
}

template <typename KeyType>
auto CountMinSketch<KeyType>::TopK(uint16_t k, const std::vector<KeyType> &candidates)
    -> std::vector<std::pair<KeyType, uint32_t>> {
  std::vector<std::pair<KeyType, uint32_t>> result;
  result.reserve(candidates.size());
  for (const auto &item : candidates) {
    result.emplace_back(item, Count(item));
  }
  std::sort(result.begin(), result.end(), [](const auto &a, const auto &b) { return a.second > b.second; });
  if (result.size() > k) {
    result.resize(k);
  }
  return result;
}

// Explicit instantiations for all types used in tests
template class CountMinSketch<std::string>;
template class CountMinSketch<int64_t>;
template class CountMinSketch<int>;

#pragma once

#include <atomic>
#include <cstdint>
#include <functional>
#include <memory>
#include <utility>
#include <vector>

/**
 * @brief Combines two hash values to create a new hash.
 * Uses the boost hash_combine algorithm.
 */
inline size_t CombineHashes(size_t h1, size_t h2) {
  return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
}

template <typename KeyType>
class CountMinSketch {
 public:
  /** @brief Constructs a count-min sketch with specified dimensions
   * @param width Number of buckets
   * @param depth Number of hash functions
   */
  explicit CountMinSketch(uint32_t width, uint32_t depth);

  CountMinSketch() = delete;                                            // Default constructor deleted
  CountMinSketch(const CountMinSketch &) = delete;                      // Copy constructor deleted
  auto operator=(const CountMinSketch &) -> CountMinSketch & = delete;  // Copy assignment deleted

  CountMinSketch(CountMinSketch &&other) noexcept;                      // Move constructor
  auto operator=(CountMinSketch &&other) noexcept -> CountMinSketch &;  // Move assignment

  /**
   * @brief Inserts an item into the count-min sketch
   *
   * @param item The item to increment the count for
   * @note Updates the min-heap at the same time
   */
  void Insert(const KeyType &item);

  /**
   * @brief Gets the estimated count of an item
   *
   * @param item The item to look up
   * @return The estimated count
   */
  auto Count(const KeyType &item) const -> uint32_t;

  /**
   * @brief Resets the sketch to initial empty state
   *
   * @note Clears the sketch matrix, item set, and top-k min-heap
   */
  void Clear();

  /**
   * @brief Merges the current CountMinSketch with another, updating the current sketch
   * with combined data from both sketches.
   *
   * @param other The other CountMinSketch to merge with.
   * @throws std::invalid_argument if the sketches' dimensions are incompatible.
   */
  void Merge(const CountMinSketch<KeyType> &other);

  /**
   * @brief Gets the top k items based on estimated counts from a list of candidates.
   *
   * @param k Number of top items to return (will be capped at initial k)
   * @param candidates List of candidate items to consider for top k
   * @return Vector of (item, count) pairs in descending count order
   */
  auto TopK(uint16_t k, const std::vector<KeyType> &candidates) -> std::vector<std::pair<KeyType, uint32_t>>;

 private:
  /** Dimensions of the count-min sketch matrix */
  uint32_t width_;  // Number of buckets for each hash function
  uint32_t depth_;  // Number of independent hash functions
  /** Pre-computed hash functions for each row */
  std::vector<std::function<size_t(const KeyType &)>> hash_functions_;

  constexpr static size_t SEED_BASE = 15445;

  /**
   * @brief Seeded hash function generator
   *
   * @param seed Used for creating independent hash functions
   * @return A function that maps items to column indices
   */
  inline auto HashFunction(size_t seed) -> std::function<size_t(const KeyType &)> {
    return [seed, this](const KeyType &item) -> size_t {
      auto h1 = std::hash<KeyType>{}(item);
      auto h2 = CombineHashes(seed, SEED_BASE);
      return CombineHashes(h1, h2) % width_;
    };
  }

  std::unique_ptr<std::atomic<size_t>[]> sketch_;  // size = depth_ * width_
};

HyperLogLog

HyperLogLog 与以上两种的生态位也不同，目的是估计一个集合中不同元素的数量（基数估计）。

若要精确统计，则需要记录所有元素以供查询是否重复，但这会占用大量内存。

考虑一个抛硬币的情景，可以发现当第四次才抛出正面，前面三次都是反面时，那么这个序列的概率是 $\frac{1}{16}$ 。那么逆向过来可以理解为：要想得出这个序列，平均需要抛 16 次硬币。

那么对于元素取 Hash，记录所有元素的前导零的最大值 $R$ ，由于特定比特位只有 0 和 1 两个可能，就可以估计出不同元素的数量大约是 $2^(R+1)$ 。

但是很显然，单次伯努利试验的随机性太高，容易因为某个极端哈希值（例如一开始就连续出现很多个 0）导致估算结果出现巨大偏差。

为了降低误差，HyperLogLog 将哈希值分成 $m = 2 ^{b}$ 个桶（有 $b$ 个位用于分桶），每个桶记录前导零的最大值 $R_i$ （前导零不算用于分桶的 $b$ 位）。

计算 HyperLogLog 的估计值时，先计算每个桶的 $2^{R_i}$ 的估计值的调和平均值，乘以总共 $m$ 个分桶。

实际上看，会再乘一个修正因子 $\alpha _{m}$ 来调整估计值，具体的修正因子取值可以参考 HyperLogLog Wikipedia 的相关内容。

HLL 相比 LL（LogLog）算法的改进：LL 计算几何平均值，而 HLL 则是计算调和平均值，这样可以更好地抵消极端值的影响。

\displaystyle Z= {(\sum _{j=1}^{m}{2^{-M[j]}})}^{-1}

\displaystyle E=\alpha _{m}m^{2}Z

其中 $M[j]$ 就是分桶的前导零的最大值， $Z$ 是分桶的调和平均值， $E$ 则是最终的估计值。

实现如下：

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using hash_t = std::size_t;

template <typename T>
class HyperLogLog {
    public:
    HyperLogLog(size_t b): b_(b), m_(1 << b), registers(m_, 0) {}

    void Add(const T& value) {
        hash_t hash = std::hash<T>{}(value);
        size_t index = hash & (m_ - 1);

        hash_t remaining = hash >> b_;
        int rank;
        if (remaining != 0) {
            int leading_zeros = __builtin_clzll(remaining) - static_cast<int>(b_);
            rank = leading_zeros + 1;
        } else {
            // 高位全为 0，前导零为最大有效位数
            rank = (sizeof(hash_t) * 8 - b_) + 1;
        }

        registers[index] = std::max(registers[index], rank);
    }

    auto ComputeCardinality() -> double {
        constexpr auto constant = 0.79402;

        double sum = 0;
        for (auto index = 0; index < m_; index++) {
            sum += std::pow(2.0, -registers[index]);
        }

        return constant * (m_ * (m_ / sum));
    }

    auto Merge(const HyperLogLog& other) {
        if (b_ != other.b_) {
            throw std::invalid_argument("HyperLogLog instances must have the same b value to merge.");
        }

        for (size_t i = 0; i < m_; i++) {
            registers[i] = std::max(registers[i], other.registers[i]);
        }
    }

private:
    size_t b_;
    size_t m_;
    std::vector<int> registers;
};

std::vector<std::string> generate(const int count, const std::string &prefix = "item") {
    std::vector<std::string> res;
    res.reserve(count);
    for (int i = 0; i < count; ++i) {
        res.push_back(prefix + std::to_string(i));
    }
    return res;
}

int main () {
    HyperLogLog<std::string>hll(14);
    auto items = generate(100000000);
    for (const auto& item : items) {
        hll.Add(item);
    }

    std::cout << "Estimated cardinality: " << hll.ComputeCardinality() << std::endl;
}

结果为：

1	Estimated cardinality: 1.11156e+08

哈希函数的质量很重要，用之前 Bloom Filter 的那个 D. E. Knuth 的简单 Hash 比 std::hash 的误差会大不小。但不想花时间在处理哈希上，之前的就没改。

此外，如果考虑时间窗口，比如通过时间段内的访问用户数量（日活、月活），可以维护多个 HyperLogLog 实例来实现时间窗口的滑动，每个实例对应一个时间段。当时间窗口滑动时，旧的实例被丢弃，新的实例被创建。

Cuckoo Filter

Cuckoo Filter 和 Bloom Filter 类似，但是支持删除元素，其空间占用效率应该高于 Bloom Filter。

Cuckoo 是布谷鸟的意思（出生的幼鸟踢开其他鸟蛋），其思想和 Cuckoo Hashing 类似，处理冲突的方式是“踢出”与插入项冲突的项，直到找到一个空位或者达到最大尝试次数。

为了支持删除，就需要存元素的信息。但同样，存完整信息就变成哈希表了，所以是部分信息。

与 Cuckoo Hashing 不同的是，Cuckoo Filter 不是存储元素的完整信息，而是存储元素的指纹，或者叫标签 Tag，都可以，以节省空间。

此外，Cuckoo Filter 的一个 index 对应的是一个较小的 bucket，例如四个 Slot 存储 Tag。

Cuckoo Hashing 利用两个哈希函数和两个子表来存储元素，而 Cuckoo Filter 的每个元素对应的是根据元素的 Hash 值计算的一个 Tag，以及两个 index。Cuckoo Hashing 确认 index 的时候是直接计算 $h_1(x)$ 和 $h_2(x)$ ，而 Cuckoo Filter 没有存储完整的元素，只能根据 Tag 和一个 index，来计算出 alt_index。

注意：index 和 alt_index 的 alt 只是相对与 index 而言的，它们之间是一个异或计算，有自反性。可以从任意一个 index 和 Tag 计算出另一个 index。

其中 $Tag$ 是元素的 Tag， $M$ 是桶的数量（总是二次幂）， $i$ 是 index，那么 $i_{alt}$ 的计算方式是：

i_{alt} = (i \oplus Tag) \ \& \ (M - 1)

Tag 的计算公式通常是取元素的 Hash 值的某些位，例如：

Tag = H(x) \ \& \ (2^b - 1)

注意这里和一般哈希表不同，不通过取模而是位与来取 index，原因是需要自反性，而取模会破坏自反性。
（From Gemini，我最开始实现的时候取模了，然后一直没领会到和 Cuckoo Hashing 不同，要利用异或的 $A \oplus A \oplus B = B$ 的性质来计算 alt_index）

查询时，应该检查 index 和 alt_index 对应的桶中是否有 Tag 匹配。

插入时，首先计算 index 和 alt_index，如果其中一个桶有空位，就直接插入；如果两个桶都满了，则开始循环：随机选择一个桶中的随机一个 Tag 踢出，然后将被踢出的 Tag 试着插入到其对应的另一个桶中，若成功则结束，若失败则继续循环这个过程，直到找到一个空位或者达到最大尝试次数。

删除时，计算 index 和 alt_index，检查两个桶中是否有匹配的 Tag，如果找到则删除其一。

必须是其一，不能都删掉。假设有相同 Tag 和 index 的两个元素 A 和 B，则其应该位于于 index 和 alt_index 不同桶中，如果删除了 A 的 Tag 之后还去找 alt_index 的桶去删除 B 的 Tag，则会误删 B。

反之，如果删除了 A 但是没有删除 B 的 Tag，当然查看 alt_index 时看到了相同 Tag 的 B，A 仍然会被误判为存在，符合预期。

考虑上面 A 和 B 的极端情况，如果没有 bucket，此时有 C 也符合情况，那么插入就会失败，因为只有 index 和 alt_index 两个 Slot，互相踢出直到达到最大尝试次数，仍然无法找到空位。这就是需要 bucket 的原因，通过增加常数时间的开销（遍历较小的 bucket），避免在 Filter 明明还要很多空余空间的情况下，因为布谷鸟的机制被迫无法 Add。

此外，更极限一点，还可以增加一个 Victim，临时记录添加失败的元素的信息。在有删除时，最后检查是否有 Victim，如果有则尝试重新插入 Victim，如果成功则清空 Victim，如果失败则继续保留 Victim。也就是从 $2B$ 变成 $2B + 1$ ，多了一次机会。

记得在添加和查找操作都要额外检查 Victim

Bucket 的大小为 4 是论文中实践出来的最优解，详情见论文 Cuckoo Filter: Practically Better Than Bloom 或者 doi:10.1145/2674005.2674994 的 Optimal Bucket Size 的部分，作者有尝试过 1、2、4、8，最终推荐 4。

Redis 提供有 CF 命令，见 DocsDocs → Develop with Redis → Redis data types → Probabilistic → Cuckoo filter

官方实现见：efficient/cuckoofilter

一份我觉得正确的实现：z0z0r4 - Cuckoo Filter

#include <iostream>
#include <vector>
#include <string>
#include <random>
#include <chrono>

using hash_t = std::size_t;
using TagType = uint16_t;

size_t UpperPower2(size_t x) {
    x--;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    x++;
    return x == 0 ? 1 : x;
}

struct Victim {
    size_t index;
    TagType tag;
    bool used;
};

template<typename KeyType>
class CuckooFilter {
public:
    explicit CuckooFilter(const size_t capacity) : capacity_(capacity), size_(0), table_(0), victim_({0, 0, false}) {
        capacity_ = UpperPower2(capacity_);
        table_.assign(capacity_, std::vector<TagType>());
    }

    [[nodiscard]] auto TagHash(const hash_t &hash) const -> TagType {
        const auto tag = hash & ((1ULL << bits_per_item_) - 1);
        return tag == 0 ? 1 : tag; // avoid zero tag
    }

    auto GenerateIndexAndTag(const KeyType &key) -> std::pair<size_t, TagType> {
        hash_t hash_val = std::hash<KeyType>{}(key);
        auto index = (hash_val >> 32) & (capacity_ - 1);
        auto tag = TagHash(hash_val);
        return std::make_pair(index, tag);
    }

    [[nodiscard]] auto GenerateAltIndex(const TagType &tag, const size_t index) const -> size_t {
        return (index ^ (tag * 0x5bd1e995)) & (capacity_ - 1);
    }

    bool Add(const KeyType &key) {
        if (victim_.used) {
            return false; // 过滤器已满
        }

        if (Contain(key)) {
            return true; // already exists
        }

        auto [curr_index, curr_tag] = GenerateIndexAndTag(key);
        return AddImpl(curr_index, curr_tag);
    }

    bool Contain(const KeyType &key) {
        auto [index, tag] = GenerateIndexAndTag(key);
        if (auto &bucket = table_[index]; std::find(bucket.begin(), bucket.end(), tag) != bucket.end()) {
            return true;
        }

        // alt bucket
        auto alt_index = GenerateAltIndex(tag, index);
        if (auto &alt_bucket = table_[alt_index];
            std::find(alt_bucket.begin(), alt_bucket.end(), tag) != alt_bucket.end()) {
            return true;
        }


        auto victim_index = victim_.index;
        auto victim_alt_index = GenerateAltIndex(victim_.tag, victim_index);
        if (victim_.used && (victim_.index == index || victim_.index == victim_alt_index) && victim_.tag == tag) {
            return true;
        }

        return false;
    }

    auto Delete(const KeyType &key) -> bool {
        auto [index, tag] = GenerateIndexAndTag(key);
        auto alt_index = GenerateAltIndex(tag, index);
        auto &bucket = table_[index];
        auto &alt_bucket = table_[alt_index];
        auto it = std::find(bucket.begin(), bucket.end(), tag);

        if (it != bucket.end()) {
            bucket.erase(it);
            size_--;
            AddVictim();
            return true;
        }

            // alt bucket
            it = std::find(alt_bucket.begin(), alt_bucket.end(), tag);
            if (it != alt_bucket.end()) {
                alt_bucket.erase(it);
                size_--;
                AddVictim();
                return true;
            }


        if (victim_.used && (victim_.index == index || victim_.index == alt_index) && victim_.tag == tag) {
            victim_.used = false;
            return true;
        }

        return false;;
    }

private:
    auto AddVictim() -> bool {
        if (!victim_.used) {
            return true;
        }

        const auto index = victim_.index;
        const auto tag = victim_.tag;

        victim_.used = false; // clear victim before reinsertion
        return AddImpl(index, tag);
    }

    auto AddImpl(const size_t curr_index, TagType curr_tag) -> bool {
        if (auto &bucket = table_[curr_index]; bucket.size() < bucket_size_) {
            bucket.push_back(curr_tag);
            size_++;
            return true;
        }

        // try alt bucket
        auto alt_index = GenerateAltIndex(curr_tag, curr_index);
        if (auto &alt_bucket = table_[alt_index]; alt_bucket.size() < bucket_size_) {
            alt_bucket.push_back(curr_tag);
            size_++;
            return true;
        }

        size_t kick_index = curr_index;

        for (auto i = 0; i < max_kicks_; ++i) {
            // max 10 evictions
            auto &kick_bucket = table_[kick_index];

            const size_t rand_pos = rng_() % kick_bucket.size();
            std::swap(curr_tag, kick_bucket[rand_pos]);

            kick_index = GenerateAltIndex(curr_tag, kick_index);

            if (auto &next_bucket = table_[kick_index]; next_bucket.size() < bucket_size_) {
                next_bucket.push_back(curr_tag);
                size_++;
                return true;
            }
        }

        if (!victim_.used) {
            victim_ = {kick_index, curr_tag, true};
            return true;
        }

        return false;
    }


    size_t capacity_;
    size_t size_;
    size_t max_kicks_ = 500;
    size_t bits_per_item_ = 16;
    size_t bucket_size_ = 4;
    std::vector<std::vector<TagType> > table_;
    Victim victim_;
    std::mt19937 rng_{std::random_device{}()};
};

TODO: Cuckoo Hashing

Bloom Filter

Count-min Sketch

HyperLogLog

Cuckoo Filter

说些什么吧！