Redis03-Redis的数据结构之字典

前言

周末被社会的皮鞭狠狠的抽打了几下。人微言轻，为生计奔波，劳碌一生。富则妻妾成群，穷则孤独一生。个人牢骚。今天接着来学习Redis的第三篇，字典的数据结构。字典的数据结构其实完全可以类比Java中的HashMap数据结构，两者都是哈希表。

字典

简介说明

字典，又称为符号表 ，关联数组或映射。是一种用于保存键值对（key-value pair）的抽象数据结构。字典中的每个键都是唯一的，通过键来更新值，或者根据键来删除整个键值对等等。字典在Redis中的应用相当广泛，比如Redis的数据库就是使用字典作为底层实现的。对数据库的增、删、查、改操作也是构建在对字典的操作之上的。

字典的实现

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以用多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

哈希表

哈希表的数据结构定义如下：

typedef struct dictht
{
         //哈希表数组，C语言中，*号是为了表明该变量为指针，有几个* 号就相当于是几级指针，这里是二级指针，理解为指向指针的指针
         dictEntry **table;
         //哈希表大小
         unsigned long size;
         //哈希表大小掩码，用于计算索引值
         unsigned long sizemask;
         //该哈希已有节点的数量
         unsigned long used;
}dictht;

1. table属性是一个数组，数组中的每个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对，
2. size属性记录了哈希表的大小，也即table数组的大小。
3. used属性则记录哈希表目前已有节点（键值对）的数量。
4. sizemask属性的值总是等于size-1（从0开始）,这个属性和哈希值一起决定一个键应该被放在table数组的那个索引上面。
   下图表示一个空的哈希表的结构图
   

哈希表节点

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对。

typedef struct dictEntry
{
         //键
         void *key;
         //值
         union{
           void *val;
            uint64_tu64;
            int64_ts64;
            }v;
         // 指向下个哈希表节点，形成链表
         struct dictEntry *next;
}dictEntry;

key属性保存着键值中的键，而v属性则保存着键值对中的值，键值（v属性）可以是一个指针，或uint64_t整数，或int64_t整数。next属性是指向另一个哈希表节点的指针，可以将多个哈希值相同的键值对连接在一起。以此来解决键冲突的问题。

字典

Redis中的字典由dict.h/dict 结构表示：

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

type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的。
type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数。Redis会为用途不同的字典设置不同的类型特定函数。
privdata属性则保存了需要传给那些类型特定函数的可选参数。

typedef struct dictType
{
         //计算哈希值的函数 
         unsigned int  (*hashFunction) (const void *key);
         //复制键的函数
         void *(*keyDup) (void *privdata,const void *key);
         //复制值的函数
         void *(*keyDup) (void *privdata,const void *obj);
          //复制值的函数
         void *(*keyCompare) (void *privdata,const void *key1, const void *key2);
         //销毁键的函数
         void (*keyDestructor) (void *privdata, void *key);
         //销毁值的函数
         void (*keyDestructor) (void *privdata, void *obj);
}dictType;

ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，数组中的每个项都是一个dictht哈希表，情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会对ht[0]哈希表进行rehash时使用。
rehashidx记录了rehash目前的进度，如果目前没有进行rehash，值为-1。

哈希算法

当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放在哈希表数组的指定索引上面。
Redis计算哈希值和索引值的方法如下：

#使用字典设置的哈希函数，计算键key的哈希值
hash=dict->type->hashFunction(key);
#使用哈希表的sizemask属性，计算出索引值
#根据情况不同，ht[x]可以是ht[0]或者ht[1]
index=hash&dict->ht[x].sizemask;

当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。

解决键冲突(链表法)

当有两个或者以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突的。
Redis使用链表法解决哈希冲突，每个哈希表节点都有一个next指针，多个哈希表节点next可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以使用这个单向链表连接起来。如下图所示：

如图所示，当键k0和k1经过哈希函数得到的索引值都是1时，就会使用next指针将连个节点（使用节点的好处是不需要辅助变量去获得链表的长度信息)连接起来。而由于节点没有指向链尾的指针，因此新的节点总是插入到链表的头部，排在已有节点的前面。

Redis rehash

随着操作的进行，哈希表中保存的键值对会逐渐的增多或者减少，程序需要对哈希表的大小进行相应的扩展或者收缩。
扩展和收缩哈希表的工作可以通过执行rehash(重新散列)来完成，Redis对字典的哈希表执行rehash的步骤如下：

1. 为字典的ht[1]哈希表分配空间，哈希表大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht[0].used属性的值）
   如果，执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂。
   如果执行的是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂。
2. 将保存在ht[0]中的所有键值对rehash到ht[1]上面；rehash指的是重新计算键的哈希值和索引值。然后将键值对放置到ht[1]哈希表的指定位置上。
3. 当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表）释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。

总结

本文简单的介绍了Redis中的字典的数据结构， 她是通过哈希表节点来存储键值信息，通过链表法来处理键冲突。

参考

https://www.cnblogs.com/hunternet/p/9989771.html
《Redis设计与实现》