Redis中key-value的实现原理
实现字典的方法有很多种：
- 最简单的就是使用链表或数组， 但是这种方式只适用于元素个数不多的情况下；
- 要兼顾高效和简单性，可以使用哈希表；
- 如果追求更为稳定的性能特征， 并且希望高效地实现排序操作的话， 则可以使用更为复杂的平衡树；
在众多可能的实现中， Redis 选择了高效且实现简单的哈希表作为字典的底层实现。
dict 类型的 API ， 它们的作用及相应的算法复杂度：
| 操作类型 | 操作 | 函数 | 算法复杂度 |
|---|---|---|---|
| 创建 | 创建一个新字典 | dictAdd | O(1) |
| 添加或更新给定键的值 | dictFind | O(1) | |
| 在字典中查找给定键的值 | dictGetRandomKey | O(N) | |
| 删除 | 根据给定键，删除字典中的键值对 | dictRelease | O(N) |
| 清空并重置（但不释放）字典 | dictResize | O(N) | |
| 扩大字典 | dictRehash | O(N) | |
| 在给定毫秒内，对字典进行rehash | dict 类型使用了两个指针分别指向两个哈希表。
其中， 0 号哈希表（ht[1]）则只有在程序对 0 号哈希表进行 rehash 时才使用。 接下来两个小节将对哈希表的实现，以及哈希表所使用的哈希算法进行介绍。 ?字典所使用的哈希表实现由 table 属性是一个数组， 数组的每个元素都是一个指向 dictEntry 都保存着一个键值对， 以及一个指向另一个 next 属性指向另一个 dictEntry 可以通过 dictht dictht 和数个 dict 类型，那么整个字典结构可以表示如下： 在上图的字典示例中， 字典虽然创建了两个哈希表， 但正在使用的只有 0 号哈希表， 这说明字典未进行 rehash 状态。 dictCreate 函数创建并返回一个新字典：
dict * d = dictCreate( & hash_type, NULL);
table 属性分配任何空间：
|
key4 和 key4 的哈希值和 0 号索引上发生碰撞。
通过将 key1-value1 两个键值对用链表连接起来， 就可以解决碰撞的问题：
迭代器实现 —— 对字典进行迭代实际上就是对字典所使用的哈希表进行迭代：
- 迭代器首先迭代字典的第一个哈希表， 然后，如果 rehash 正在进行的话， 就继续对第二个哈希表进行迭代。
- 当迭代哈希表时， 找到第一个不为空的索引， 然后迭代这个索引上的所有节点。
- 当这个索引迭代完了， 继续查找下一个不为空的索引， 如此循环， 一直到整个哈希表都迭代完为止。
整个迭代过程可以用伪代码表示如下：
def iter_dict(dict):# 迭代 0 号哈希表
iter_table(ht[ 0 ] -> table)
# 如果正在执行 rehash ，那么也迭代 1 号哈希表
if dict.is_rehashing(): iter_table(ht[ 1 ] -> table)
def iter_table(table):
# 遍历哈希表上的所有索引
for index in table:
# 跳过空索引
if table[index].empty():
continue
# 遍历索引上的所有节点
for node in table[index]:
# 处理节点
do_something_with(node)
字典的迭代器有两种：
- 安全迭代器：在迭代进行过程中，可以对字典进行修改。
- 不安全迭代器： 在迭代进行过程中，不对字典进行修改。
以下是迭代器的数据结构定义：
/** 字典迭代器
*/
typedef struct dictIterator {
dict * d; // 正在迭代的字典
int table, // 正在迭代的哈希表的号码（0 或者 1）
index, // 正在迭代的哈希表数组的索引
safe; // 是否安全？
dictEntry * entry, // 当前哈希节点
* nextEntry; // 当前哈希节点的后继节点
} dictIterator;
以下函数是这个迭代器的 API ，它们的作用及相关算法复杂度：
| 函数 | 作用 | 算法复杂度 |
|---|---|---|
| dictGetSafeIterator | 创建一个安全迭代器。 | O(1) |
| NULL 。 | O(1) | |
| dictReleaseIterator | 释放迭代器。 | O(1) |
?
- 字典由键值对构成的抽象数据结构。
- Redis 中的数据库和哈希键都基于字典来实现。
- Redis 字典的底层实现为哈希表，每个字典使用两个哈希表，一般情况下只使用 0 号哈希表，只有在 rehash 进行时，才会同时使用 0 号和 1 号哈希表。
- 哈希表使用链地址法来解决键冲突的问题。
- Rehash 可以用于扩展或收缩哈希表。
- 对哈希表的 rehash 是分多次、渐进式地进行的。