乐趣区

关于redis:深入理解Redis-数据结构字典

字典,又称为 符号表、关联数组或映射 ,是一种用于保留 键值对 的形象数据结构。在字典中,一个键能够和一个值进行关联,这些关联的键和值称为键值对。键值对中键是 惟一的 , 咱们能够依据 键 key通过映射查找或者更新对应的 值 value

很多高级开发语言有对应汇合反对字典这种数据结构,比方 Java 中的 Map 汇合。 C 语言 并未内置字典这种数据结构,Redis构建了本人的字典实现。

利用

字典在 Redis 中利用十分宽泛,Redis数据库就是应用字典作为数据底层的实现。对数据的 增、删、改、查 操作也是建设在字典之上操作。

当执行命令:

set msg "hello"

在数据库中创立一个键为 msg,值为 hello 的键值对,这个 键值对 就用字典来实现的。创立其余数据类型的键值对,比方 listhashsetsort set 也是用字典来实现的。

解决用来示意数据中的键值对,字典还是 hash 数据类型底层实现之一,比方一个 hash 数据类型 website,蕴含100 个键值对,这些键值对中的键是 网址名称 ,值是 网页地址:

redis> HGETALL website
1)"Redis"
2)"Redis.io"
3)"nacos"
4)"nacos.io"
.....

website键的底层就是一个字典,包好了 100键值对,例如:

  • 键值对中的键为"Redis",值为"Redis.io"
  • 键值对中的键为"nacos",值为"nacos.io"

字典的实现

Redis字典应用哈希表作为底层实现,一个哈希表外面有多个哈希表节点,每个哈希表节点保留字典中的键值对。

哈希表

Redis字典应用的哈希表由 dict.h/dictht 构造来示意:

