Redis 数据结构：字典

前言

字典有多种叫法。可以叫
“符号表”
，
“关联数组”
以及
“映射”
。字典主要存储的是
键值对
。键值对的
键必须唯一
。其中Redis的
数据库
和
哈希键
的底层实现就是字典。

由于Redis的字典使用了散列表(哈希表)作为底层实现，下面先了解一下什么是
散列表
。

一、什么是散列表（哈希表）

学习了数据结构我们应该知道，
顺序存储结构
的底层存储位置是
一块连续
的
存储空间
。想要查找某元素，通常是采用循环法逐个对比。如果元素比较多，查询效率就会很低。

那么有没有一种办法不需要循环，也不需要对比，根据关键词直接定位查询呢？
通常我们查看通讯录，并不会从上到下逐个寻找，而是通过姓名的拼音（关键词）就可以直接定位到手机号码。咦~ 没错，这样的设计方式，正是我们所需要的。散列技术的思想就类似于这种形式。

散列技术
就是在记录的
存储位置
和它的
关键词
之间建立了确定的
对应关系
F
(function) , 每一个
关键词
都有对应
位置 
(key)，通过位置找到值 (value)。

这种关系F 称作为
散列函数
或
哈希函数
，采用散列技术将记录存储在了
一块连续
的
存储空间
中，这块连续的存储空间就被称为
散列表
或
哈希表
。

举个例子，想要通过散列技术存储手机号码信息。

分析：上图例子，哈希函数通过拿取手机号码后四位（这四位是比较有意义的关键词）作为哈希地址（key）。这个哈希地址（key）就是该手机号码所存储位置的键，而值就是手机号码。如右侧的绿色部分的键，是通过哈希函数处理所得。

#一个简单哈希函数（截取后四位作为哈希键）

int Hash(string key) {

  #截取后四位字符

  return hashValue =key.Substring(key.Length-4);

}

哈希函数可以参考以下两个原则去实现。毕竟函数复杂会影响创建和查询的效率。

• 计算简单
• 散列地址分布均匀

常规的哈希函数有以下几种构造方法：

• 直接地址法

• 数字分析法

• 平方取中法

• 折叠法

• 除留余数法

• 随机数法

二、散列冲突的解决方式

尽管再好的哈希函数，也很难避免键冲突的现实。仍然是基于上面的例子， 假设手机号后四位的数字有两条相同的，通过哈希算法算出的（key）自然也是相同的，那如果键冲突了应该怎么解决呢？可采用以下四种方式。

2.1 开放定址法

开放定址法就是，对一个key进行哈希，发现算出来的这个地址已经被占用了。此时，从当前位置逐个向下寻找未被使用的地址，如果找到最后还是没有找到空余位置，则重头开始找，直到找到空余位置为止。缺点是找位置和查询时都会很耗时间。

分析：如上图所示，红色箭头的关键词，和哈希表地址为3的键发生了键冲突，此时从当前位置向下逐个找未被使用的地址。直到遇到未被使用的地址才将数据存储进去。如果哈希表找到底部，仍旧没有找到未被使用的位置。则重头再开始找位置。此时，找位置和后期查询的时间复杂度O(n)。
2.2 链地址法 
当发生键冲突的时候，会有2个或2个以上的值使用同一个地址。此时将这个地址指向一个链表地址，并由链表去存储具体的值。缺点是查找时需要遍历链表的时间。

分析：如上图所示，红色箭头所指向的200003 和 200002 通过哈希函数算出的哈希地址，和哈希表中的键发生了冲突。

通过
链地址法
解决键冲突的做法是，将哈希表的键，指向链表的第一个头结点地址。这样每次有新的键发生了冲突，都将这个值放入链表的表头结点，再由链表的表头结点指向已有的链表的第一个头元素。

链式法的缺点是，每次查询元素时，一旦发现键指向的是链表的地址，则需要遍历链表中的元素，此时的查询时间复杂度是O(n)。

2.3 再散列函数法

首先是提供多个散列函数，当发生键冲突的时候，我们可以使用关键词，换一个散列函数重新计算位置，直到计算出的位置没有被使用过。缺点是增加了计算时间。

2.4 公共溢出区法
首先建立一个公共溢出区，当发生键冲突的时候，将这些冲突的键放到公共溢出区表中存储。

分析：如上图所示，在查找的时候，首先根据哈希算法获得该元素的哈希地址后，在通过哈希地址从哈希表中获取元素，获取时间是O(1)，如果相等则查找成功。如果不相等，则到溢出表中进行顺序查找。时间复杂度是O(n)。
三、散列表查找性能分析
在最理想的状态下，散列表不发生键冲突，一个好的哈希函数可以尽可能的避免或减少键冲突的存在。在不发生键冲突的时候，散列表的查询时间复杂度是O(1) 因为散列表也是基于数组的，查询速度非常快。回归于现实，键往往是会发生冲突的，那么怎么检测一个散列表的是否会频繁出现键冲突的状态呢？

3.1 散列表的装载因子和Rehash

装载因子a = 提入表中的记录个数/散列表长度

a 标志着散列表的装满程度。当填入表的记录越多，a 就越大，产生冲突的可能性就会越高。如果 a 太小，则会产生内存空间的不合理使用，造成内存空间的浪费。
所以我们可以控制装载因子的大小，限定在一个区间范围之内，才可以尽可能的将查询时间复杂度达到O(1)。为了做到这一点，我们可以采用空间换时间的做法。也可以根据散列表进行收缩空间即rehash，进而改变散列表的大小。
四、Redis中的字典结构

Redis中的
字典
是采用了
哈希表
作为底层实现，一个哈希表里面可以有多个
哈希结点
，而每个哈希结点就保存了字典中的一个
键值对
。下图是一个完整的普通状态下的字典。

