Redis系列——10.字典结构

前言

大年初五送财神，emmm，希望今年暴富，每年都是这么单纯简单的小愿望，没有一次让我实现的。

年会一个奖都没抽到，emmmm，我很好。

so，还是自己动手，丰衣足食。今天学习redis中的字典。

结构介绍

字典，C语言中没有内置这种数据结构，所以redis自己构建了实现。

hash类型的数据底层就是字典。

哈希表：

typedef struct dictht {
    //存放一个数组的地址，数组存放着哈希表节点dictEntry的地址。
    dictEntry **table;     
    //哈希表table的大小，初始化大小为4
    unsigned long size;     
    //用于将哈希值映射到table的位置索引。它的值总是等于(size-1)。
    unsigned long sizemask; 
    //记录哈希表已有的节点（键值对）数量。
    unsigned long used;     
} dictht;

哈希节点：

typedef struct dictEntry { 
     void *key; //key
     union { 
       void *val; 
       uint64_t u64; 
       int64_t s64;       double d;
     } v; //value 
     //指向下一个hash节点，用来解决hash键冲突（collision）
     struct dictEntry *next;
   } dictEntry;

字典：

typedef struct dict { 
      //指向dictType结构，dictType结构中包含自定义的函数，
      //这些函数使得key和value能够存储任何类型的数据。
       dictType *type; 
      //私有数据，保存着dictType结构中函数的参数。
       void *privdata; 
      //两张哈希表。
       dictht ht[2]; 
      //rehash的标记，rehashidx==-1，表示没在进行rehash  
       long rehashidx; 
      //正在迭代的迭代器数量 
       int iterators; 
   } dict;

上面代码整个结构图如下：

注意：这边ht是一个数组，ht[1]为空，是用来进行散列的。

解决冲突

在解决冲突之前，我们先看（k0，v0）为什么会存在下标为1的位置？

这其实是哈希算法，先计算hash值（hash=dict->type->hashFunction(key)），再计算索引值（index=hash&dict->ht[x].sizemask。

那如果再有一个（k2，v2），他的索引值也是下标为1，那就会出现两个值在同一位置的情况。这就是冲突啦。

redis的哈希表采用链地址法来解决键冲突，上面的整个结构图中的哈希节点dictEntry有一个next指针，他是指向下一个节点的。

最新的节点添加到链表的表头位置，这样是为了速度考虑。

重新散列

随着操作的不断进行，哈希表保存的键值对会逐渐的增多或减少，为让哈希表的负载因子（used/size）保持在一个合理的范围内，哈希表会进行扩展和收缩。

简单来说，比如我们现在有10个空间，但是我数据量有30个，这已经平均每个空间都有链表，且链表长度为3。如果极限考虑，这30个数据都在同一节点，那链表长度太长，查询，更新，删除都慢（这里不说新增，是因为每次新增的节点都在表头，与长度无关）。这效率贼慢啊。我们是不是要扩展空间。

再比如我们现在有10个空间，数据量只有1个，这是不是太浪费空间了。我们是不是要收缩空间，等数据量大的时候，我们再扩展嘛。

那扩展和收缩的条件是什么呢？

首先是扩展，没有执行bgsave命令时，负载因子大于等于1；执行bgsave命令时，负载因子大于等于4。

这边重点说明下区分bgsave命令的原因。因为在执行bgsave命令时，需要创建子进程，所以要提高负载因子，避免在子进程执行期间进行扩展，避免不必要的内存写入操作，最大限度的节约内存。

其次是收缩，负载因子小于0.1。

扩展和收缩的步骤如下：

1.确定ht[1]的分配空间。（在重新散列之前，数据都是放在ht[0]中的，ht[1]为空。）

扩展：第一个大于等于ht[0].used*2的2的n次方

收缩：第一个大于等于ht[0].used的2的n次方

2.将ht[0]的键值重新散列到ht[1]中。

3.将ht[1]改为ht[0]，ht[1]新建一个空白哈希。

渐进式散列

扩展和收缩都需要将ht[0]里面的所有键值对散列到ht[1]中，但是这个动作并不是一次性完成的，而是分多次，渐进式完成的。

这么做的原因在于，如果ht[0]如果只保存了四个键值对，那么服务器可以在瞬间完成，但是如果里面保存的是四百万，四千万的键值对，那么一次性将这些键值对全部散列到ht[1]中，这个计算量还是很庞大的。

因此，为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]里面的所有键值对全部散列到ht[1]中，而是分多次，渐进式慢慢的散列。

步骤如下：

1.为ht[1]分配空间。

2.在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。

3.rehash过程中，逐渐将rehashidx加1。

4.rehash结束，将reshidx属性的值设为-1，表示rehash工作已完成。

注意：

如果在重新散列的过程中，还有对该hash的操作，就要分情况啦。

1.如果是新增操作，就将数据添加到ht[1]中。

2.如果是查询，更新，删除等操作，就会ht[0],ht[1]都要查，因为并不知道这条数据现在在哪个数组里面。

这样可以做到ht[0]只增不减，直到整个操作完成。

恩恩，到这里就结束啦，明天见（虽然偶也不知道明天能不能更）。