CMU 15-445 Project 0：HyperLogLog 从懵逼到通关

最近在做 CMU 15-445 Fall 2024 的 Project 0，被 HyperLogLog 这个数据结构搞得头大。网上讲原理的文章一堆，但真正动手实现的时候还是踩了不少坑。这篇文章记录一下我的理解和踩坑过程。

这玩意是干嘛的？

HyperLogLog（简称 HLL）说白了就是用来数"有多少个不重复的东西"的。

举个例子：你要统计网站的日活用户数（UV）。最直接的方法是用一个 HashSet 把所有用户 ID 存下来，最后看 size。但问题是，如果你有 10 亿用户，每个 ID 占 8 字节，光存这些 ID 就要 8GB 内存。

HLL 的骚操作是：只存一些统计信息，就能估算出大概有多少人，误差还挺小（标准误差约 2%），而且只需要 12KB 内存。

核心思想：抛硬币的概率游戏

HLL 的原理其实很简单，用抛硬币来类比：

假设你抛硬币，记录连续出现正面的最大次数。如果你告诉我"我最多连续抛出了 5 次正面"，我大概能猜到你抛了 32 次左右（因为连续 5 次正面的概率是 1/32）。

HLL 把这个思想用到了 hash 值上：

  1. 把每个元素 hash 成一个 64 位的二进制数
  2. 数这个二进制数从左边开始有多少个 0（或者说第一个 1 出现在第几位）
  3. 记录这个"最大前导零数量"
  4. 用这个数字反推大概有多少个不同的元素

为什么这样能估算数量？因为 hash 值是均匀分布的：

  • 第 1 位是 0 的概率：1/2
  • 前 2 位都是 0 的概率：1/4
  • 前 k 位都是 0 的概率：1/2^k

所以如果你观察到最大前导零数量是 k，说明大概有 2^k 个不同的元素。

但是！单个估计太不准了

只用一个计数器误差太大。HLL 的解决方案是：分桶 + 调和平均。

把 hash 值的前 b 位作为桶的编号，剩下的位用来计算前导零。这样就有 2^b 个桶，每个桶独立统计，最后用调和平均把结果合并。

为什么用调和平均而不是算术平均？因为调和平均对异常大的值不敏感。如果某个桶碰巧遇到了一个前导零特别多的 hash 值，用算术平均会被带偏，但调和平均能压住这种异常值。

Task 1：基础版 HyperLogLog

数据结构

class HyperLogLog {
  int16_t n_bits_;           // 用多少位来确定桶编号
  std::vector<uint64_t> buckets_;  // 每个桶存储最大的"第一个1的位置"
  size_t cardinality_;       // 最终估算的基数
};

AddElem：添加元素

auto HyperLogLog<KeyType>::AddElem(KeyType val) -> void {
  if (n_bits_ < 0) {
    return;
  }

  // 1. 计算 hash 值
  hash_t hash = CalculateHash(val);
  std::bitset<64> binary(hash);

  // 2. 取前 n_bits_ 位作为桶索引
  //    比如 n_bits_=3，hash=0b101xxxxx...，桶索引就是 5
  uint64_t bucket_index = (binary >> (64 - n_bits_)).to_ulong();

  // 3. 剩余位左移，然后找第一个 1 的位置
  std::bitset<64> remaining = binary << n_bits_;
  uint64_t position = PositionOfLeftmostOne(remaining);

  // 4. 更新桶的最大值
  buckets_[bucket_index] = std::max(position, buckets_[bucket_index]);
}

这里有个细节：PositionOfLeftmostOne 返回的是"第一个 1 在第几位"，从 1 开始计数。如果全是 0，返回 64。

auto HyperLogLog<KeyType>::PositionOfLeftmostOne(const std::bitset<64> &bset) const -> uint64_t {
  for (int i = 63; i >= 0; i--) {
    if (bset.test(i)) {
      return 64 - i;  // 从左边数第几位
    }
  }
  return 64;  // 全是 0
}

ComputeCardinality：计算基数

auto HyperLogLog<KeyType>::ComputeCardinality() -> void {
  if (buckets_.empty()) {
    cardinality_ = 0;
    return;
  }

  // 调和平均：sum = Σ(2^(-bucket[i]))
  double sum = 0.0;
  for (uint64_t bucket : buckets_) {
    sum += std::pow(2.0, -static_cast<double>(bucket));
  }

  // 估算公式：E = α * m^2 / sum
  auto m = static_cast<double>(buckets_.size());
  double estimate = 0.79402 * m * m / sum;

  cardinality_ = static_cast<size_t>(std::floor(estimate));
}

0.79402 是一个修正常数，用来消除系统性偏差。

Task 2：Presto 优化版

