字典在Redis中应用十分广泛，它是实现数据库的基础，特别的它是数据库键空间的实现方式，因此非常必要研究透彻字典的构建。

1、散列方法

也就是hash方法。

思想：

根据节点的关键码值确定存储地址。

核心：

散列函数。

原理：

对于任意给定的查找表 DL，选定“理想”的散列函数 h 及相应的散列表 HT ，则对于 DL 中每个元素 X ，函数值 h(X.key) 为 X 在 HT 中的存储位置。

首要问题：

• 如何构造使节点“分布均匀”的散列函数
• 一旦发生冲突，用什么方法解决（开散列法、闭散列法）

下面看一下两个经典的散列函数：

djb2

this algorithm (k=33) was first reported by dan bernstein many years ago in comp.lang.c. another version of this algorithm (now favored by bernstein) uses xor: hash(i) = hash(i - 1) * 33 ^ str[i]; the magic of number 33 (why it works better than many other constants, prime or not) has never been adequately explained.

    unsigned long
    hash(unsigned char *str)
    {
        unsigned long hash = 5381;
        int c;

        while (c = *str++)
            hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

        return hash;
    }

Murmurhasher

当前的版本是 MurmurHash3 ，能够产生出32-bit或128-bit哈希值。

较早的 MurmurHash2 能产生 32-bit 或 64-bit 哈希值。对于大端存储和强制对齐的硬件环境有一个较慢的 MurmurHash2 可以用。MurmurHash2A 变种增加了Merkle–Damg?rd 构造，所以能够以增量方式调用。 

有两个变种产生64-bit哈希值：MurmurHash64A，为64位处理器做了优化；MurmurHash64B，为32位处理器做了优化。MurmurHash2-160用于产生160-bit 哈希值，而 MurmurHash1 已经不再使用。

Murmur3_32(key, len, seed)
    c1  0xcc9e2d51
    c2  0x1b873593
    r1  15
    r2  13
    m  5
    n  0xe6546b64
 
    hash  seed

    for each fourByteChunk of key
        k  fourByteChunk

        k  k * c1
        k  (k << r1) OR (k >> (32-r1))
        k  k * c2

        hash  hash XOR k
        hash  (hash << r2) OR (hash >> (32-r2))
        hash  hash * m + n

    with any remainingBytesInKey
        remainingBytes  SwapEndianOrderOf(remainingBytesInKey)
        remainingBytes  remainingBytes * c1
        remainingBytes  (remainingBytes << r1) OR (remainingBytes >> (32 - r1))
        remainingBytes  remainingBytes * c2

        hash  hash XOR remainingBytes
 
    hash  hash XOR len

    hash  hash XOR (hash >> 16)
    hash  hash * 0x85ebca6b
    hash  hash XOR (hash >> 13)
    hash  hash * 0xc2b2ae35
    hash  hash XOR (hash >> 16)

2、字典的实现

Redis选择高效、实现简单的哈希表作为字典的底层实现。

dict.h给出了字典的定义：

/*
 * 字典
 *
 * 每个字典使用两个哈希表，用于实现渐进式 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 时使用的。

哈希表的定义如下：

/*
 * 哈希表
 */
typedef struct dictht {

    // 哈希表节点指针数组（俗称桶，bucket）
    dictEntry **table;      

    // 指针数组的大小
    unsigned long size;     

    // 指针数组的长度掩码，用于计算索引值
    unsigned long sizemask; 

    // 哈希表现有的节点数量
    unsigned long used;     

} dictht;

/*
 * 哈希表节点
 */
typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 链往后继节点
    struct dictEntry *next; 

} dictEntry;

3、创建新字典

dict.c 中给出了创建字典的方法 dictCreate

/*
 * 创建一个新字典
 *
 * T = O(1)
 */
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    // 分配空间
    dict *d = zmalloc(sizeof(*d));

    // 初始化字典
    _dictInit(d,type,privDataPtr);

    return d;
}

/*
 * 初始化字典
 *
 * T = O(1)
 */
int _dictInit(dict *d, dictType *type,
        void *privDataPtr)
{
    // 初始化 ht[0]
    _dictReset(&d->ht[0]);

    // 初始化 ht[1]
    _dictReset(&d->ht[1]);

    // 初始化字典属性
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = -1;
    d->iterators = 0;

    return DICT_OK;
}

/*
 * 重置哈希表的各项属性
 *
 * T = O(1)
 */
static void _dictReset(dictht *ht)
{
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

dict *d = dictCreate(&hash_type, NULL);

其中 ht[0]->table 空间分配将在第一次往字典添加键值时进行

 ht[1]->table 空间分配将在 rehash 时进行

4、添加键值对到字典

键值对的添加在 Redis 实现时，是很重要的一部，涉及到效率问题。

情况也比较复杂，需要进行讨论：

• 字典未初始化，即 0 哈希表的 table 为空，则需要对其初始化
• 在插入时发生键碰撞，程序需要处理碰撞
• 插入新元素，使字典满足 rehash 条件，则需要启动相应 rehash 程序

4.1 添加新元素到空白字典

// 所有哈希表的起始大小
#define DICT_HT_INITIAL_SIZE     4

如下所示是一个空字典：

添加一个键值对以后如下所示：

4.2 碰撞处理

在哈希表实现中，当两个不同的键拥有相同的哈希值时，称这两个键发生碰撞(collision)，哈希表实现必须想办法对碰撞进行处理。
字典哈希表所使用的碰撞解决方法被称之为链地址法： 这种方法使用链表将多个哈希值相同的节点串连在一起。
假设现在有一个带有三个节点的哈希表，如下图：

对一个新的键值对 key4 和 value4 ，如果 key4 的哈希值和 key1 的哈希值相同，那么它们将在哈希表的 0 号索引上发生碰撞。
通过将 key4-value4 和 key1-value1 两个键值对用链表连接起来， 就可以解决碰撞的问题：

4.3 添加新键值对时触发 rehash

链地址法实现的碰撞问题，会影响哈希表的性能，而性能主要取决于大小（size属性）与保存节点数量（used属性）之间的比率：

• 哈希表的大小与节点数量，比率在 1:1 时，哈希表的性能最好
• 如果节点数量比哈希表的大小要大很多的话，那么哈希表就会退化成多个链表，哈希表本身的性能优势便不复存在

 下面这个哈希表， 平均每次失败查找只需要访问 1 个节点（非空节点访问 2 次，空节点访问 1 次）：

下面这个哈希表，平均每次失败查询需要访问5个节点：

为了在字典的键值对不断增多的情况下保持良好的性能， 字典需要对所使用的哈希表（ht[0]）进行 rehash 操作： 

在不修改任何键值对的情况下，对哈希表进行扩容， 尽量将比率维持在 1:1 左右。

dictAdd 在每次向字典添加新键值对之前， 都会对哈希表 ht[0] 进行检查， 对于 ht[0] 的 size 和 used 属性， 如果它们之间的比率 ratio = used / size 满足以下任何一个条件的话，rehash 过程就会被激活：

• 自然 rehash ： ratio >= 1 ，且变量 dict_can_resize 为真
• 强制 rehash ： ratio 大于变量 dict_force_resize_ratio

5、Rehash 执行过程

字典的 rehash 操作实际上就是执行以下任务：

• 创建一个比 ht[0]->table 更大的 ht[1]->table ；
• 将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ；
• 将原有 ht[0] 的数据清空，并将 ht[1] 替换为新的 ht[0] ；

5.1 开始 rehash

• 设置字典的 rehashidx 为 0 ，标识着 rehash 的开始；
• 为 ht[1]->table 分配空间，大小至少为 ht[0]->used 的两倍；

5.2 rehash 进行时

在这个阶段， ht[0]->table 的节点会被逐渐迁移到 ht[1]->table ， 因为 rehash 是分多次进行的，字典的 rehashidx 变量会记录 rehash 进行到 ht[0] 的哪个索引位置上。

以下是 rehashidx 值为 2 时，字典的样子：

5.3 节点迁移完毕

5.4 rehash 完毕

• 释放 ht[0] 的空间；
• 用 ht[1] 来代替 ht[0] ，使原来的 ht[1] 成为新的 ht[0] ；
• 创建一个新的空哈希表，并将它设置为 ht[1] ；
• 将字典的 rehashidx 属性设置为 -1 ，标识 rehash 已停止；

5.5 渐进式 rehash

rehash 程序并不是在激活之后，就马上执行直到完成的，而是分多次、渐进式地完成的。

假设这样一个场景：在一个有很多键值对的字典里，某个用户在添加新键值对时触发了 rehash 过程，如果这个 rehash 过程必须将所有键值对迁移完毕之后才将结果返回给用户，这样的处理方式将是非常不友好的。

另一方面，要求服务器必须阻塞直到 rehash 完成，这对于 Redis 服务器本身也是不能接受的。

为了解决这个问题， Redis 使用了渐进式（incremental）的 rehash 方式：通过将 rehash 分散到多个步骤中进行，从而避免了集中式的计算。

渐进式 rehash 主要由 _dictRehashStep 和 dictRehashMilliseconds 两个函数进行：

• _dictRehashStep 用于对数据库字典、以及哈希键的字典进行被动 rehash
• dictRehashMilliseconds 则由 Redis 服务器常规任务程序（server cron job）执行，用于对数据库字典进行主动 rehash

_dictRehashStep

每次执行 _dictRehashStep ， ht[0]->table 哈希表第一个不为空的索引上的所有节点就会全部迁移到 ht[1]->table 。
在 rehash 开始进行之后（d->rehashidx 不为 -1）， 每次执行一次添加、查找、删除操作， _dictRehashStep 都会被执行一次：

因为字典会保持哈希表大小和节点数的比率在一个很小的范围内，所以每个索引上的节点数量不会很多，所以在执行操作的同时，对单个索引上的节点进行迁移，几乎不会对响应时间造成影响。

dictRehashMilliseconds
dictRehashMilliseconds 可以在指定的毫秒数内，对字典进行 rehash 。

当 Redis 的服务器常规任务执行时，dictRehashMilliseconds 会被执行，在规定的时间内，尽可能地对数据库字典中那些需要 rehash 的字典进行 rehash ， 从而加速数据库字典的 rehash 进程。

6、字典的收缩

当哈希表的可用节点数比已用节点数多很多时，就可以对哈希表进行 rehash 实现收缩字典。

默认情况下，当达到 10% 的时候，就会进行收缩。

redis.c/htNeedResize 函数定义如下：

/*
 * 检查字典的使用率是否低于系统允许的最小比率
 *
 * 是的话返回 1 ，否则返回 0 。
 */
int htNeedsResize(dict *dict) {
    long long size, used;

    // 哈希表大小
    size = dictSlots(dict);

    // 哈希表已用节点数量
    used = dictSize(dict);

    // 当哈希表的大小大于 DICT_HT_INITIAL_SIZE 
    // 并且字典的填充率低于 REDIS_HT_MINFILL 时
    // 返回 1
    return (size && used && size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < REDIS_HT_MINFILL));
}

