字典（dictionary），又名映射（map）或关联数组（associative array）， 它是一种抽象数据结

构，由一集键值对（key-value pairs）组成，各个键值对的键各不相同，程序可以将新的键值对添加到字典中，或者基于键进行查找、更新或删除等操作。

 

字典的主要用途有以下两个：

1. 实现数据库键空间（key space）

2. 用作Hash 类型键的其中一种底层实现

 

实现数据库键空间

Redis 是一个键值对数据库，数据库中的键值对就由字典保存：每个数据库都有一个与之相对应的字典，这个字典被称之为键空间（key space）。当用户添加一个键值对到数据库时（不论键值对是什么类型），程序就将该键值对添加到键空间；当用户从数据库中删除一个键值对时，程序就会将这个键值对从键空间中删除；等等。

 

用作Hash 类型键的其中一种底层实现

Redis 的Hash 类型键使用以下两种数据结构作为底层实现:1. 字典；2. 压缩列表；因为压缩列表比字典更节省内存，所以程序在创建新Hash 键时，默认使用压缩列表作为底层实现，当有需要时，程序才会将底层实现从压缩列表转换到字典。

 

字典的实现

实现字典的方法有很多种： 最简单的就是使用链表或数组，但是这种方式只适用于元素个数不多的情况下； 要兼顾高效和简单性，可以使用哈希表； 如果追求更为稳定的性能特征，并且希望高效地实现排序操作的话，则可以使用更为复杂的平衡树；在众多可能的实现中，Redis 选择了高效且实现简单的哈希表作为字典的底层实现。dict.h/dict 给出了这个字典的定义：

/** 字典**每个字典使用两个哈希表，用于实现渐进式rehash ，即哈希表扩容*/typedef struct dict {// 特定于类型的处理函数dictType *type;// 类型处理函数的私有数据void *privdata;// 哈希表（2 个）dictht ht[2];// 记录rehash 进度的标志，值为-1 表示rehash 未进行int rehashidx;// 当前正在运作的安全迭代器数量int iterators;} dict;

注意dict 类型使用了两个指针分别指向两个哈希表。

其中，0 号哈希表（ht[0]）是字典主要使用的哈希表，而1 号哈希表（ht[1]）则只有在程序对0 号哈希表进行rehash 时才使用。

哈希表实现

字典所使用的哈希表实现由dict.h/dictht 类型定义：

/** 哈希表*/typedef struct dictht {// 哈希表节点指针数组（俗称桶，bucket）dictEntry **table;// 指针数组的大小unsigned long size;// 指针数组的长度掩码，用于计算索引值unsigned long sizemask;// 哈希表现有的节点数量unsigned long used;} dictht;

table 属性是一个数组，数组的每个元素都是一个指向dictEntry 结构的指针。

每个dictEntry 都保存着一个键值对，以及一个指向另一个dictEntry 结构的指针：

/** 哈希表节点*/typedef struct dictEntry {// 键void *key;// 值union {void *val;uint64_t u64;int64_t s64;} v;// 链往后继节点struct dictEntry *next;} dictEntry;

next 属性指向另一个dictEntry 结构，多个dictEntry 可以通过next 指针串连成链表，从

这里可以看出，dictht 使用链地址法来处理键碰撞：当多个不同的键拥有相同的哈希值时，哈希表用一个链表将这些键连接起来。下图展示了一个由dictht 和数个dictEntry 组成的哈希表例子：

如果再加上之前列出的dict 类型，那么整个字典结构可以表示如下：

在上图的字典示例中，字典虽然创建了两个哈希表，但正在使用的只有0 号哈希表，这说明字

典未进行rehash 状态。

 

创建新字典

新创建的两个哈希表都没有为table 属性分配任何空间：

 ht[0]->table 的空间分配将在第一次往字典添加键值对时进行； ht[1]->table 的空间分配将在rehash 开始时进行；

 

添加键值对到字典

根据字典所处的状态，将一个给定的键值对添加到字典可能会引起一系列复杂的操作： 如果字典为未初始化（也即是字典的0 号哈希表的table 属性为空），那么程序需要对0号哈希表进行初始化； 如果在插入时发生了键碰撞，那么程序需要处理碰撞； 如果插入新元素使得字典满足了rehash 条件，那么需要启动相应的rehash 程序；当程序处理完以上三种情况之后，新的键值对才会被真正地添加到字典上。整个添加流程可以用下图表示：

在接下来的三节中，我们将分别看到添加操作如何在以下三种情况中执行：

1. 字典为空;2. 添加新键值对时发生碰撞处理；3. 添加新键值对时触发了rehash 操作；

 

~~每次遇到指针，就有点头大，明天继续吧！