韦德国际1946英国 > 计算机网络 > redis里面字典的实现,redis数据结构存储Dict设计细

原标题:redis里面字典的实现,redis数据结构存储Dict设计细

浏览次数:159 时间:2019-05-25

聊到redis的Dict(字典),虽说算法上跟市面上一般的Dict实现未有什么分别,但是redis的Dict有一个独树一帜的地点那正是它的rehash(重新散列)和它的字典节点单向链表。

  1. type和privdata是针对性分歧门类的键值对,为创立多态字典而设置的
    type是指向dictType结构的指针,各个dictType结构保留了一簇操作特定类型键值对的函数,redis会为用途不一样的字典设置区别的特定管理函数。
    privdata则保留了传给那一个特定管理函数的可选参数的新闻。

  2. ht属性包括多少个数组,那多个数组都以1个dictht哈希表,一般情形下字典只利用ht[0]本条哈希表,ht[1]只会在对哈希表实行rehash时才会动用。

  3. rehashdx记录了rehash当前的进程,假设没有进展rehash,则 rehashdx值为-一

图片 1

能够观察,哈希表结构dictht中,最关键的就是table相月素指向的哈希表节点dictEntry这种键值对组织,hash表节点dictEntry的构造定义为:

redis里面字典的实现,redis数据结构存储Dict设计细节。当k2和k壹出现计量出键索引同样的事态下,那时候redis的dictEntry(字典节点)有贰个next属性(单项链表),redis会把抵触键索引的元素排到后插入数据的前方,从而缓和了那么些主题材料

字典,又称符号表,是保存键值对的虚幻数据结构。诸多语言都置于字典这种常用的数据结构,可是C语言未有放置,所以redis自个儿来落到实处了字典。

图片 2

Paste_Image.png

是因为楼主算法技术轻易:所以对哈希算法未有太深的明白,所以在此间算法就一窍不通写了,大家有意思味能够百度。

哈希算法

当要将1个新的键值对充分到字典里面时,程序会依据键计算出哈希值和索引值,然后再根据索引值将新键值对停放哈希表数组钦赐的目录上。

 

下图是家常便饭状态(不是在rehash状态)下的字典:

图片 3

redis中的字典由dict.h/dict结构来定义:

typedef struct dictEntry {//字典的节点  
    void *key;  
    union {//使用的联合体  
        void *val;  
        uint64_t u64;//这两个参数很有用  
        int64_t s64;  
    } v;  
    struct dictEntry *next;//下一个节点指针  
} dictEntry;  

typedef struct dictType {  
    unsigned int (*hashFunction)(const void *key); //hash函数指针  
    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;  

/* This is our hash table structure. Every dictionary has two of this as we 
 * implement incremental rehashing, for the old to the new table. */  
typedef struct dictht { //字典hash table  
    dictEntry **table;//可以看做字典数组,俗称桶bucket  
    unsigned long size; //指针数组的大小,即桶的层数  
    unsigned long sizemask;  
    unsigned long used; //字典中当前的节点数目  
} dictht;  

typedef struct dict {  
    dictType *type;  
    void *privdata; //私有数据  
    dictht ht[2];   //两个hash table  
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */ //rehash 索引  
    int iterators; /* number of iterators currently running */ //当前该字典迭代器个数  
} dict;   

rehash

乘胜键值对的逐年扩充或调整和收缩,为了让哈希表的负荷因子保持在3个创造的界定之内,当哈希表保存的键值对太多也许太少时,程序须要对哈希表进行对应的恢宏或然减弱,这么些进度叫做rehash。

Redis 对字典的哈希表实施 rehash 的手续如下:

  1. 为字典的 ht[1] 哈希表分配空间,空间的轻重取决于要施行的操作,以及ht[0]时下包含的键值对数据( used 属性值):
    假诺实行的是扩展操作,那么 ht[1] 的高低为率先个超越等于ht[0].used*2的 $2^n$ .
    一经举行的是减弱操作,那么ht[1]的尺寸为打四个压倒等于ht[0].used 的$2^n$.
  2. 将保留在 ht[0] 中颇具键值对 rehash 到 ht[1] 上面: 任何事指的是再一次总结键的哈希值和索引值,然后将键值对放手 ht[1] 哈希表的钦命地点.
  3. 当 ht[0] 包涵的富有键值对都迁移到了ht[1]之后, 释放 ht[0], 再将 ht[1] 设置为 ht[0],并在 ht[1] 后边成立一个空白的哈希表.

比如,假若程序要对下图的 `ht[0] 举办扩张操作

图片 4

此处输入图片的讲述

ht[0].used 当前值为肆 , $二^三$ 恰好是第三个高于等于 四*2 的值,所以 ht1 哈希表的高低设置为八,下图展现了 ht1 分配了上空之后字典的样子.

图片 5

此处输入图片的叙说

将 ht[0] 蕴涵的多个键值对 rehash 到 ht1, 图下图所示:

图片 6

这里输入图片的描述

释放 ht[0], 将 ht1 设置为 ht[0]. 再分配3个空哈希表. 哈希表的尺寸由原来的四 增加至8.

图片 7

那边输入图片的叙述

目前一经在插入二条成分,此时数据量已经超(英文名:jīng chāo)过dict的负载了,redis就能够启用rehash,尽管是rehash操作但是redis是应用了渐进式操作,并不是须臾间内部存款和储蓄器非常不够用了 就一直操作内部存款和储蓄器,然后全部转变数据,那样会招致操作很耗费时间,redis思量到了这点,然后

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

本文由韦德国际1946英国发布于计算机网络,转载请注明出处:redis里面字典的实现,redis数据结构存储Dict设计细

关键词: 日记本

上一篇:计算机网络:删除和更新,增删改文档上

下一篇:没有了