最近在学习CMU的15-445 DB课程，在做Project1的Extendible Hash Table的时候，由于是先看了课程，过了一个多星期才做的Lab，对extendible hash table只能说是知道大体的意思，并没有透彻的了解它，尤其是bucket指针和数据重分配这一部分，涉及到比较tricky的位运算，在一知半解的情况下实现它，完全没办法找到对应的bug，ConcurrentInsertFindTest和GetNumBucketsTest总是fail。又去参考了很多对可扩展哈希的文章，才发现自己一些细节是错误的。本篇文章尝试以我的理解说清楚extendible hash table，并作为我的菜坑记录。

这一部分的任务就是搭建一个通用的存储unique KV对的哈希表。我们需要实现哈希表的插入、删除以及查找操作。实验手册中并没有要求我们实现shrink部分，所以只需要关注如何扩展哈希表即可。代码在scr/include/container/hash/extendible_hash_table.h以及 src/container/hash/extendible_hash_table.cpp下，实现之前建议先阅读这两个文件的代码和注释，明确我们的目标。

在理解可扩展哈希表之前，我们需要了解几个概念。

下面是一个简单的可扩展哈希表的示意图，具体不用关心它是怎么来的，先对它建立一个直观的印象即可。

上图又出现两个概念：

两者之间有什么关系呢？

Global depth和local depth的概念就是这些，然而在实现算法的过程中还有对这些概念的应用，我们暂且先忽略，之后的部分会一一阐述。

对于Bucket的Insert，Remove以及Find操作，熟悉一下C++的list容器相关操作就可以实现。不过有一个地方需要注意的是，实现bucket的Insert方法时，注释里说的是先检查key是否存在，如果存在就要更新value。这里如果先判断bucket是否满了，就会出现bug。因为如果一个bucket满了，但刚你要插入的key在这个bucket的中，先判断是否满的话就会直接返回，不会更新对应key的value，就会造成之后find的错误。

实现了Bucket的三个操作之后，就可以实现ExtendibleHashTable的三大操作了。为了确保线程安全，每一个操作应当加锁来保证。

这里阐述一下Insert的算法流程，然后结合一个具体的例子，分析算法可能遇到的情况。

这个例子来自于官方的Homework #2 - Question 3。假定每一个bucket的容量大小为2，且哈希函数用最低的g个二进制位，g指global depth。

按顺序插入15，14，23，11，9。这几个数对应的二进制分别是，1111，1110，10111，1011，1001。

STEP 1：首先插入15和14，第一步没什么问题。

STEP 2：接着插入23，23的二进制是10111，当前的global depth是0，计算得到的IndexOf(key)是0，说明23要插入到directory的第0个entry中，但是这个entry所指向的bucket满了。我们执行步骤3（重复一下步骤3：如果当前global depth等于local depth，说明bucket已满，需要增长direcotry的大小。增加directory的global depth，并将新增加的entry链接到对应的bucket。否则，继续执行步骤4）。

这一步有一个很重要的点，新增长的entry怎么分配到对应的bucket？如果和上图的情况一样，从1增长到2，只需要把多出来的一个拉到唯一的bucket上就可以了，但如果从2到4，从4到8呢？多出来的若干个如何处理？其实只需要将多出来的一部分指针完全复制之前的一份就可以了。这样做法我觉得是可扩展哈希的比较重要的细节，由于可扩展哈希扩展direcotry时是按照当前大小的两倍进行扩展，新增长出来的部分作为之前directory的对等实体，每一个新的entry都对应了之前对应的entry，指向相同的bucket。唯一的不同就是之前的direcotry的索引最高位是0，扩展出来的最高位是1。

STEP 3：执行步骤4（记录当前的local mask，创建bucket1和bucket2，增加两个bucket的local depth，增加num bucket的数量。取出之前满了的bucket中的元素，按照local mask的标准将每个元素重新分配到bucket1和bucket2中。执行步骤5）。

当前local mask的计算方法是1 Insert(14, "b"); table->Insert(23, "c"); table->Insert(11, "d"); table->Insert(9, "e"); EXPECT_EQ(4, table->GetNumBuckets()); EXPECT_EQ(1, table->GetLocalDepth(0)); EXPECT_EQ(2, table->GetLocalDepth(1)); EXPECT_EQ(3, table->GetLocalDepth(3)); EXPECT_EQ(3, table->GetLocalDepth(7)); } TEST(ExtendibleHashTableTest, ConcurrentInsertFindTest) { const int num_runs = 50; const int num_threads = 3; // Run concurrent test multiple times to guarantee correctness. for (int run = 0; run < num_runs; run++) { auto table = std::make_unique(2); std::vector threads; threads.reserve(num_threads); for (int tid = 0; tid < num_threads; tid++) { threads.emplace_back([tid, &table]() { int val; table->Insert(tid, tid); EXPECT_TRUE(table->Find(tid, val)); }); } for (int i = 0; i < num_threads; i++) { threads[i].join(); } EXPECT_EQ(table->GetGlobalDepth(), 1); for (int i = 0; i < num_threads; i++) { int val; EXPECT_TRUE(table->Find(i, val)); EXPECT_EQ(i, val); } } } TEST(ExtendibleHashTableTest, ConcurrentInsertFind2Test) { const int num_runs = 30; const int num_threads = 5; // Run concurrent test multiple times to guarantee correctness. for (int run = 0; run < num_runs; run++) { auto table = std::make_unique(2); std::vector threadsInsert; std::vector threadsFind; threadsInsert.reserve(num_threads); threadsFind.reserve(num_threads); for (int tid = 0; tid < num_threads; tid++) { threadsInsert.emplace_back([tid, &table]() { for (int i = tid * 10; i < (tid + 1) * 10; i++) { table->Insert(i, i); } }); } for (int i = 0; i < num_threads; i++) { threadsInsert[i].join(); } for (int tid = 0; tid < num_threads; tid++) { threadsFind.emplace_back([tid, &table]() { for (int i = tid * 10; i < (tid + 1) * 10; i++) { int val; EXPECT_TRUE(table->Find(i, val)); } }); } for (int i = 0; i < num_threads; i++) { threadsFind[i].join(); } } } TEST(ExtendibleHashTableTest, GetNumBucketsTest) { auto table = std::make_unique(2); table->Insert(4, "a"); table->Insert(12, "b"); table->Insert(16, "c"); EXPECT_EQ(4, table->GetNumBuckets()); table->Insert(64, "d"); table->Insert(31, "e"); table->Insert(10, "f"); table->Insert(51, "g"); EXPECT_EQ(4, table->GetNumBuckets()); table->Insert(15, "h"); table->Insert(18, "i"); table->Insert(20, "j"); EXPECT_EQ(7, table->GetNumBuckets()); table->Insert(7, "k"); table->Insert(23, "l"); EXPECT_EQ(8, table->GetNumBuckets()); }