哈希表（第 2 部分）
8.6 固定大小的链地址法哈希表
我们将实现过程分为两个阶段：
- 1. 使用侵入式链表的固定大小哈希表。
- 2. 带有渐进式重新哈希的可调整大小哈希表。
源代码在文章末尾
步骤0：选择哈希函数
有几类哈希函数，它们具有不同的属性，适用于不同的用途：
- 1. 加密哈希函数，例如MD5、SHA1。
- 2. 校验和哈希函数，例如CRC32、Adler32。
- 3. 用于哈希表的哈希函数，例如FNV、Murmur。这就是我们要使用的！
它们都被称为哈希函数，但它们的用途并不重叠。不要将加密哈希函数用于哈希表，因为它们速度慢且大材小用。也不要将哈希表的哈希函数用于其他用途，因为它们不够强大。
步骤1：定义侵入式链表节点
struct HNode {
HNode *next = NULL;
uint64_t hcode = 0; // 哈希值
};这只是一个带有键的哈希值的侵入式链表节点。侵入式哈希表并不关心数据本身，但在插入时它仍然需要哈希值。
步骤2：定义固定大小的哈希表
struct HTab {
HNode **tab = NULL; // 槽位数组
size_t mask = 0; // 2的幂次方大小的数组，2^n - 1
size_t size = 0; // 键的数量
};hash(key) % N 将哈希值映射到一个槽位。取模或除法是CPU的慢速操作，所以通常使用2的幂次方大小的数组。对2的幂次方取模实际上就是取低位，所以可以通过快速的按位与操作来实现：hash(key) & (N-1)。
static void h_init(HTab *htab, size_t n) {
assert(n > 0 && ((n - 1) & n) == 0); // n必须是2的幂次方
htab->tab = (HNode **)calloc(n, sizeof(HNode *));
htab->mask = n - 1;
htab->size = 0;
}步骤3：链表插入
static void h_insert(HTab *htab, HNode *node) {
size_t pos = node->hcode & htab->mask; // node->hcode & (n - 1)
HNode *next = htab->tab[pos];
node->next = next;
htab->tab[pos] = node;
htab->size++;
}新节点总是插入到链表的头部，所以最坏情况下插入操作的时间复杂度为O(1)。侵入式意味着在数据结构代码中不需要进行内存分配，这与std::list不同。
链表是像Linux内核这样的大型C项目中最常见的集合，并且几乎所有实际使用的链表都是侵入式的，像std::list这样的非侵入式链表很少有用。
步骤6：哈希表查找
通用的搜索函数需要一个回调函数来进行相等性比较，因为它对数据一无所知。注意，在调用回调函数之前它会先比较哈希值，这是一种优化，可以尽早排除不符合条件的候选节点。
static HNode **h_lookup(HTab *htab, HNode *key, bool (*eq)(HNode *, HNode *)) {
if (!htab->tab) {
return NULL;
}
size_t pos = key->hcode & htab->mask;
HNode **from = &htab->tab[pos]; // 指向目标节点的指针的地址
for (HNode *cur; (cur = *from) != NULL; from = &cur->next) {
if (cur->hcode == key->hcode && eq(cur, key)) {
return from; // 问题：为什么不返回 `cur` 呢？这是为了删除操作
}
}
return NULL;
}这个函数应该返回找到的节点，但实际上它返回的是该节点的父指针的地址，需要解引用这个指针才能得到目标节点的指针。为什么呢？因为我们需要这个指针的地址来删除节点。
步骤7：哈希表删除
要删除一个链表节点，我们需要更新其父节点中的指针。这就是为什么h_lookup()函数返回父指针的地址。不需要单独的搜索和删除函数！
static HNode *h_detach(HTab *htab, HNode **from) {
HNode *node = *from; // 目标节点
*from = node->next; // 更新指向目标节点的指针
htab->size--;
return node;
}但是如果我们要删除的是第一个没有父节点的节点呢？这似乎是一个特殊情况。
- 1. 如果节点是第一个节点，更新数组槽位。
- 2. 否则，更新其父节点。
实际上上述情况是不必要的，因为h_lookup()返回的是要更新的指针的地址，无论这个指针是来自数组槽位还是链表节点都没有关系。
HNode **from = &htab->tab[pos]; // 指向目标节点的指针的地址
for (HNode *cur; (cur = *from) != NULL; from = &cur->next) {
if (cur->hcode == key->hcode && eq(cur, key)) {
return from; // 可能是一个节点，也可能是一个槽位
}
}当你深入思考时，特殊情况可能根本就不特殊。
- 1. 删除链表的第一个节点并不是特殊情况。
- 2. 不需要搜索和删除函数。
8.7 可调整大小的哈希表
步骤8：定义哈希表接口
可调整大小的HMap是基于固定大小的HTab实现的。为了实现渐进式重新哈希，它包含两个HTab。
struct HMap {
HTab newer;
HTab older;
size_t migrate_pos = 0;
};获取（get）、设置（set）、删除（del）接口：
HNode *hm_lookup(HMap *hmap, HNode *key, bool (*eq)(HNode *, HNode *));
void hm_insert(HMap *hmap, HNode *node);
HNode *hm_delete(HMap *hmap, HNode *key, bool (*eq)(HNode *, HNode *));步骤9：在重新哈希期间处理两个哈希表
通常情况下，使用HMap::newer哈希表，而HMap::older哈希表不使用。当负载因子过高时，将HMap::newer移动到HMap::older，并将HMap::newer替换为一个更大的空表。由于我们使用的是2的幂次方大小的数组，所以新表的大小简单地翻倍。
static void hm_trigger_rehashing(HMap *hmap) {
hmap->older = hmap->newer; // (newer, older) <- (new_table, newer)
h_init(&hmap->newer, (hmap->newer.mask + 1) * 2);
hmap->migrate_pos = 0;
}在重新哈希期间，查找或删除操作可能需要查询两个哈希表。
HNode *hm_lookup(HMap *hmap, HNode *key, bool (*eq)(HNode *, HNode *)) {
HNode **from = h_lookup(&hmap->newer, key, eq);
if (!from) {
from = h_lookup(&hmap->older, key, eq);
}
return from ? *from : NULL;
}
HNode *hm_delete(HMap *hmap, HNode *key, bool (*eq)(HNode *, HNode *)) {
if (HNode **from = h_lookup(&hmap->newer, key, eq)) {
return h_detach(&hmap->newer, from);
}
if (HNode **from = h_lookup(&hmap->older, key, eq)) {
return h_detach(&hmap->older, from);
}
return NULL;
}步骤10：根据负载因子触发重新哈希
插入操作总是更新新的哈希表。当负载因子过高时，它会触发重新哈希。
void hm_insert(HMap *hmap, HNode *node) {
if (!hmap->newer.tab) {
h_init(&hmap->newer, 4); // 如果为空则初始化
}
h_insert(&hmap->newer, node); // 总是插入到新的哈希表中
if (!hmap->older.tab) { // 检查是否需要重新哈希
size_t shreshold = (hmap->newer.mask + 1) * k_max_load_factor;
if (hmap->newer.size >= shreshold) {
hm_trigger_rehashing(hmap);
}
}
hm_help_rehashing(hmap); // 迁移一些键
}对于链地址法哈希表，负载因子限制应该大于1，因为每个槽位本来就是为了容纳多个元素而设计的。
const size_t k_max_load_factor = 8;hm_help_rehashing()函数会将一些键移动到新的哈希表中。我们也可以在查找和删除操作中触发这个函数，因为它只做O(1)的工作，不会有什么影响。
HNode *hm_lookup(HMap *hmap, HNode *key, bool (*eq)(HNode *, HNode *)) {
hm_help_rehashing(hmap);
// ...
}
HNode *hm_delete(HMap *hmap, HNode *key, bool (*eq)(HNode *, HNode *)) {
hm_help_rehashing(hmap);
// ...
}步骤11：渐进式重新哈希
hm_help_rehashing()函数会扫描每个槽位，移动固定数量的元素，然后退出。它会在HMap::migrate_pos中记住上一个槽位的索引。
const size_t k_rehashing_work = 128; // 固定的工作量
static void hm_help_rehashing(HMap *hmap) {
size_t nwork = 0;
while (nwork < k_rehashing_work && hmap->older.size > 0) {
// 找到一个非空的槽位
HNode **from = &hmap->older.tab[hmap->migrate_pos];
if (!*from) {
hmap->migrate_pos++;
continue; // 空槽位
}
// 将链表的第一个元素移动到新的哈希表中
h_insert(&hmap->newer, h_detach(&hmap->older, from));
nwork++;
}
// 如果完成了，就释放旧的哈希表
if (hmap->older.size == 0 && hmap->older.tab) {
free(hmap->older.tab);
hmap->older = HTab{};
}
}8.8 Redis命令：get、set、del
步骤1：定义数据类型
static struct {
HMap db; // 顶级哈希表
} g_data;
// 顶级哈希表的键值对
struct Entry {
struct HNode node; // 哈希表节点
std::string key;
std::string val;
};struct Entry是一个带有嵌入哈希表节点的键值对。相等性回调函数展示了如何使用container_of宏。
static bool entry_eq(HNode *lhs, HNode *rhs) {
struct Entry *le = container_of(lhs, struct Entry, node);
struct Entry *re = container_of(rhs, struct Entry, node);
return le->key == re->key;
}步骤2：实现get、set、del
在查找过程中进行比较时，我们使用了一个只包含键的虚拟Entry。
static void do_get(std::vector<std::string> &cmd, Response &out) {
// 一个仅用于查找的虚拟 `Entry`
Entry key;
key.key.swap(cmd[1]);
key.node.hcode = str_hash((uint8_t *)key.key.data(), key.key.size());
// 哈希表查找
HNode *node = hm_lookup(&g_data.db, &key.node, &entry_eq);
if (!node) {
out.status = RES_NX;
return;
}
// 复制值
const std::string &val = container_of(node, Entry, node)->val;
assert(val.size() <= k_max_msg);
out.data.assign(val.begin(), val.end());
}注意，键不一定必须是Entry类型，键可以是其他嵌入了HNode的类型，只要你相应地更新entry_eq()函数即可。目前Entry只是一个键值对，随着我们的深入，它会变得更复杂。我们可以为查找操作定义一个更精简的结构体。
struct LookupKey { // 仅用于查找
HNode node;
std::string key;
};
LookupKey key = {...};
HNode *node = hm_lookup(&g_data.db, &key.node, &key_eq);8.8 我们学到了什么
- 1. 可扩展的哈希表实现。
- 2. 通过链表代码中的指针间接引用来避免特殊情况。
源代码：
