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

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

利用

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

当执行命令：

set msg "hello"

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

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

redis> HGETALL website1)"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值雷同的哈希表节点k0和k1，两者通过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，搁置如下图所示：

举个例子，要将一个键值对k0和v0增加到下方的空字典表中：

首先计算键的哈希值：

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

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

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

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

键抵触

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

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

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

解决抵触的方法就是应用next指针将k2和k1所在的节点连接起来，如下图所示：

总结

  • 字典是一种映射的键值对数据结构，其中键是惟一的，通过惟一的键能够疾速找到对应的值。

  • 字典蕴含宽泛用在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)计算键的哈希值,再和dictht的sizemask做取余操作，计算失去要寄存table数组的索引地位。如果产生键抵触时，应用链表法将多个哈希节点通过next指针组成一个单链表。

  • Redis字典的实现和Java中的HashMap数据结构有以下相似的点：

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

参考

Redis设计与实现