CMU 15-445 | Project #2 - Extendible Hash Index

• 官网链接：https://15445.courses.cs.cmu.edu/fall2023/project2/
• 耗时：3 天
• Leaderboard：18 (2024-10-17)

今天来补补 Project2 的思路和过程。Project2 的重头戏是可扩展哈希表，理解了可扩展哈希的原理的细节才好上手进行实现，要是直接对着接口看，绝对一头雾水，连实验提供的几个类之间的关系都理不清。

Extendible Hash Table

哈希表其实非常常见，它可以实现 $O(1)$ 复杂度的键值对存储和索引。哈希表的常见实现方式有线性表、B+ 树等。这次实验则要求我们实现一个可扩展的哈希表。下图是一个简单的示例：

主要参考了这篇文章

这张图里已经填充了一些数据，可以看出有两个不同的 directory，在第二个 directory 中连接了三个 bucket，这几个 bucket 似乎是根据末尾的 01 排列进行区分的。下面通过一个例子来加深对 Extendible Hash Table 的理解。

Extendible Hash Table 的主要思想就是对 hash 末尾的 01 进行分桶。

通过 global_depth / local_depth 对 01 的长度进行限定，bucket 只负责存储原始键值对，完全不考虑前面的 directory 是怎么分组的。

Leaderboard

这部分实验的优化暂时没有做，只是将 Project1 的优化直接 merge 进来了，结果 Rank 提升得相当离谱

• 2024-09-26 #Rank 16 - Merge branch ‘optim-p1’ into optim-p2