1）依据上图，从左到右分析结构，首先看最左边字典的结构。
redis中的字典由 dict.h/dict 结构表示：

typedef struct dict {

    # 类型特定函数

    dictTyepe *type

    # 私有数据

    void *privdata;

    # 哈希表

    dictht ht[2];

    # rehash 索引

    # 当rehash 不在进行时 值为 -1

    int trehashidx;

}dict;

• type 属性
  是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，redis会根据不同用处的字典设置不同的函数类型。

• privdata 属性
  则保存了需要传那些类型特定函数的可选参数。

• ht 属性
  是一个包含两个项的数组，每个项都是一个dictht哈希表。一般情况下字典只使用 ht[0] 哈希表。而 ht[1] 哈希表只会对 ht[0] 哈希表进行rehash时使用。

• trehashidx 属性
  是结合与 ht[1] 来使用的，当没有存在rehash的时候其值为 -1。

2）再看一下散列表的结构：redis中的字典所使用的散列表由 dict.h/dictht 结构定义

typedef struct dictht {

    # 哈希表数组

    dictEntry **table;

    # 哈希表大小

    unsigned long size;

    # 哈希表大小掩码，用于计算索引值

    # 总是等于 size-1

    unsigned long sizemask;

    # 该哈希表已有结点的数量

    unsigned long used;

}

可以设想一下，一个散列表就是一个数组，有大小，有总数量，还有一个索引值。

• table 属性
  是一个数组，数组中的每个元素都是一个指向 dict.h/dictEntry结构的指针。每个dictEntry结构存在一个键值对。

• size 属性
  记录了散列表的大小，也是table数组的大小。

• sizemask 属性
  的值总是等于size-1，这个属性和哈希值一起决定一个键应该放到数组的哪个索引上面。

• used 属性
  记录了散列表已有数据（键值对）的数量。

3）再看一下哈希表结点的结构：哈希表结点使用dictEntry结构表示。每一个dictEntry结构都保存着一个键值对

typedef struct dictEntry {

    # 键

    void *key;

    # 值

    union {

        void *val;

        uint64_t u64;

        int64_t s64;

    }v;

    # 指向下个哈希表结点，形成链表

    struct dictEntry *next;

}dictEntry;

• key 属性
  保存着键值对的键。

• v 属性
  则保存着键值对中的值。其中键值对的值可以是一个指针又或者是一个整数。

• next 属性
  是指向另一个哈希表结点的指针，这个指针用于解决键冲突的，将多个相同键的值链接在一起形成一个链表。

五、Redis中的解决键冲突

经过上文的学习，我们已经知道，Redis中的字典底层是由哈希表来实现的。如果想要将一个键值对添加到字典中去。首先需要通过哈希算法获得一个哈希键，通过这个哈希键的位置来储存这个键值对。既然使用了哈希算法，就避免不了键冲突的存在，那么在Redis中又是如果解决键冲突的问题呢？

当有两个或以上的键被分配到同一个哈希表的同一个索引上，则称为
键冲突
。在 redis 中哈希表使用了
链地址法
来解决键冲突。通过哈希表中的
next 指针
指向一个
单向链表
。被分配到同一个索引上的值则存储在这个链表里面。从而解决了哈希键冲突的问题。

5.1 Redis中的 rehash

通过上文中学习到，想要让哈希表的负载因子维持在一个合理的范围之内，需要对哈希表进行收缩或扩容。这个工作就交给了rehash (重新散列) 来完成。在redis中对字典的哈希表操作执行rehash的步骤如下：
1）为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作。以及 ht[0] 当前包含的键值对的数量

• 如果执行的是扩展操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2的n次方幂。

• 如果执行的是收缩操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的大小。

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做准备。

举个例子如下图所示：

分析上图，上图的主要目的是将ht[0]哈希表的所有键值对rehash到 ht[1] 哈希表中去。

因为ht[0] 的哈希表大小为4，目前已经存储满了，需要扩容到2的次方幂升级到大小为8空间。所以需要rehash扩容。

首先，从图中最左侧的字典中可以看到，rehashidx 从原本的 -1 已经变成了 2。这个是因为 rehash 索引 会从 -1 逐个变成 0、1、2、3 直到变成sizemask的大小为止，则认为rehash结束了。而目前 rehashidx 为 2 则说明，ht[0] 哈希表中还有一个键值对待rehash到 ht[1] 中去。
因为 ht[0] 中有4个元素，所以如果rehashidx 为 3 的时候则认为rehash 结束了，此时需要将  ht[1] 设置为 ht[0] 并重新建立一个 ht[1] 的空哈希表。此时rehash结束。

5.2 Redis中的 渐进式rehash

通过上文中的rehash，我们已经知道rehash的基本流程。其实这个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] ，此时rehash工作结束。程序在将 rehashidx 属性的值设置为-1。

六、总结

本章主要讲解了redis中字典的数据结构。同时学习了《大话数据结构》中的hash表的相关知识。从而对redis中的字典底层实现的哈希表有了一个更清楚的认识。这样在学习的时候贯穿疏通会更好理解，基于图文的形式更容易去记忆。

redis中的字典数据结构底层是由哈希实现的。一个字典中维护了两个哈希表，一个作为存储键值对，另一个用作rehash的备用空间。

其中哈希表是由一块连续的存储空间实现的，redis中的哈希表，如果遇到了键冲突则使用链式法的一个链表去解决键冲突的问题。

对于链表的收缩或扩容问题，采用的是装载因子的值去决定的，通过装载因子值的大小进行决定收缩或扩容。无论做哪种 rehash 都是采用渐进式的方式操作。

七、参考文献

《redis 设计与实现》
《大话数据结构》