实现字典的方法有很多种:
在众多可能的实现中, 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 状态。 哈希算法Redis 目前使用两种不同的哈希算法:
dict * d = dictCreate( & hash_type, NULL); table 属性分配任何空间:
|
根据字典所处的状态, 将一个给定的键值对添加到字典可能会引起一系列复杂的操作:
当第一次往空字典里添加键值对时, 程序会根据 d->ht[0]->table 分配空间 (在目前的版本中, 4 )。
以下是字典空白时的样子:
以下是往空白字典添加了第一个键值对之后的样子:
在哈希表实现中, 当两个不同的键拥有相同的哈希值时, 我们称这两个键发生碰撞(collision), 而哈希表实现必须想办法对碰撞进行处理。
字典哈希表所使用的碰撞解决方法被称之为key4 和 key4 的哈希值和 0 号索引上发生碰撞。
通过将 key1-value1 两个键值对用链表连接起来, 就可以解决碰撞的问题:
对于使用链地址法来解决碰撞问题的哈希表 size属性)和它所保存的节点的数量(ht[0])进行 rehash 操作: 在不修改任何键值对的情况下,对哈希表进行扩容, 尽量将比率维持在 1:1 左右。
ht[0] 进行检查, 对于 size 和 ratio =used / size 满足以下任何一个条件的话,rehash 过程就会被激活:
ratio 大于变量 dict_force_resize_ratio 的值为
什么时候 BGSAVE 或 copy on write 机制, 程序会会暂时将 dict_can_resize 会重新被设为真。
另一方面, 当字典满足了强制 rehash 的条件时, 即使 BGSAVE 或
创建一个比 ht[1]->table ;将 ht[1]->table ;将原有 ht[1] 替换为新的 设置字典的 0 ,标识着 rehash 的开始;为 ht[0]->used 的两倍;
这时的字典是这个样子:
在这个阶段, ht[1]->table , 因为 rehash 是分多次进行的(细节在下一节解释), 字典的 ht[0] 的哪个索引位置上。
以下是 2 时,字典的样子:
注意除了节点的移动外, 字典的 ht[0]->used 和 ht[0] 迁移到
释放 ht[1] 来代替 ht[1] 成为新的 ht[1] ;将字典的 -1 ,标识 rehash 已停止;
以下是字典 rehash 完毕之后的样子:
对比字典 rehash 之前和 rehash 之后, 新的 _dictRehashStep 和 _dictRehashStep 用于对数据库字典、以及哈希键的字典进行被动 rehash ;
_dictRehashStep , ht[1]->table 。
在 rehash 开始进行之后(-1), 每次执行一次添加、查找、删除操作, dictRehashMilliseconds 可以在指定的毫秒数内, 对字典进行 rehash 。
当 Redis 的服务器常规任务执行时, ht[0] 上进行,还需要在 ht[1] 而不是 ht[0] 的节点数量在整个 rehash 过程中都只减不增。
上面关于 rehash 的章节描述了通过 rehash 对字典进行扩展(expand)的情况, 如果哈希表的可用节点数比已用节点数大很多的话, 那么也可以通过对哈希表进行 rehash 来收缩(shrink)字典。
收缩 rehash 和上面展示的扩展 rehash 的操作几乎一样,它执行以下步骤:
扩展 rehash 和收缩 rehash 执行完全相同的过程, 一个 rehash 是扩展还是收缩字典, 关键在于新分配的 ht[1]->table 比 ht[1]->table 比 数据库》一章的《迭代器实现 —— 对字典进行迭代实际上就是对字典所使用的哈希表进行迭代:
整个迭代过程可以用伪代码表示如下:
def iter_dict(dict):字典的迭代器有两种:
以下是迭代器的数据结构定义:
/*以下函数是这个迭代器的 API ,它们的作用及相关算法复杂度:
函数 | 作用 | 算法复杂度 |
---|---|---|
dictGetSafeIterator | 创建一个安全迭代器。 | O(1) |
NULL 。 | O(1) | |
<tt literal"="" style=" color: rgb(34, 34, 34); font-size: 1.1em;">dictReleaseIterator | 释放迭代器。 | O(1) |