Redis-字典

Redis 还有一种比较常用的数据类型,字典。C 语言没有这种数据结构,但是 在JAVA 语言中的 map,和 PHP 语言里的 关联数组,就是这种类型,它用来保存 key => value 的键值对,要求键必须是唯一,在字段中,已知一个 key,对这个的 key 对应 value 做 CRUD操作,都非常方便。

Redis 自己实现了这个结构,并且用它来作 哈希键的底层实现之一,如果 一个哈希类型包含的键值对较多 或者 键值对中的元素都是较长的字符串,就会用 字典 来作为它的实现。数据库的 CRUD 操作也是作用在 字典上。具体的源码在文件 src/dict.h,它的底层使用哈希表,哈希表内部可以拥有多个节点,每个节点上就存储这一个键值对。

// 哈希表
typedef struct dictht {
    dictEntry **table;  // 哈希表数组
    unsigned long size; // 哈希表大小,一般是2的指数
    unsigned long sizemask; // 哈希表掩码,等于 size - 1
    unsigned long used; // 哈希表已有节点数量,used / size 这个是装载因子,比值越大,hash冲突月 
} dictht;

// 哈希表节点
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

dictht 结构体中 table 数组中的每个元素,都是一个指向哈希表节点 dictEntry 的指针,size 标识dictEntry指针数组,就是 table 数组的长度,它总是2的指数;sizemask 的值为 size - 1, 这个属性和哈希值决定了一个键要被放在 table 数组的哪个索引位置上(通过hash & sizemask计算出),used 的属性则记录了哈希表目前已有节点的数量,size / used 是装在因子,这个值越大,哈希冲突的概率就越高。

这个就是 dictdictEntry 的结构示意:

dictEntry 结构是哈希表的节点,其中 key 是键值对的键,而 v 是键值对的值,v 中可以是一个指针、uint64 的整数、uint64的整数或者是一个 double 的浮点数,next 属性是指向下一个哈希表节点 dictEntry 结构体的指针,所谓下一个哈希表节点,就是当哈希键 key 相同的哈希表节点,它们会挨个排列,前一个的 next 指针指向后一个。

Hash键冲突

Redis 使用 MurmurHash 算法来计算键的hash值,虽然在效率上和随机性上很好,但是还是会产生 hash冲突。
针对这个问题,采用了 拉链法 解决冲突。next 指针,表示两个相同的hash组成的一个链表。
包含多个键hash值相同的情况:

每次冲突时,都会从头部插入新的键,时间复杂度保证都是O(1)。

dict 结构体里,管理这两个的 dictht

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

typeprivdata 属性是为实现多态字典而设置的,主要是用于不同类型的键值对。其实,type 是指向 dictType 结构的指针,在 dictType 结构体中,保存着一系列的方法:

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

ht 是拥有两个元素的数组,每个都是一个 dictht。一般情况,使用第1个索引位置的哈希表来存储,第二个索引位置的哈希表一般是做 rehash 时使用的。rehashidx 就是表示是否正在做 rehash,如果目前不是正在进行,它的值为 -1。iterators 是当前正在运行的迭代器数目。

typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
    /* unsafe iterator fingerprint for misuse detection. */
    long long fingerprint;
} dictIterator; 

这是字典的迭代器。d 是指向字典的指针,index 是迭代器当前索引的位置。

Rehash

如果哈希表的数据变的越来越多,在装载因子(dictht 中 size / used 的比值)超过预定时,
这时,Redis 会对哈希表做 Rehash 操作,它采用的是一种增量式重哈希,就是将rehash的过程,
分散到所有对 dict 的增删改查操作中。
开始 rehash 后,所有的写入操作,都直接写入 ht[1] 里,同时,会将 ht[0] 哈希表在 rehashidx 上的所有键 rehash 至 ht[1],
直到 ht[0] 中键的个数为 0时,rehash 结束。释放 ht[0], 再将 ht[1] 设为 ht[0], 重新申请一个空白哈希表作为新的 ht[1]。

##
Redis对于字典的操作就是这些,还有一些 API,没有做更深入的研究。

如果文章对您的工作有帮助的话,不如请我喝杯咖啡吧,您的支持是我继续写下去的动力。
8090Lambert WeChat Pay

WeChat Pay

8090Lambert Alipay

Alipay

分享到: