Redis的设计与实现 字典

一 字典的概念

字典是一种保存键值对的抽象数据结构，在许多语言中都有使用，C语言并没有内置，所以Redis构建了自己的字典实现

127.0.0.1:6379> set msg "hellow yanglele"
OK

这个msg键和"hellow yanglele"值就是保存在代表数据库的字典里面，除了用来表示数据库，字典还是哈希键的底层实现，如果哈希键包含的键值对比较多，或者键值对中的元素都是比较长的字符串时，redis会使用字典作为hash键的底层实现

二 字典的实现

1. 哈希表

   数据结构

   typedef stuct dictht {
       // 哈希表数组
       dictEntry **table；
   
       // 哈希表大小
       unsigned long size；
   
       // 哈希表大小掩码，用来计算索引值
       // 总是等于size-1
       unsigned long sizeremark;
   
       // 该hash表已有节点的数量
   }

2. 哈希表节点

   typedef stuct dictEntry {
   
      //键
      void *key;
   
      //值
      union{
          void *val;
          unit64_t u64;
          int64_t s64;
      } v;
   
      //指向下一个hash表节点，形成链表
   
   } dictEntry；
   

   next可以将多个hash值相同的键连接在一起，从而解决hash冲突。

3. 字典

   • 数据结构

     typedef struct dict {

     //类型特定函数
     dictType *type;;
     
     //私有数据
     void *privdata；
     
     // 哈希表
     dictht ht[2]
     
     // rehash索引
     // 当rehash不再进行时，值为-1
     int trehashindex

     } dict；

  `type`属性是为多态字典而设定的，里面包含hash值的一些函数，比如计算索引的函数，`dictht` ht[2]中包含两个数组，ht[0],和ht[1],ht[1]是对ht[0]进行rehash操作的，当rehash结束后，ht[1]就会变成ht[0];

• 解决冲突

  如果学习过java的`HashMap`，那么就会很容易理解`redis`是怎么解决的，因为他们大概是一致的，首先通过key的hash来取的索引位置，但是索引位置可能会冲突，这时候就使用链表来解决，与HashMap一致，他们都是单项的链表，如果产生冲突，就在链表中添加元素
  

  • rehash

    这个就是前面说的，ht0与ht1，不做描述

• 渐进式rehash

   如果值太大了，一次性移不动，怎么办，redis的解决方案就是渐进式hash，也就是一点一点移，然后通过`trehashindex`属性来看移动的进度。