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
本文由作者按照 CC BY 4.0 进行授权