字典（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 给出了这个字典的定义：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/*
* 字典
**
每个字典使用两个哈希表，用于实现渐进式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 类型定义：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
/*
* 哈希表
*/
typedef
struct
dictht {
// 哈希表节点指针数组（俗称桶，bucket）
dictEntry **table;
// 指针数组的大小
unsigned
long
size;
// 指针数组的长度掩码，用于计算索引值
unsigned
long
sizemask;
// 哈希表现有的节点数量
unsigned
long
used;
} dictht;
|
table 属性是一个数组，数组的每个元素都是一个指向dictEntry 结构的指针。
每个dictEntry 都保存着一个键值对，以及一个指向另一个dictEntry 结构的指针：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/*
* 哈希表节点
*/
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 操作；
~~每次遇到指针，就有点头大，明天继续吧！
本文转自shayang8851CTO博客，原文链接：http://blog.51cto.com/janephp/1351687，如需转载请自行联系原作者
