`

字典实现

阅读更多
    字典在 Redis 中的应用相当广泛,如 Redis 的数据库、Hash 类型等的底层实现都用到了字典。
    Redis 的字典使用了哈希表,其中可以包含多个哈希表节点,每个节点就保存了字典中的一个键值对。这两者的结构定义分别如下:
typedef struct dictht{
    dictEntry **table;         // 哈希表节点数组
    unsigned long size;        // 哈希表节点数组大小
    unsigned long sizemask;    // 哈希表大小掩码,用于计算索引值,总是等于 size-1 
    unsigned long used;        // 该哈希表已有节点的数量
}dictht;

typedef struct dictEntry{
    void *key;          // 键
    union{              // 值
        void *val;
        uint64_t u64;
        int64_t s64;
    }v;
    struct dictEntry *next;    // 指向下一个哈希表节点,形成链表
}dictEntry;

    从 dictEntry 结构的定义可以看出,键值对中的值可以是一个指针,或者是一个 uint64_t 类型的整数,又或者是一个 int64_t 类型的整数。另外,其中的 next 属性是指向另一个具有相同哈希值的节点的指针,用以避免键冲突。
    哈希表的定义给出后,接下来再看看 Redis 中的字典的结构表示。
typedef struct dict{
    dictType *type;          // 类型特定函数
    void *privdata;          // 私有数据
    dictht ht[2];            // 哈希表
    int rehashidx;           // 渐进式 rehash 索引,当没进行 rehash 时,值为 -1
}dict;

typedef struct dictType{
    unsigned int (*hashFunction)(const void *key);       // 计算哈希值的函数
    void *(*keyDup)(void *privdata, const void *key);    // 复制键的函数
    void *(*valDup)(void *privdata, const void *obj);    // 复制值的函数
    void (*keyDestructor)(void *privdata, void *key);    // 销毁键的函数
    void (*valDestructor)(void *privdata, void *obj);    // 销毁值的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);  // 对比值的函数
}dictType;

    dict 结构中的 type 属性是一个指向 dictType 结构的指针,该结构保存了一组用于操作特定类型键值对的函数,以便 Redis 为不同用途的字典设置不同的类型特定函数。privdata 属性中则保存了需要传给那些类型特定函数的可选参数。这两个属性主要是为创建多态字典,针对不同类型的键值对而设置的。ht 属性是一个包含两个 dictht 哈希表的数组。一般情况下只使用 ht[0] 哈希表,ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash(即重新对 ht[0] 哈希表中的节点进行哈希值计算) 时使用。属性 rehashidx 也与 rehash 有关,它记录了 rehash 目前的进度。如果目前没有进行 rehash,它的值就为 -1。
    下图是一个没有进行 rehash 时的普通状态下的字典的示例。

    当要添加一个新的键值对到字典中时,Redis 会先根据键值对的键计算出哈希值和索引值,然后将该包含该键值对的哈希表节点放到哈希数组的指定索引上面。计算方式大致如下:
        hash = dict->type->hashFunction(key);  # 使用字典设置的哈希函数计算哈希值
        index = hash & dict->ht[x].sizemask;   # 根据情况,ht[x] 可以是 ht[0] 或 ht[1]
    在键发生冲突时,Redis 使用了链地址法来处理,即利用哈希表节点结构 dictEntry 中 的 next 指针来指向具有相同索引的节点。不过为了速度考虑,程序总是将新节点添加到链表的表头位置(复杂的为 O(1)),排在其他已有节点的前面。
    接下来再来说说字典的 rehash。
    由于哈希表中保存的键值对会随着操作的不断执行而逐渐地增多或减少,所以为了让哈希表的负载因子(load factor)维持在一个合理的范围内,Redis 需要在必要的时刻对哈希表的大小进行相应的扩展或收缩。这可以通过执行 rehash 操作来完成。大致步骤如下:
    1、根据要执行的操作以及 ht[0] 当前已包含的键值对的数量为字典的 ht[1] 哈希表分配空间:
    a、如果执行的是扩展操作,则 ht[1] 的大小将为第一个大于等于 ht[0].used * 2 并且是 2 的 n 次幂的数。
    b、如果执行的是收缩操作,则 ht[1] 的大小将是第一个大于等于 ht[0].used 并且是 2 的 n 次幂的数。
    2、将 ht[0] 中的所有键值对 rehash 到 ht[1] 上面。
    3、迁移完 ht[0] 中的键值对后,释放 ht[0],再将 ht[1] 设置为 ht[0],并新建一个空白哈希表作为 ht[1],以便为下一次 rehash 做准备。
    那么 Redis 如何知道在什么时候对哈希表进行扩展或收缩呢?
    总的来说,当程序满足以下任意一个条件时,Redis 将会自动开始进行扩展操作:
    1、服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且哈希表的负载因子大于等于 1。
    2、服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且哈希表的负载因子大于等于 5。
    其中,哈希表的负载因子通过下面公式计算:
        load_factor = ht[0].used / ht[0].size; # 即:哈希表已有节点数 / 哈希表大小
    另一方面,当哈希表的负载因子小于 0.1 时,程序会自动开始对哈希表执行收缩操作。
    另外需要指出的是,在对哈希表进行扩展或收缩时,将 ht[0] 中的键值对 rehash 到 ht[1] 中的这个动作并非是一次性、集中式地完成的,而是分多次、渐进式地完成的。这样做的原因是为了避免在 ht[0] 中的键值对较多时,如果一次性将这些键值对全部迁移到 ht[1] 的话,可能会导致服务器在一段时间内停止对外服务。
    渐进式 rehash 的详细步骤如下:
    1、为 ht[1] 分配空间。
    2、将 dict 结构中的索引计数器字段 rehashidx 的值设置为 0,表示 rehash 开始。
    3、在 rehash 进行期间,每次对字典执行添加、删除、查找或者更新操作时,除了执行指定的操作,程序还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1],然后将 rehashidx 的值增 1。在这个过程中,字典的删除、查找和更新操作会依次在 ht[0] 和 ht[1] 中查找对应的键,而新添加到字典的键值对会一律保存到 ht[1] 中,以保证 ht[0] 中包含的键值对数量只减不增,能随着 rehash 操作的进行而最终变成空表。
    4、随着字典操作的不断执行,ht[0] 的所有键值对会在某个时刻被 rehash 到 ht[1] 上,这时再将 rehashidx 属性的值设为 -1,表示 rehash 操作已完成。

参考书籍:《Redis 设计与实现》第四章——字典。
  • 大小: 15.4 KB
分享到:
评论

相关推荐

    简单的字典实现

    在这个“简单的字典实现”项目中,我们将探讨如何使用Java来创建一个基本的电子词典应用,这个应用能够查询单词、词组,并且支持用户向词典中添加新词汇。 首先,我们需要理解词典的基本结构。在数据结构的角度,...

    java实现字典

    本项目“java实现字典”旨在利用Java来构建一个具备查词、改错、联想功能的智能字典工具,这些功能对于学习者和专业人士来说具有很高的实用价值。 首先,让我们详细了解一下每个功能的实现: 1. **查词**: 在...

    java电子字典实现

    总的来说,Java电子字典的实现是一个综合性的项目,涉及到Java编程、数据库设计、GUI开发等多个方面,对于提升编程技能和理解软件工程有着重要的实践价值。对于学习者来说,这样的项目不仅可以帮助巩固理论知识,还...

    WPF通过资源字典加绑定实现多语言切换

    本教程将深入讲解如何利用WPF中的资源字典和数据绑定来实现多语言切换。 资源字典在WPF中扮演着关键角色,它允许开发者集中存储和管理应用中的可重用资源,如颜色、字体、样式和模板。在多语言场景下,我们可以为每...

    Python字典实现伪切片功能

    早上起床看到一条评论,有点懵逼,字典切片? 查阅了一下Python资料,3.6版本的Python改写了dict的内部算法,3.6版本之前是无序的; So,现在就是有序的啦,注意的是这个顺序是key的插入顺序; 但字典虽有序没下标怎么切片?...

    数据字典实现面包屑效果

    react数据字典结合路由实现面包屑的切换效果

    常见的字典数据结构实现

    首先,二叉搜索树(BST)是最基础的字典实现之一。它的每个节点包含一个键、一个关联的值、一个指向左子节点的指针和一个指向右子节点的指针。在二叉搜索树中,所有左子节点的键都小于父节点的键,而所有右子节点的...

    一种灵活的web表单字典的实现.pdf

    本文提供了一种灵活的 Web 表单字典的实现方法,使用 JavaScript 和 JSP 技术,实现了一个低并发系统下的字典实现方式。通过使用 hidden 变量保存字典 ID,input 文本框存储字典值,并使用 span 标签支持 ondblclick...

    Python使用字典实现的简单记事本功能示例

    在本示例中,字典被用来实现一个简单的记事本功能,用户可以通过添加、更新、查看和删除条目来管理他们的日程。以下是基于这个例子的详细知识点: 1. **字典数据结构**: - 字典是Python中的一个内置容器型数据...

    C#简单的通用基础字典实现方法

    本文将详细介绍如何在C#中实现一个简单的通用基础字典,包括字典的索引、记录管理、回调功能以及查询技巧。 首先,字典在C#中是通过`System.Collections.Generic.Dictionary, TValue>`类实现的。这个类提供了高效的...

    Excel VBA_字典套字典实例集锦.zip_Excel VBA_VBA 字典_excel vba实例_vba excel_字

    - **复杂逻辑处理**:如通过字典实现多条件查询,嵌套字典可以用来表示多层关系的数据。 5. **错误处理**: 使用字典时要注意键的唯一性,尝试添加已存在的键会引发错误,因此在添加元素时需要检查键是否已存在。...

    超强字典有多强就有多强

    "超强字典"通常指的是具有高效性能、大容量存储以及高度自定义功能的字典实现。在这个主题中,我们将深入探讨字典的原理、优化策略以及在实际应用中的强大之处。 首先,我们要理解字典的基本概念。字典是一种键值对...

    Python基于字典实现switch case函数调用

    下面我们将详细介绍如何利用字典实现一个`switch`...`case`式的函数调用,并探讨在实现过程中可能遇到的问题及其解决方案。 首先,让我们来看一个基本的实现方式。假设我们有一个函数库,包含几个处理不同情况的...

    python矩阵/字典实现最短路径算法

    本文将深入探讨如何使用Python矩阵和字典实现Dijkstra算法,这是一种常用的求解单源最短路径问题的算法。 首先,我们来看矩阵实现。矩阵通常用于表示图的邻接矩阵,其中元素`matrix[i][j]`表示节点i到节点j的边的...

    python字典

    "源码"可能是指字典在Python内部的实现机制,而"工具"可能指的是利用字典实现的一些实用功能或工具。 1. **字典创建**: Python中可以通过大括号{}或者dict()函数创建字典。例如: ```python dict1 = {'name': '...

    shared-memory-dict:一个非常简单的共享内存字典实现

    一个非常简单的字典实现。 要求:Python> = 3.8 >> from shared_memory_dict import SharedMemoryDict >> smd = SharedMemoryDict ( name = 'tokens' , size = 1024 ) >> smd [ 'some-key' ] = 'some-value-with-...

    c-dictionary-trie:用 C 编写并由前缀树支持的字典实现

    显现dictionary.h 字典实现的头文件,它创建了字典 API 应该如何工作的框架。 这给出了关于如何实现每种方法的严格规范,并允许用户在不阅读完整源代码的情况下参考这些信息。 dictionary.c 字典实现的源代码文件,...

Global site tag (gtag.js) - Google Analytics