7、字典的迭代

字典带有自己的迭代器实现 —— 对字典进行迭代实际上就是对字典所使用的哈希表进行迭代：

• 迭代器首先迭代字典的第一个哈希表，然后，如果 rehash 正在进行的话，就继续对第二个哈希表进行迭代。
• 当迭代哈希表时，找到第一个不为空的索引，然后迭代这个索引上的所有节点。
• 当这个索引迭代完了，继续查找下一个不为空的索引，如此反覆，直到整个哈希表都迭代完为止。

/*
 * 字典迭代器
 *
 * 如果 safe 属性的值为 1 ，那么表示这个迭代器是一个安全迭代器。
 * 当安全迭代器正在迭代一个字典时，该字典仍然可以调用 dictAdd 、 dictFind 和其他函数。
 *
 * 如果 safe 属性的值为 0 ，那么表示这不是一个安全迭代器。
 * 如果正在运作的迭代器是不安全迭代器，那么它只可以对字典调用 dictNext 函数。
 */
typedef struct dictIterator {

    // 正在迭代的字典
    dict *d;                

    int table,              // 正在迭代的哈希表的号码（0 或者 1）
        index,              // 正在迭代的哈希表数组的索引
        safe;               // 是否安全？

    dictEntry *entry,       // 当前哈希节点
              *nextEntry;   // 当前哈希节点的后继节点
} dictIterator;

Redis源码学习——字典,布布扣,bubuko.com

Redis源码学习——字典

原文：http://blog.csdn.net/xsc_c/article/details/21371871