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结束。