基础版有个问题：每个桶用 64 位来存储，但实际上前导零最多也就 64 个，用 7 位就够了。Presto 的优化思路是：

  • Dense Bucket（4 位）：存储前导零数量的低 4 位
  • Overflow Bucket（3 位）：只有当前导零 > 15 时才用，存储高 3 位

这样大部分情况下只需要 4 位，只有少数"异常值"才需要额外的 3 位。

关键区别：从右往左数零！

这是我踩的最大的坑。Presto 版本数的是 trailing zeros（从右往左数零），不是 leading zeros（从左往右）。

为什么？我猜是因为从右往左数更容易用位运算实现，而且不需要先把桶索引位移走。

auto HyperLogLogPresto<KeyType>::AddElem(KeyType val) -> void {
  if (n_leading_bits_ < 0 || dense_bucket_.empty()) {
    return;
  }

  hash_t hash = CalculateHash(val);
  std::bitset<64> binary(hash);

  // 桶索引还是取最高的 n_leading_bits_ 位
  uint64_t bucket_index = 0;
  if (n_leading_bits_ > 0) {
    bucket_index = (binary >> (64 - n_leading_bits_)).to_ullong();
  }

  // 关键：直接在原始 hash 上数 trailing zeros，不需要移位！
  uint64_t trailing_zeros = 0;
  if (binary.none()) {
    trailing_zeros = 64;
  } else {
    while (!binary.test(0)) {  // test(0) 检查最低位
      binary >>= 1;
      trailing_zeros++;
    }
  }

  // 读取旧值（dense + overflow 拼起来）
  uint64_t old_low = dense_bucket_[bucket_index].to_ullong();
  uint64_t old_high = 0;
  if (overflow_bucket_.count(bucket_index) > 0) {
    old_high = overflow_bucket_[bucket_index].to_ullong();
  }
  uint64_t old_val = (old_high << 4) | old_low;

  // 更新（如果新值更大）
  if (trailing_zeros > old_val) {
    dense_bucket_[bucket_index] = std::bitset<4>(trailing_zeros & 0xF);  // 低 4 位
    uint64_t new_high = trailing_zeros >> 4;  // 高位
    if (new_high > 0) {
      overflow_bucket_[bucket_index] = std::bitset<3>(new_high);
    }
  }
}

另一个坑：CalculateHash 的行为不一样

看头文件里的 CalculateHash：

// HyperLogLog 版本：所有类型都做 hash
inline auto CalculateHash(KeyType val) -> hash_t {
  Value val_obj;
  if constexpr (std::is_same<KeyType, std::string>::value) {
    val_obj = Value(VARCHAR, val);
  } else {
    val_obj = Value(BIGINT, val);
  }
  return bustub::HashUtil::HashValue(&val_obj);
}

// Presto 版本：int64_t 直接返回原值！
inline auto CalculateHash(KeyType val) -> hash_t {
  if constexpr (std::is_same<KeyType, std::string>::value) {
    // string 做 hash
    return bustub::HashUtil::HashValue(&val_obj);
  }
  if constexpr (std::is_same<KeyType, int64_t>::value) {
    return static_cast<hash_t>(val);  // ⭐ 直接返回！
  }
}

这意味着测试用例里的 AddElem(262144) 实际上就是在处理 262144 这个数本身，不是它的 hash 值。262144 = 2^18，二进制末尾有 18 个 0，所以 trailing_zeros = 18。

踩坑记录

坑 1：n_bits = 0 的边界情况

一开始我写的是 if (n_bits_ <= 0) return;，结果 EdgeTest2 挂了。

n_bits = 0 是合法的！它表示只有 1 个桶（2^0 = 1），所有 64 位都用来计算前导零。

坑 2：负数左移是未定义行为

size_t m = static_cast<size_t>(1) << n_bits;  // 如果 n_bits = -2，boom!

当 n_bits 是负数时，1 << -2 是未定义行为，会产生一个巨大的数字，导致 vector 创建失败。所以必须在创建 vector 之前检查负数。

坑 3：Presto 不需要 +1

基础版 HLL 存的是"第一个 1 的位置"（从 1 开始），但 Presto 存的是"trailing zeros 的数量"（从 0 开始）。

我一开始写了 trailing_zeros + 1，结果所有 Presto 测试都挂了。

坑 4：clang-tidy 的代码风格要求

Gradescope 的 clang-tidy 检查比本地严格，有几个必须改的：

// ❌ 不行
return std::bitset<64>(hash);
// ✅ 要用花括号初始化
return {hash};

// ❌ 不行
if (bset[i] == 1)
// ✅ 用 test() 或直接判断
if (bset.test(i))

// ❌ 不行
for (size_t i = 0; i < buckets_.size(); i++)
// ✅ 用 range-based for
for (uint64_t bucket : buckets_)

// ❌ 不行
double m = static_cast<double>(buckets_.size());
// ✅ 用 auto
auto m = static_cast<double>(buckets_.size());

