redis实现之字典

大耗子 2021年01月23日 47次浏览

字典

  • 在不进行rehash的时候,使用的是ht[0],进行rehash的时候,ht[0]和ht[1]一起使用。
typedef struct dict {
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2]; 
    // rehash索引
    //当rehash不在进行时, 值为-1
    in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

redis字典

哈希表结构

  • Redis字段所使用的的哈希表有idct.h/dictht结构定义:
typedef struct dictht {
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码, 用于计算索引值
    //总是等于size-1
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
} dictht;

哈希表节点

  • 哈希表节点使用dictEntry结构表示,每个dictEntry结构都保存着一个键值对:
typedef struct dictEntry {
    //键
    void *key;
    //值
    union{
    	void *val;
        uint64_tu64;
        int64_ts64;
    } v;
    //指向下个哈希表节点, 形成链表
    struct dictEntry *next;
} dictEntry;

字典存储函数指针的函数

用来存储特定类型键值对处理的函数,redis会为不同用途的字典设置不同的特定函数。

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;

哈希算法

  • 当要将一个新的键值对添加到字典里面时, 程序需要先根据键值对的键计算出哈希值和索引值, 然后再根据索引值, 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
  • Redis计算哈希值和索引值的方法如下:
hash = dict->type->hashFunction(key);
index = hash & dict->ht[x].sizemask; // x可以为1或0

解决键冲突

  • 如果有两个或两个以上的键被分配到同一个索引上的时候,我们称这些键发生了冲突
  • 在redis中通过使用指针的方式,将冲突的键通过链表的方式,将冲突的键连接起来。也就是dictEntry结构中的next成员。
  • 并且为了插入的快速,会通过头插法插入链表。

哈希表的收缩与扩张

哈希表的负载因子公式:

#负载因子=哈希表已保存节点数量/哈希表大小
load_factor = ht[0].used / ht[0].size

扩张触发条件:

  1. 服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令, 并且哈希表的负载因子大于等于1。
  2. 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令, 并且哈希表的负载因子大于等于5。
    注:此处负载因为为5才触发,是因为redis执行BGSAVE命令或者BGREWRITEAOF命令是创建服务器的子进程来进行操作的,此时如果轻易对哈希表继续扩张,会造成写时复制,浪费内存。

收缩触发条件:

  1. 负载因子小于0.1的时候,程序自定开始对哈希表执行收缩操作。

rehash操作

  • 重新建立哈希表的时候,如果键值比较多,要一次性转移所有的键值到另一个哈希表,时间一定会非常的多,影响效率,甚至导致服务停滞,所以redis中涉及的rehash动作并不是一次性、集中式的,而是分多次、渐进式的完成的。

rehash详细步骤

  1. 为ht[1]分配空间, 让字典同时持有ht[0]和ht[1]两个哈希表。
  2. 在字典中维持一个索引计数器变量rehashidx, 并将它的值设置为0, 表示rehash工作正式开始。
  3. 在rehash进行期间, 每次对字典执行添加、 删除、 查找或者更新操作时, 程序除了执行指定的操作以外, 还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当rehash工作完成之后, 程序将rehashidx属性的值增一。
  4. 随着字典操作的不断执行, 最终在某个时间点上, ht[0]的所有键值对都会被rehash至ht[1], 这时程序将rehashidx属性的值设为-1, 表示rehash操作已完成。

注:渐进式rehash的好处在于它采取分而治之的方式, 将rehash键值对所需的计算工作均摊到对字典的每个添加、 删除、 查找和更新操作上, 从而避免了集中式rehash而带来的庞大计算量。

在rehash期间操作哈希表如何取值?

在rehash的时候,由于数据存在与ht[0]和ht[1]中,所以操作会在这两个表中进行。

  1. 要查找一个键,程序会先去ht[0]中找,然后再去ht[1]中查找。
  2. 要添加一个键,程序会添加到ht[1]中。