[Redis源码阅读]dict字典的落到实处

[Redis源码阅读]dict字典的落到实处

dict的用途

dict是1种用于保存键值对的肤浅数据结构,在redis中运用1②分布满,比方数据库、哈希结构的底层。

当实行上边这几个命令:

> set msg "hello"

以及采纳哈希结构,如:

> hset people name "hoohack"

都会动用到dict作为底层数据结构的兑现。

  1. v属性保存着键值对的值,在那之中的键值能够是指针,或许是uint_6四类型,也或者是int6四_t 类型。
  2. next属性是指向另二个哈希表节点的指针,这几个指针把七个哈希值同样的节点连接在联合签名,来化解hash碰撞难点。

消除键争辩

当有五个或几个以上的键被分配到了哈希表数组的一模2样索引上时,称那一个键发生了抵触(
collision)

Redis 的哈希表使用链地址法来化解争持,每一种哈希表节点都有五个 next
指针,四个哈希表节点能够用 next
指针构成一个单项链表,被分配到同贰个目录上的七个节点可以用那一个对单向链表连接起来,那就缓慢解决了键争论的难题.

如前方的字典暗暗提示图所示, 键 k0 和 k一 的索引值均为壹,这里只需用 next
指针将五个节点连接起来.
,因为dictEntry 节点组成的链表未有表尾指针,为了
速度驰念,程序连接将新节点调整价格到链表的表头地点,排在其余已有节点的前方,那样插入的复杂度为$
O(1)$.

施行rehash的流程图

澳门新萄京 1

能够观察,字典dict结构中,最重大的就是dictht
这类别型
的ht哈希表(平日都以ht[0]在起成效),哈希表的数据结构dictht定义为:

渐进式 rehash

上1节说过, 扩大或收缩哈希表须要将 ht[0] 里的保有键值对 rehash 到
ht[1] 中,不过这一个 rehash
动作并不是二遍性,聚焦式达成的,而是分多次,渐进式完毕的.

诸如此类做的由来是,当哈希表里保存的键值对多至百万以致亿品级时,二回性地全部rehash 的话,强大的总括量会对服务器质量形成惨重影响.

以下是渐进式 rehash 的步骤:

  1. 为 ht[1] 分配空间
  2. 在字典中保险三个索引计数器变量 rehashidx, 将它的值设置为0,表示
    rehash 正式启幕
  3. 在 rehash 举行时期,每回对字典实行增加和删除改查时,顺带将 ht[0] 在
    rehashidx 索引上的享有键值对 rehash 到 ht[1] 中,同时将 rehashidx
    加 1.
  4. 随着操作不断开始展览,最后在有个别时刻点上, ht[0] 全体的键值对整个 rehash
    到 ht[1] 上,那是讲 rehashidx 属性置为 -壹,,表示 rehash操作实现.
  5. 在渐进式 rehash 施行时期,新扩张到字典的键值对1律保存到 ht[1]
    里,不会对 ht[0] 做增多操作,那1办法确定保障了 ht[0]只减不增,并乘机
    rehash 实行, 最后编制程序空表.

Ref:
https://segmentfault.com/a/1190000004850844

负载因子解释

澳门新萄京,负载因子 = 哈希表已保存节点数量 / 哈希表大小

负载因子越大,意味着哈希表越满,越轻便产生争执,品质也就越低。因而,一般的话,当负载因子大于有些常数(恐怕是
一,也许 0.7伍 等)时,哈希表将机关扩大体积。

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

哈希表节点

哈希表节点使用 dictEntry 表示,每一个 dictEntry 结构保留着2个键值对

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

瞩目这里 v 属性保存着键值对中的值,个中的键值能够是指针,或是 uint_6四整数,又恐怕是 int6四_t 整数.
next
属性是指向另3个哈希表节点的指针,那个指针将八个哈希值一样的键值对接二连三在1块,以此来缓慢解决键值争辩(collision)难点.

下图显示了二个普通状态下的字典(未有 rehash 举办)

澳门新萄京 2

rehash(重新散列)

当操作更为多,比方持续的向哈希表添澳成分,此时哈希表要求分配了更加多的上空,假使接下去的操作是频频地删除哈希表的成分,那么哈希表的轻重缓急就能够爆发变化,更注重的是,现在的哈希表不再需求那么大的空中了,在redis的达成中,为了确认保障哈希表的负荷因子保持在一个客观限定内,当哈希表保存的键值对太多恐怕太少时,redis对哈希表大小实行对应的扩张和减少,称为rehash(重新散列)。

消除键争执

莫不存在那样1种情景:八个差别的键值对,计算出的哈希值和索引值是如出壹辙的。那就叫hash碰撞。怎么消除hash碰撞的难题啊??大家想到了种种hash节点都有2个next指针,借助于这些next指针,大家得以将哈希值同样的节点串起来,形成1个单链表。

哈希算法

Redis 使用 MurmurHash2
算法
来总结键的哈希值.
Redis 计算哈希值和目录的点子如下:
hash = dict->type->hashFunction(k);
index = hash & dict->ht[0].sizemask

协会的定义

先看看字典以及相关数据结构体的概念:

  1. table属性是一个数组,数组中种种成分都以指向三个dictEntry结构的指针,每一种dictEntry结构保留着2个键值对。
  2. size属性记录了hash表的大小,也正是table那几个数组的大小。
  3. sizemask属性和哈希值共同决定了二个键应当被内置数组的哪位索引上。

字典

Redis 中的字典 由 dict.h/dict 结构意味着:

typedef struct dict {
    dictType *type;     //类型特定函数
    void *privdata;     //私有数据
    dictht ht[2];       //哈希表
    int rehashdx;      //rehash 索引,当 rehash 不在进行时,值为-1
} dict;

type 和 privdata 是针对性不一样门类的键值对,为创建多态字典而设置的
type针对二个 dictType 结构的指针, 每一种dictType
结构保留了1簇用于操作特作一定项目键值对的函数, Redis
会为用途分歧的字典设置不一样的品类特定函数.

pridata 则保存了亟需传给那多少个特定类型函数看可选参数.
ht 属性,包蕴五个数组,数组的每一项都是贰个 dictht
哈希表,一般情形下字典只使用ht[0]
哈希表,ht[1]哈希表只会在对哈希表举行 rehash 时使用.
rehashidex 记录了 rehash 当前的速度,假诺未有开始展览 rehash, 值就为-壹.

哈希表

/* 哈希表结构 */
typedef struct dictht {
    dictEntry **table; /* 哈希表节点数组 */
    unsigned long size; /* 哈希表大小 */
    unsigned long sizemask; /* 哈希表大小掩码,用于计算哈希表的索引值,大小总是dictht.size - 1 */
    unsigned long used; /* 哈希表已经使用的节点数量 */
} dictht;

能够看出,哈希表结构dictht中,最入眼的正是table瓜时素指向的哈希表节点dictEntry这种键值对协会,hash表节点dictEntry的结构定义为:

哈希表

Redis 字典所运用的哈希表由 dict.h/dictht 结构定义:

typedef struct dictht {
    dictEntry **table;      //哈希表数组
    unsigned long size;     //哈希表大小
    unsigned long sizemask; //用于计算索引值,
                            //总是等于 size - 1
    unsigned long used;     //哈希表已有节点数量
}  dictht;

table 属性是三个数组, 数组中各种元素都以3个对准 dictEntry 结构的指针,
各样 dictEntry 结构保留着1个键值对.
size 属性记录了哈希表的深浅,也等于 table 数组的轻重
sizemask 属性和哈希值一同决定一个键相应被停放 table 数组的哪个索引上边

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图