C++ 知识点（给非 C++ 背景的同学）

很多同学可能是 Java/Python/Go 背景，想通过 CMU 15-445 学数据库但被 C++ 劝退。这部分我用 Java 类比的方式讲一下这个项目用到的 C++ 特性。

1. 头文件和源文件分离

C++ 把代码分成 .h（头文件）和 .cpp（源文件）两部分：

Java 的做法：
public class HyperLogLog {
    private int n_bits;
    public void addElem(int val) { ... }  // 声明和实现在一起
}

C++ 的做法：
// hyperloglog.h - 只放声明
class HyperLogLog {
    int n_bits_;
    void AddElem(int val);  // 只有声明，没有实现
};

// hyperloglog.cpp - 放实现
void HyperLogLog::AddElem(int val) {
    // 具体实现
}

为什么要分开？C++ 是编译型语言，编译器需要先知道"有哪些类和函数"，然后才能编译使用它们的代码。头文件就是告诉编译器"我有这些东西"，源文件才是真正的实现。

2. 模板（Template）≈ Java 泛型

// C++ 模板
template <typename KeyType>
class HyperLogLog {
    void AddElem(KeyType val);
};

// 使用时
HyperLogLog<int64_t> hll1;
HyperLogLog<std::string> hll2;

// Java 泛型
public class HyperLogLog<KeyType> {
    public void addElem(KeyType val);
}

// 使用时
HyperLogLog<Long> hll1;
HyperLogLog<String> hll2;

几乎一样对吧？但有个重要区别：C++ 模板的实现必须放在头文件里（或者用显式实例化）。这是因为 C++ 模板是编译期展开的，编译器需要看到完整实现才能生成代码。

项目里用了显式实例化的方式，在 .cpp 文件末尾写：

template class HyperLogLog<int64_t>;
template class HyperLogLog<std::string>;

这告诉编译器"只需要生成这两种类型的版本"。

3. std::vector ≈ Java ArrayList

// C++
std::vector<uint64_t> buckets_;
buckets_ = std::vector<uint64_t>(m, 0);  // 创建 m 个元素，初始值都是 0
buckets_[i] = 42;  // 访问第 i 个元素
buckets_.size();   // 获取大小
buckets_.empty();  // 是否为空

// Java
ArrayList<Long> buckets;
buckets = new ArrayList<>(Collections.nCopies(m, 0L));
buckets.set(i, 42L);
buckets.size();
buckets.isEmpty();

C++ 的 vector 可以直接用 [] 访问元素，比 Java 的 get()/set() 简洁。

4. std::unordered_map ≈ Java HashMap

// C++
std::unordered_map<uint16_t, std::bitset<3>> overflow_bucket_;

// 检查 key 是否存在
if (overflow_bucket_.count(bucket_index) > 0) {
    // key 存在
}

// 访问/插入
overflow_bucket_[bucket_index] = some_value;

// Java
HashMap<Integer, BitSet> overflowBucket;

// 检查 key 是否存在
if (overflowBucket.containsKey(bucketIndex)) {
    // key 存在
}

// 访问/插入
overflowBucket.put(bucketIndex, someValue);

C++ 的 [] 操作符很方便，但要注意：如果 key 不存在，[] 会自动创建一个默认值的条目。所以读取前最好先用 count() 检查。

5. std::bitset：固定大小的位数组

这个 Java 里没有直接对应的，Java 的 BitSet 是动态大小的。

std::bitset<64> binary(hash);  // 用 hash 值初始化一个 64 位的 bitset

binary.test(i);     // 检查第 i 位是否为 1（从右往左数，0 是最低位）
binary[i];          // 同上，但返回的是引用
binary.none();      // 是否全是 0
binary.to_ullong(); // 转成 unsigned long long（64位整数）

binary >> 3;        // 右移 3 位
binary << 3;        // 左移 3 位
binary >>= 1;       // 右移 1 位并赋值给自己

注意 test(0) 检查的是最低位（最右边），不是最高位。

6. auto 关键字 ≈ Java var

// C++
auto m = static_cast<double>(buckets_.size());  // 编译器自动推断 m 是 double 类型
auto hash = CalculateHash(val);  // 自动推断 hash 的类型

// 遍历容器
for (auto& item : buckets_) { ... }

// Java 10+
var m = (double) buckets.size();
var hash = calculateHash(val);

for (var item : buckets) { ... }

7. static_cast ≈ Java 强制类型转换

// C++
auto m = static_cast<double>(buckets_.size());  // size_t -> double
auto index = static_cast<size_t>(1) << n_bits;  // 确保是 size_t 类型再左移

// Java
double m = (double) buckets.size();
long index = 1L << nBits;  // 用 1L 确保是 long 类型

