哈希表
让我们替换掉上一章中用作占位符的映射。前置知识：基本数据结构、大O表示法。
8.1 哈希表快速回顾
键值对的数据结构
用于键值对存储的数据结构有两类：
- 1. 排序数据结构，例如AVL树、Treap树、前缀树（Trie）、B树。
- 2. 两种类型的哈希表：开放寻址法和链地址法。
源代码在文章末尾
排序数据结构维护元素的顺序，并通过比较来缩小搜索范围，它们的时间复杂度为O(log (N))。而哈希表依赖均匀分布的哈希值来实现O(1)的时间复杂度。
如何在它们之间进行选择呢？首要考虑的是键是否需要排序。对于Redis中的顶级键，没有这样的要求，所以我们选择速度更快的那种。
从数组到哈希表
假设你需要一个映射，其中键是唯一的整数，用数组就可以轻松满足这个需求。我们在文件描述符到连接的映射中就已经这样做了：
std::vector<Conn *> fd2conn; // 类似于 map<int, Conn *>现在考虑键不唯一的用例，这种映射是一对多的，所以我们需要存储一个值的列表：
std::vector<std::vector<T>> m;再考虑键可以是非整数类型，比如字符串、结构体，我们可以使用哈希函数将任意类型转换为整数。不同的键可能会哈希到相同的整数，这被称为冲突，但对于二维数组来说这不是问题，我们只需要同时存储键和值来区分它们。
std::vector<std::vector<std::pair<K, T>>> m;
m.resize(N);
m[hash(key) % N].push_back(std::pair{key, val}); // 插入
for (std::pair<K, T> &p : m[hash(key) % N]) { // 查找
if (p.first == key) { /* 找到 */ }
}这就是用三行代码构建哈希表的方法。没有理由不理解它。
两种类型的哈希表：链地址法与开放寻址法
二维数组是一种链地址法哈希表。嵌套的集合不一定是数组，最常见的是链表数组，树数组也是可行的。
std::vector<std::vector<std::pair<K, T>>> m; // 数组的数组
std::vector<std::list<std::pair<K, T>>> m; // 链表的数组
std::vector<std::map<K, T>> m; // 树的数组另一种类型的哈希表称为开放寻址法，它不使用嵌套集合，而是直接将键值对存储在数组中。发生冲突时，它只需找到另一个数组槽位，如果该槽位为空就使用它，否则就继续探测更多的槽位。探测下一个槽位的方案是确定的，所以给定一个哈希值，它可以找到所有冲突的键。
有不同的探测方案，如线性探测、二次哈希等，但我们不会深入探讨，因为我们将选择链地址法。
为什么哈希函数至关重要？
典型的哈希函数会在整数的整个范围内产生均匀分布。然而，数组大小N远小于整数范围，所以通过hash(key) % N来缩小范围。
即使键已经是整数，也仍然需要哈希函数，因为它可以减少冲突。例如，如果键是指针，由于对齐的原因，键很可能是8的倍数，这意味着key % N只能使用1/8的槽位，这意味着每个使用的槽位平均会有8倍多的键，这意味着搜索现有键需要更长的时间。
最坏的情况是所有键都映射到同一个槽位，使得搜索的时间复杂度从O(1)变为O(N)。使用哈希函数时这种情况不太可能发生，因为即使键的分布不均匀，键到槽位的映射实际上（伪）是随机的。
最大负载因子
为什么哈希表的平均时间复杂度是O(1)呢？因为相对于槽位的数量，键的数量是有限制的。假设N个槽位可以存储k × N个键，那么每个槽位平均有k个键。这个比率被称为负载因子 = 键的数量/槽位的数量。
当达到最大负载因子时，键会被迁移到一个更大的哈希表中（称为重新哈希），这可以由插入操作触发。和动态数组一样，新的哈希表会以指数方式变大，所以均摊后的插入成本仍然是O(1)。
8.2 Redis的哈希表
最坏情况的延迟会导致可扩展性问题
哈希表的原理很简单，就像那三行代码的哈希表所示。那么为什么还要自己编写一个呢？为什么不直接使用C++ STL中的std::unordered_map呢？因为如果Redis只是通过网络使用STL集合，在大规模部署时会出现问题。
有两种可扩展性问题：吞吐量和延迟。吞吐量问题通常有通用的、简单的解决方案，比如分片和只读副本，而延迟问题通常是特定领域的，更难解决。吞吐量是平均情况的问题，而延迟通常是最坏情况的问题。
对于哈希表来说，最大的延迟问题来自插入操作，它可能会触发O(N)的调整大小操作。现代机器很容易拥有数百GB的内存，但调整如此规模的哈希表大小需要很长时间，会导致服务不可用。
有一个解决这个问题的方案，但它不在C++ STL或大多数通用库中，因为大多数数据结构库是针对吞吐量进行优化的，而不是延迟。人们通常认为每种需求都有相应的库，但你学得越多，就会发现这并不总是真的。
渐进式哈希表调整大小
解决调整大小延迟问题的方法是渐进式地进行。分配新的哈希表后，不要一次性移动所有的键，只移动固定数量的键。然后，每次使用哈希表时，再移动一些键。这可能会在调整大小期间减慢查找速度，因为有两个哈希表需要查询。
分配哈希表后，槽位必须初始化。所以触发调整大小似乎仍然是O(N)的操作。使用calloc()可以避免这个问题。当分配一个大数组时，calloc()从mmap()获取内存，并且从mmap()获取的页面在第一次访问时才进行分配和清零，这实际上是一个渐进式零初始化的数组。
对于较小的数组，calloc()从堆中获取内存，这需要立即清零，但延迟是有限的。大小数组的阈值由libc决定。
应该使用calloc()而不是malloc() + memset()来避免O(N)的初始化延迟。但如果你使用的是数据结构库或高级语言，你可能没有这种级别的控制权。这就是需要底层C代码的地方。
链地址法哈希表健壮、简单、灵活
下一个延迟问题是冲突。总是存在出现非常长的冲突链的可能性。链地址法哈希表不太容易出现冲突，因为冲突的键共享同一个槽位，而对于开放寻址法，冲突的键会占用多个槽位，进一步增加了冲突的概率。
有许多探测策略可供选择。简单的探测策略，如线性探测，会导致更高的冲突概率，所以它们大多只存在于教科书中。而链地址法哈希表则无需考虑这个问题。
我们将编写一个使用链表的链地址法哈希表。但为什么选择链表而不是数组呢？
- 1. 延迟：插入操作始终是O(1)，找到节点后删除操作也是O(1)。
- 2. 引用稳定性：即使调整大小后，指向数据的指针仍然有效。
- 3. 可以实现为侵入式数据结构：稍后会解释。
引用稳定性是STL使用链地址法哈希表的原因。它使哈希表更灵活，使用时更不容易出错。
8.3 C语言中的通用集合
我们的哈希表以后会用于不同的数据类型，但C++泛型并不是唯一的方法；我们将学习另一种更灵活的解决方案，称为侵入式数据结构。这是一种被忽视的技术，因为教科书不教它，但许多实际的C项目，比如Linux内核，都在使用它。
但首先，让我们回顾一下使数据结构通用化的常见方法及其缺点，以链表为例。
方法1：void *指针
C语言中最常见的方法是使用无类型指针void *。
struct Node {
void *data; // 指向任何类型的数据
struct Node *next;
};如果数据恰好是指针大小或更小，就可以存储在里面。但通常数据更大，或者大小可变，所以数据可能是从堆中分配的，这有一些缺点：
- 1. 访问数据时需要多一层指针间接引用。
- 2. 更多的动态内存管理。
- 3. 没有类型检查。
方法2：使用C宏、代码生成器生成代码
C++模板会为每种类型生成代码，这可以用C宏来模拟。
#define DEFINE_NODE(T) struct Node_ ## T { \
T data; \
struct Node_ ## T *next; \
} \
// 以及所有的链表函数...也可以不使用宏，而是使用代码生成器来实现。从编译器的角度来看，这与C++泛型是一样的。但从程序员的角度来看，这是一团无法调试、难以维护的混乱代码。别费心思用这个了，我们将学习更好的方法。
8.4 侵入式数据结构
在数据中嵌入结构体
上面的两种方法是用结构体来封装数据：
template <class T>
struct Node {
T data; // 或者 `T *data`
struct Node *next;
};如果我们不封装数据，而是将结构体添加到数据中会怎样呢？
struct Node {
Node *next;
};
struct MyData {
int foo; // 数据
Node node; // 嵌入的结构体
// 更多数据...
};结构体Node不包含数据，相反，数据包含了这个结构体。这是如何实现通用化的呢？示例：
size_t list_size(struct Node *node) {
size_t cnt = 0;
for (; node != NULL; node = node->next) {
cnt++;
}
return cnt;
}list_size()不涉及任何数据；它只对唯一的节点类型struct Node进行操作。数据结构关注的是结构体，而不是数据类型，所以通过不包含数据，数据结构代码可以实现通用化。
与封装数据的方法相比：
template <class T>
size_t list_size(struct Node<T> *node);模板函数依赖于数据类型T，即使实际上并不使用它。
使用侵入式数据结构
将“无数据”的结构体嵌入到数据类型中被称为侵入式数据结构，因为你需要修改你的数据类型才能使用它。现在数据结构与数据无关了，要获取数据，只需偏移结构体的地址即可。
Node *pnode = some_data_structure_code();
MyData *pdata = (MyData *)((char *)pnode - offsetof(MyData, node));使用宏使代码更简洁且不易出错：
#define container_of(ptr, T, member) \
((T *)( (char *)ptr - offsetof(T, member) ))
MyData *pdata = container_of(pnode, MyData, node);container_of是侵入式数据结构的事实上的标准。“Container”指的是包含结构体的数据类型。在Linux内核中，container_of的定义如下：
#define container_of(ptr, T, member) ({ \
const typeof( ((T *)0)->member ) *__mptr = (ptr); \
(T *)( (char *)__mptr - offsetof(T, member) ); })它有一个额外的类型检查，使用GCC扩展typeof来确保ptr与T::member匹配。({...})语法是GCC扩展，允许在表达式中使用语句。
优点1：无需间接引用即可快速访问数据
void *指针需要额外的指针追踪来访问数据：
┌──┐ ┌──┐
│ ▼ │ ▼
┌Node──┐ │ ┌Node──┐ │ ┌Node──┐
│┌────┐│ │ │┌────┐│ │ │┌────┐│
││next├┼─┘ ││next├┼─┘ ││next├┼──▶ …
│├────┤│ │├────┤│ │├────┤│
││ptr ││ ││ptr ││ ││ptr ││
│└─┬──┘│ │└─┬──┘│ │└─┬──┘│
└──┼───┘ └──┼───┘ └──┼───┘
▼ ▼ ▼
┌────┐ ┌────┐ ┌────┐
│data│ │data│ │data│
└────┘ └────┘ └────┘侵入式数据结构避免了额外的间接引用，因为结构体和数据是同一个节点。
┌Data──┐ ┌Data──┐ ┌Data──┐
│ … │ │ … │ │ … │
│┌────┐│ │┌────┐│ │┌────┐│
││node├┼──▶││node├┼──▶││node├┼──▶ …
│└────┘│ │└────┘│ │└────┘│
│ … │ │ … │ │ … │
└──────┘ └──────┘ └──────┘从计算机的角度来看，这和模板代码一样好：
┌──┐ ┌──┐
│ ▼ │ ▼
┌Node──┐ │ ┌Node──┐ │ ┌Node──┐
│┌────┐│ │ │┌────┐│ │ │┌────┐│
││next├┼─┘ ││next├┼─┘ ││next├┼──▶ …
│├────┤│ │├────┤│ │├────┤│
││data││ ││data││ ││data││
│└────┘│ │└────┘│ │└────┘│
└──────┘ └──────┘ └──────┘优点2：最小化内存管理
手动内存管理容易出错，所以越少越好。侵入式数据结构代码不需要分配结构节点，因为它从数据中借用空间；数据是如何分配的甚至都不重要。
对于我们的哈希表代码，我们只需要管理槽位的数组，而不需要管理链表节点。
优点3：在多个集合之间共享数据节点
一个数据节点有可能属于多个数据结构。
struct MultiIndexedData {
// 数据...
HashNode node1; // 嵌入的结构体
TreeNode node2; // 另一个结构体
};例如，Redis有序集合既按名称索引，又按分数索引，需要两个数据结构。对于非侵入式数据结构，一个索引包含数据，另一个索引包含指向数据的指针，这需要额外的分配和间接引用。而对于侵入式数据结构，你可以向单个数据节点添加多个数据结构。这种灵活性是侵入式数据结构所独有的。
优点4：在同一个集合中使用多种数据类型
虽然侵入式数据结构不是类型安全的，但它们有在同一个集合中使用不同数据类型的灵活性，只要你有办法区分它们。例如，你可以使用不同的数据类型作为链表的第一个元素。
8.5 哈希表总结
- 1. 哈希表的两类：开放寻址法和链地址法。
- 2. 链地址法哈希表的原理：集合的数组。
- 3. 大规模使用哈希表的挑战：最坏情况的延迟。
- 4. 用于实现通用数据结构的侵入式数据结构。
这些就是你需要知道的所有内容。你可以开始编码了，或者看下一章的代码。
源代码：
