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

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

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

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

当执行命令：

set msg "hello"

在数据库中创立一个键为 msg，值为 hello 的键值对，这个 键值对 就用字典来实现的。创立其余数据类型的键值对，比方 list、hash、set、sort 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 值 雷同的哈希表节点 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计算哈希值和索引值的步骤如下：

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

hash = dict—>type->hashFunction(key)
应用哈希表的 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 设计与实现

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

利用

字典的实现

哈希表

哈希表节点

字典

哈希算法

键抵触

总结

参考