一、介绍

    字典又称为符号表、关联数组或映射，是一种保持键值对的抽象数据结构。它综合了数组和链表的优点，是这两种数据结构的折中，内置于各种高级语言。在 redis 中广泛使用，作为底层结构对数据库做增删改查等操作。

二、数据结构

字典相关数据结构：

#哈希表节点数据结构typedef struct dictEntry {         //字典的节点      void *key;      union {             //使用的联合体        void *val;          uint64_t u64;                int64_t s64;      } v;      struct dictEntry *next;      //下一个节点指针  } dictEntry;    #DictType数据结构typedef struct dictType {      unsigned int (*hashFunction)(const void *key);           //hash函数指针      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;     #哈希表数据结构typedef struct dictht {     //字典hash table      dictEntry **table;        //可以看做字典数组，俗称桶bucket      unsigned long size;          //指针数组的大小，即桶的层数      unsigned long sizemask;      unsigned long used;      //字典中当前的节点数目  } dictht;    #字典数据结构typedef struct dict {      dictType *type;      void *privdata;     //私有数据      dictht ht[2];     //两个hash table      int rehashidx;    //rehash 索引      int iterators;        //当前该字典迭代器个数  } dict;   

eg:包含三个键值对的哈希表

三、哈希算法

Redis 计算哈希值和索引值的方法如下：

#使用字典设置的hash函数，计算key的hash值hash=dict->type->hashFunction(key);  #使用hash表的sizemask 属性和哈希值，计算索引值index=hash&dict->hx[x].sizemask;   

四、哈希冲突

1、产生原因：

       当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突（Collosion）。

2、哈希冲突的解决方法：

          redis 采用链地址法解决哈希冲突。采用单链表连接哈希冲突的键值对，这样做的好处：

（1）不必要求分配连续的大片空间

（2）可以将分散的空间利用起来

使用链表解决 k1 和 k2 的冲突问题，如图所示：

3、节点的添加方法

        redis 里面采用头插法进行节点的添加，主要是从效率考虑。头插法的时间复杂度为 O(1)。

五、Rehash

1、哈希因子

         哈希因子又称为负载因子，即为哈希表的使用率。load_factor = ht[0].used/ht[0].size;

2、哈希表的收缩和扩展

         为了让哈希表的负载因子维持在一个合理的范围之内（主要是为了保证哈希表的利用率，减少空间浪费）。当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行扩展或者收缩。

3、哈希表收缩和扩展的步骤：

         1）为字典 ht[1]哈希表分配空间

               ①扩展：ht[1]>=ht[0].used*2*2^n

               ②收缩：ht[1]<=ht[0].used*2^n

         2) 将保存在 ht[0]中的所有键值对重哈希到 ht[1]上，并将键值对放到 ht[1]指定位置。

         3）当 ht[0]所有的键值对都迁移到 ht[1]后，释放 ht[0],并将 ht[1]设置为 ht[0],然后为 ht[1]创建一个空白哈希表，为下一次 rehash 做准备。

4、扩展和收缩的时机

        扩展：

               1）当前没有执行 BGSAVE 或者 BGREWRITEAOF 命令，且哈希表的负载因子大于等于 1

               2）当前正在执行 BGSAVE 或者 BGREWRITEAOF 命令，且哈希表的负载因子大于等于 5

       收缩：

              当哈希表的负载因子小于 0.1 时

5、哈希表收缩和扩展的方案

            哈希表的扩展和收缩的并不是一次性、集中式完成的，而是分多次、渐进式的完成。（主要避免对服务器性能造成影响）

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 完成。

相关图例演示：

1、渐进式 rehash-开始

2、渐进式 rehash-进行中

3、渐进式 rehash-结束