/* 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 {
     // table 数组 
    dictEntry **table;
    // 哈希表的大小
    unsigned long size;
    // 等于 size-1,用于计算索引值
    unsigned long sizemask;
    // 已有的键值对数量
    unsigned long used;
} dictht;

正文:这是哈希表构造,每个字典有两个实现增量重散列,从旧的哈希表到新的哈希表。

  • table属性的是一个数组,数组中的每个元素都指向哈希节点 dictEntry,每个dictEntry 构造都保留一个键值对。
  • size记录了哈希表的大小,也就是 table 数组的大小。
  • used属性记录了哈希表目前已有的键值对数量。sizemask的值等于 size-1,这个属性和哈希表一起决定键应该放在 table 数组的那个地位上。

下图展现一个大小为 4 空哈希表(没有蕴含工作的键值对):

哈希表节点

哈希表节点应用 dictEntry 构造来示意,每个 dictEntry 构造都保留着一个 键值对

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

其中:

  • key保留键值
  • v放弃值,v能够是一个指针,能够是 uint64_t 整数,也能够是一个 int64_t 整数。
  • next指向另一个哈希表节点的指针,这个指针将多个 哈希值雷同 的键值对连贯在一起,以此解决 hash 抵触 的问题。

下图展现两个 键的 hash 值 雷同的哈希表节点 k0k1,两者通过 next 指针连贯在一起。

字典

Redis 中的字典由 dict.h/dict 构造示意:

typedef struct dict {
    // 类型特定的函数 
    dictType *type;
   // 公有函数
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引 
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;
  • type属性和 privadata 属性是针对不同类型的键值对,为创立多态的字典而设置。
  • type是指向 dictType 构造的指针,每个 dictType 蕴含几组针对特定类型的键值对操作的函数,Redis会为用处不同的字典设置不同的函数。下图展现 dictType 字典类型:

    typedef struct dictType {
      // 计算哈希值
      unsigned int (*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;
    
  • privdata属性保留针对不同的类型操作的函数传的可选参数。
  • ht[2]是蕴含两个数大小的数组,类型为 dictht 哈希表。字典只应用 ht[0] 哈希表,ht[1]只会对 ht[0] 哈希表进行 rehash 时应用。
  • rehashidx记录了 rehash 的进度,如果目前没有进行的rehash,那么它的值为-1

下图为一个一般状态下(没有进行 rehash)的字典:

哈希算法

当要将一个新的键值对增加到字典中,程序须要先依据键值对中的键计算出哈希值和索引值,而后依据索引值,将蕴含新键值的哈希表放在哈希表数组的指定索引上。

Redis计算哈希值和索引值的步骤如下:

  1. 应用字典设置的哈希函数,计算键的哈希值。

    hash = dict—>type->hashFunction(key)

  2. 应用哈希表的 sizemask 属性和哈希值,取余计算出哈希值。

    index = hash & dict ->ht[x].sizemask

理解过 HashMap 底层原理的同学应该晓得,下面计算索引值和 HashMap 找到索引下标的原理是相似的。

什么是取余 & 运算?

取余就是计算两数相除的余数,比方一个数组长度为 4,索引范畴是0~3, 须要搁置0,1,7,搁置如下图所示:

举个例子,要将一个键值对 k0v0增加到下方的空字典表中:

首先计算键的哈希值:

hash = dict—>type->hashFunction(key)

计算键 k0 的哈希值。
假如计算出来的哈希值为8,而后计算索引值:

index = dict -> hash & ht[0].sizemask = 8 & 3 = 0;

计算出键 k0 的索引值 0,这示意键值对k0v0的节点搁置到哈希表数组下标 0 的地位上,如下图所示:

键抵触

当两个或者两个以上的计算出数组索引值统一时,就产生了 键抵触

Redis 的哈希表采纳 链表法 来解决键抵触,每个哈希表的节点都有一个 next 指针,多个哈希表节点用 next 指针组成一个单链表,被调配到同一个数组索引上的多个节点应用单向链表连接起来,这就很好的解决了 键抵触 的问题。

举个例子,程序要将一个键值对 k2v2增加到下图的哈希表中,并且计算 k2 的索引值为 2, 那么键k1k2将发生冲突:

解决抵触的方法 就是应用 next 指针将 k2k1所在的节点连接起来,如下图所示:

总结

  • 字典是一种映射的 键值对 数据结构,其中键是惟一的,通过惟一的键能够疾速找到对应的值。
  • 字典蕴含宽泛用在 Redis 数据库中。

    • 其中所有数据类型的键值对都应用字典作为底层实现。
    • Hash类型的键值对也是基于字典实现。
  • 字典的构造

    • 蕴含一个字典,蕴含依据特定类型解决的函数dictType、两个哈希表ht[2], 字典只用到了ht[0], 遇到了扩容才会应用ht[1]
    • 一个字典蕴含 两个哈希表 ,每个哈希表dictht 蕴含一个 table 数组,size记录数组的大小,sizemask等于 size-1,sizemask 和哈希值决定数据存在在 table 的地位。used记录已有的键值对。
    • 哈希表节点 dictEntry构造保留一个键值对,其中 key 保留键,V保留值,V能够是一个指针、能够是 uint64_t 整数、也能够是 int64_t 的整数。next是为了解决 键 hash 抵触,两个键的计算出的索引在数组的同一个中央,就应用next` 指针连贯在一起。
  • 新增一个键值对,首先通过调用 dict—>type->hashFunction(key) 计算 键的哈希值 , 再和dicthtsizemask做取余操作,计算失去要寄存 table 数组的索引地位。如果产生 键抵触 时,应用 链表法 将多个哈希节点通过 next 指针组成一个单链表。
  • Redis字典的实现和 Java 中的 HashMap 数据结构有以下相似的点:

    • 确定索引地位: 键首先应用哈希算法算出哈希值,再和数组的 长度 -1做取余操作,确定寄存数组的下标。
    • 解决 hash 抵触: 两个键值计算的索引统一,采纳 链表法 ,将多个节点通过next 指针连在一起。

参考

Redis 设计与实现

退出移动版