C++ 有好几种 cast：static_cast（编译期检查）、dynamic_cast（运行时检查）、reinterpret_cast（危险的位级转换）。一般用 static_cast 就够了。

8. const 和 constexpr

// const：运行时常量，类似 Java 的 final
const int x = 42;

// constexpr：编译期常量，必须在编译时就能确定值
static constexpr double CONSTANT = 0.79402;
static constexpr int BITSET_CAPACITY = 64;

constexpr 比 const 更严格，它要求值在编译时就能算出来。用 constexpr 定义的常量可以用在模板参数里（比如 std::bitset<BITSET_CAPACITY>）。

9. 成员变量命名：下划线后缀

你可能注意到了 C++ 代码里成员变量都有下划线后缀：

class HyperLogLog {
    int16_t n_bits_;      // 成员变量
    std::vector<uint64_t> buckets_;
};

这是 Google C++ 风格指南的约定，用来区分成员变量和局部变量。BusTub 项目遵循这个风格。

10. 返回类型后置语法

// 传统写法
std::bitset<64> ComputeBinary(const hash_t &hash) const;

// 后置返回类型（C++11）
auto ComputeBinary(const hash_t &hash) const -> std::bitset<64>;

两种写法等价，后置语法在返回类型很长或者依赖参数类型时更清晰。BusTub 项目统一用后置语法。

11. const 成员函数

auto ComputeBinary(const hash_t &hash) const -> std::bitset<64>;
//                                     ^^^^^ 这个 const

函数后面的 const 表示"这个函数不会修改对象的状态"。类似 Java 里一个方法只读取成员变量但不修改它们。

编译器会检查：如果你在 const 函数里试图修改成员变量，会报错。

12. 引用传参：const T& vs T

// 值传递：会复制一份
void foo(std::string s);

// 引用传递：不复制，直接用原来的
void bar(std::string& s);

// const 引用：不复制，且不能修改
void baz(const std::string& s);

// Java 对象本来就是引用传递
void foo(String s);  // s 是引用，不是复制

C++ 默认是值传递（会复制），对于大对象（比如 string、vector）要用 const T& 避免不必要的复制。

13. range-based for 循环

// C++ 11+
for (uint64_t bucket : buckets_) {
    sum += std::pow(2.0, -static_cast<double>(bucket));
}

// 如果要修改元素，用引用
for (auto& bucket : buckets_) {
    bucket = 0;
}

// Java
for (long bucket : buckets) {
    sum += Math.pow(2.0, -(double) bucket);
}

14. 初始化列表

// 构造函数用初始化列表
HyperLogLog<KeyType>::HyperLogLog(int16_t n_bits) 
    : cardinality_(0), n_bits_(n_bits) {  // 初始化列表
    // 构造函数体
}

// Java 在构造函数体里赋值
public HyperLogLog(int nBits) {
    this.cardinality = 0;
    this.nBits = nBits;
}

C++ 推荐用初始化列表而不是在构造函数体里赋值，效率更高（直接初始化 vs 先默认初始化再赋值）。

15. if constexpr：编译期条件判断

template <typename KeyType>
auto CalculateHash(KeyType val) -> hash_t {
    if constexpr (std::is_same<KeyType, std::string>::value) {
        // 只有 KeyType 是 string 时才编译这段代码
        return HashString(val);
    } else {
        // 否则编译这段
        return HashInt(val);
    }
}

if constexpr 是 C++17 的特性，在编译期根据类型选择代码分支。普通的 if 两个分支都会编译，可能导致类型错误。

提交注意事项

  1. 本地测试全过不代表 Gradescope 能过，clang-tidy 检查很严格
  2. 用 make format 格式化代码
  3. 用 make check-clang-tidy-p0 检查代码风格
  4. 打包时要保留目录结构： 
    zip project0-submission.zip \
    src/include/primer/hyperloglog.h \
    src/include/primer/hyperloglog_presto.h \
    src/primer/hyperloglog.cpp \
    src/primer/hyperloglog_presto.cpp

搞了两天终于全过了，感觉对 HLL 的理解比之前深多了。下一个 Project 是 Buffer Pool Manager，看起来更刺激。

# c++ # 数据库开发 # 数据库
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

9 个开题演讲稿 AI 工具，本科生格式优化推荐

avatar 2048 AI社区

CSDN 创作者干货：AI 技术文写作框架，从原理到案例快速出稿

把文章核心内容提炼成 “可复用的方法”，比如：“总结一下，做嵌入式 AI 推理加速的核心思路：先明确硬件边界（算力 / 存储 / 功耗），再用量化做基础加速，最后用轻量化剪枝优化 —— 不用追求极致速度，先保证精度达标，再逐步榨干硬件算力，这一套思路适用于所有嵌入式 AI 部署场景。

avatar 2048 AI社区
cover

9 个专科生论文降重工具，AI 写作推荐

avatar 2048 AI社区