字典

[TOC]

简介

字典是用来存储键值对的结构，亦即是他允许使用一个 键 来查找对应的 值，为什么需要把查找的依据跟需要的数据分开呢，因为 值 有可能会是一个非常复杂的结构，而 键 一般是从 值 推导出来的一个较为简单的表示方式。

字典也称哈希表，因为他主要是以各种 哈希函数 对 键 进行计算，并得到 一个唯一的 索引，来指向对应的 值。

哈希 (Hash)

哈希函数 哈希函数是指一类函数，他会将输入的参数进行一系列运算，并得出一个唯一的结果，一个设计良好的哈希函数能够从不同的参数得出不同的结果，并且这个结果将平均分布在样本空间中，如果将计算结果当成一个点，所有可能的结果集当成平面上的一个圆，那这些点将会平均的分布在这个圆上的各个地方。

时间复杂度 因为字典的查找在正常情况下，都只消耗跟 哈希 函数对应的时间，所以我们确定它是可以在常数时间，也就是 O(1) 得到结果的。

碰撞 有时候 哈希 函数根据 键 计算出来的索引不一定是唯一的，这个时候就会产生碰撞，也就是两个不同的 键 会指向同一个索引，这时有很多种方式来解决这个碰撞问题，如开地址法，链表法等，我们这里的实现只会介绍链表法。

这里进行分析的是 Redis 源码中的 Dict 实现，他较之正常定义的字典来说，主要是增加了自动扩展机制，使用了二重字典，在字典的负载超过阀值之后，就会以渐进的方式逐步将字典的内容扩展到一个新的字典中。

实现

字典的定义

// 定义了两个宏，用来表示字典的状态
 #define DICT_OK  0
 #define DICT_ERR 1

// hash 后的 字典项
// key 保存了用以查找该项的依据
// v 是保存的值
// next 则是前面说的链表法的实现，
// 当有碰撞时则将 hash 结果相同的项连接成一个链表
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

// dictType 保存了当前字典的信息，包括了 Hash 函数的具体实现
// 以及 `键` 跟 `值` 的比较、复制跟销毁方式
typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *key);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, const void *key);
    void (*valDestructor)(void *privdata, const void *key);
} dictType;

// 这个是确切的 哈希表，也就是字典的实现，
// 保存了字典的尺寸、使用量等
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigend long used;
} dictht;

// 字典对外公开的结构，其中即包含了用于重新扩展字典的标志信息:
// rehashidx
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx;
    int iterators;
} dict;

上面是跟字典相关的所有结构的定义，我们也大致说明了各个字段的意义。 基本上就是 dictht 是每个确切的 hash 表，而 dict 管理了两个 dictht，对他们进行了一个更上层的管理，如 Rehashing 机制。 接下来看看具体的实现，首先看看如何创建一个字典。

乱入的字典说明

由上面的结构定义我们能看到，Redis 的实现使用了 dict 来管理两个 dictht。 一般的字典实现是：

* 创建 Hash 表
* 增加元素
    * 对 Key Hash, 得到索引
    * 在指定的索引插入新元素
    * 如果有冲突，则使用各种冲突解决方案
* 查找元素
    * 对要查找的 Key 进行 Hash，得到索引
    * 在对应的索引位置查找需要的元素

Reids 的 dict 则将这些操作再次进行了包装，以满足再字典接近满负荷时，可以平滑的进行扩展，这个扩展的机制即是上面说过的 Rehashing

• 它使用了两个 dictdt, 并使用了 reashidx 来管理当前使用的 dictdt
• 当使用中的 dictdt 达到负荷条件时，则启动 Rehashing 机制
  • 将新的数据插入到另一个 dictdt
  • 并分批将旧的数据从原有的 dictdt 中移到新的 dictht。

所以在下文中，我们会经常看到 isRehashing 这个函数，它是用来判断当前 dict 是否正在进行 Rehashing，如果是的话则启动分批处理函数处理旧数据，并提示其他操作都要在新的 dictht 中进行。

创建字典 (dictCreate)

创建一个字典的时候需要提供两个参数。

• 一个字典类型的定义，其中包括了如何对 键 进行哈希，建 跟 值 的复制、比较以及销毁，具体定义可见 dictType 的定义.
• 一个私有数据：privDataPtr, 这个私有数据字典本身并不会用到，提供它的原因是为了字典类型的各个操作，当他们之间需要维护状态或者通信等操作时可以使用

dict *dictCreate(dictType *type, void privDataPrt) {
    dict *d = zmalloc(sizeof(*d));

    _dictInit(d, type, privDataPtr);
    return d;
}

int _dictInit(dict *d, dictType *type, void *privDataPtr) {
    // 首先重置当前字典的两个内置哈希表
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = -1;
    d->iterators = 0;
    return DICT_OK;
}

以上字典的初始化，主要是在 _dictInit 中实现，其中包括了重置字典的状态，初始化各个字段

• type 保存了字典的类型
• privdata 保存了私有数据
• rehashidx 保存了字典当前的扩展状态，如果值为 -1 说明当前没有在进行扩展
• iterators 则保存了迭代器信息

而 _dictReset 则设置各个字段的初始值。

static void _dictReset(dictht *ht) {
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

添加一个键值 (dictAdd)

接下来是往字典中添加一个项，也就是添加一个 键 跟其对应的 值。 测试代码如下：

// 这里我们使用了之前介绍过的 sds 模块，用他来保存我们的键值
// dictType = ...
dict *c = dictCreate(dtype, NULL);
sds *key = sdsnew("hello");
sds *val = sdsnew("world");

if (DICT_OK == dictAdd(d, key, val)) {
    // add kv ok
}

以上的测试代码中，首先新建了一个字典，然后分别使用 sds 来表示对应的 key 跟 value，然后将其加入字典中。 然后我们看看 dictAdd 的具体实现

int dictAdd(dict *d, void *key, void *val) {
    dictEntry *entry = dictAddRaw(d, key);
    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

所有的功能基本都是调用其他的内部接口，我们继续看内部的实现。 首先是 dictAddRaw, 它是根据 key 计算出其对应的索引值，并判断 key 是否已经存在于字典中，如果已经存在，则不做任何事情，如果不存在则返回对应的索引，然后才往字典中进行添加。

dictEntry *dictAddRaw(dict *d, void *key) {
    int index;
    dictEntry *entry;
    dictht *ht;

    // 这一步是用来扩展字典的，我们留到后面的章节来进行说明
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 如果 key 已经在字典中存在，则直接返回 NULL
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;

    // 接着添加一个新的节点用来存放新的字典项
    // 首先是获取当前可以插入数据的 dictht
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    // 将新的节点设为头节点，旧有的链表则作为新节点的后续节点
    entry->next = ht->table[index];
    ht->table[index] = entry;
    // 添加已有节点数
    ht->used++;

    // 设置新节点的 key 字段，这里的 dictSetKey 是个宏，作用是
    // 如果 字典类型指定了 key 的复制方式，则使用指定的复制方式，
    // 否则直接复制 key 的指针
    dictSetKey(d, entry, key);
    return entry;
}

上面很多步骤都包含了 dictIsRehashing 的调用，它用来判断当前字典是否正在扩展，具体如何扩展，我们留到后续的章节说明。 接着再继续看看 _dictKeyIndex 是如何获取 key 对应的索引值的

static int _dictKeyIndex(dict *d, const void *key) {
    unsigned int h, idx, table;
    dictEntry *he;

    // 判断字典是否需要扩展
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;

    h = dictHashKey(d, key); // 计算 key 对应的索引值
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while (he) {
            if (dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

重点只有两处

• 第一处是 dictHashKey 的实现，不过因为 字典 已经把 hash 的实现方式丢给了调用方，所以它这里只是单纯的转调 dictType 中的 hashFunction，具体的 hash 是怎么做的这里就不详细讨论了，最后会附上 Redis 使用的 HashFunction
• 第二处则是 for 循环，而 for 循环的重点则是查找两个 dictht，在指定的索引中寻找空位供新的元素插入。

然后附上 dictSetKey 的宏定义

#define dictSetKey(d, entry, _key_) do { \
    if ((d)->type->keyDup) \
        entry->key = (d)->type->keyDup((d)->privdata, _key_); \
    else \
        entry->key = (_key_); \
} while(0)

查找一个键值

在上面的示例代码中，我们往其中插入了元素之后，想根据 Key 来获取对应的 Value，则可以如下般调用

sds key = sdsnew("hello");

dictEntry *val = dictFind(c, key);
// 得到 dictEntry 后，即可从 v 字段得到所需的 value
printf("%s\n", (sds)val->v);

具体的实现很简单，其实就是一个插入新元素的过程，并且比插入元素还要简单得多， 首先计算 key 的 hash 值，得到其在 table 中对应的索引，然后遍历对应索引上的链表，逐一进行比较。

dictEntry *dictFind(dict *d, const void *key) {
    dictEntry *he;
    unsigned int h, idx, table;

    // 如果 dict 为空，则直接返回 NULL
    if (d->ht[0].size == 0) return NULL;

    // Rehashing 判断，下面章节会有详细说明
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 计算 key 对应的 hash 值
    h = dictHashKey(d, key);
    // 在有必要的情况下遍历两个 table, 这里的必要指的就是在 Rehashing 的情况下
    for (table = 0; table <= 1; table++) {
        // 根据当前 table 的尺寸进行取余
        idx = h & d->ht[table].sizemask;
        // 得到对应的元素链表
        he = d->ht[table].table[idx];
        // 逐一进行比较，如果找到则返回对应的 dictEntry
        while (he) {
            if (dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        // 只有正在进行 Rehashing 的情况下，才有必要再检查 ht[1]
        if (!dictIsRehashing(d)) return NULL;
    }
}

删除一个键值

删除的步骤也与查找跟插入类似，这里不再详说。

int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht, key, 0);
}

static int dictGenericDelete(dict *d, const void *key, int nofree) {
    unsigned int h, idx;
    dictEntry *he, *prevHe;
    int table;

    if (d->ht[0].size == 0) return DICT_ERR;
    if (dictIsRehashing(d)) _dictRehashStep(d);

    h = dictHashKey(d, key);

    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        prevHe = NULL;

        while (he) {
            if (dictCompareKeys(d, key, he->key)) {
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;

                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                }
                zfree(he);
                d->ht[table].used--;
                return DICT_OK;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return DICT_ERR;
}

Rehashing 的实现

在上面已经大致讲过了 Rehashing 的机制，也看到了在添加元素时，会调用对应的函数对 dictht 进行 Rehashing, 所以马上我们就来分析下具体的实现。

判断状态

首先是判断是否正在进行 Rehashing

#define dictIsRehashing(d) ((d)->rehashidx != -1)

直接判断 rehashidx 这个字段是否为 -1，如果正在 Rehashing，则 该字段则不等于 -1

何时进行 Rehashing

那什么时候会导致这个字段改变呢？也就是说，什么时候会导致 dict 需要进行 Rehashing，回忆上面的 _dictKeyIndex, 里面包含了：

static int _dictKeyIndex(dict *d, const void *key) {
    // ...
    if (_dictExpandIfNeeded(d) == DICT_ERR)
    // ...
}

_dictExpandIfNeeded 即根据 dict 的当前状态进行了判断，从而设置了该 rehashidx 字段。 接下来看看判断的具体逻辑

static int _dictExpandIfNeeded(dict *d) {
    // 如果正在进行，则直接返回 OK
    if (dictIsRehashing(d)) return DICT_OK;

    // 如果当前 dictht 为空，则已默认的大小 (4) 对其进行初始化
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used / d->ht[0].size > dict_force_resize_ratio) {
        return dictExpand(d, d->ht[0].used * 2);
     }
     return DICT_OK;
}

最后一个判断条件比较复杂，我们在这边进行解释:

首先要注意的是 dict_can_resize 这个标志，如果禁止了该标志，则只有当 used 是 size 的 dict_force_resize_ratio 倍时才会进行 Rehashing. 否则只要 used 大于 size, 也就是使用率大于 1,即会开始进行 Rehashing

然后我们可以看到，满足条件后会直接进入 dictExpand 这个调用。 该函数主要是根据当前 dict 的尺寸选择扩张的大小，并为将要使用的 dictht 进行初始化、分配内存等操作，最后则将 rehashidx 这个标志置为 0. 这个 0 表示的意思是，从需要 Rehashing 的 dictht 的第 0 个槽开始操作，所以只要不是 -1,它就表示当前正在处理的位置。

int dictExpand(dict *d, unsigned long size) {
    dictht n;
    // 选择将要扩张的尺寸，策略是扩张到下一个大于 size 的基于 2 的倍数的尺寸
    unsigned long realsize = _dictNextPower(size);

    // 如果已经在 Reashing 或者 dictht 的尺寸不合法，则返回错误
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    // 如果要扩张的尺寸等于当前尺寸（如已经满负荷，达到了 LONG_MAX) 则返回错误
    if (realsize == d->ht[0].size) return DICT_ERR;

    n.size = realsize;
    n.sizemask = realsize - 1;
    n.table = zcalloc(realsize * sizeof(dictEntry*));
    n.used = 0;

    // 如果是第一次扩张，也就是 dict 还没有使用过，则直接设置使用新的 dictht
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    // 否则设置为需要 Rehashing, 并设置新的 dictht
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;

}

static unsigned long _dictNextPower(unsigned long size) {
    unsigned long i = DICT_HT_INITIAL_SIZE;

    if (size >= LONG_MAX) return LONG_MAX;
    while (1) {
        if (i >= size)
            return i;
        i *= 2;
    }
}

如何 Rehashing

当当前 dict 进入 Rehashing 状态后，每次对 dict 进行操作时都会进入 _dictRehashStep，这里会先判断当前是否有操作在迭代 dict，如果没有的话，则进入 Rehashing 的操作。

Rehashing 的具体操作为：

• 默认执行 10 次
• 每次遍历一个 hash 槽
• 将旧的数据导到新的 dictht
• 更新 rehashidx 指向下一个需要更新的 dictht.table

static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d, 1);
}

// n 是指要 rehash 的次数，每次都会尝试从原有的 dictht 中导入 10 条数据到新的 dictht
int dictRehash(dict *d, int n) {
    int empty_visits = n * 10;
    if (!dictIsRehashing(d)) return 0;

    while (n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        assert(d->ht[0].size > (unsigned long)d->rehashidx);

        while (d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return1;
        }
        // 找到需要转移的槽
        de = d->ht[0].table[d->rehashidx];

        while (de) {
            unsigned int h;
            nextde = de->next;
            // 计算就有元素在新的 dictht 中的位置
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            // 重新连接冲突链表
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }

    // 如果旧有 ht 已经清空，将新的 ht 移到 dict->ht[0]
    // 并标志 Rehashing 已完成
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

    // 说明 Rehashing 还未完成
    return 1;
}

遍历字典

迭代器定义

首先看看迭代器的定义

• d 是一个指向需要迭代的 dict 的指针，
• index 就是迭代器的当前位置
• table 是当前遍历使用的 dictht
• safe 用来说明当前迭代器使用期间，不允许进行 Rehashing
• entry 是当前正在迭代的元素
• nextEntry 是下一个要迭代的元素，为了能够安全的迭代到下一个元素，因为使用者可能会删除当前元素

typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry; *nextEntry;
    // unsafe iterator fingerprint for misuse detection;
    // 用以判断 迭代器 的安全性
    long long fingerprint;
} dictIterator;

获取迭代器

获取普通迭代器

普通的迭代器说明当前迭代器使用期间，dict 有可能被纂改。

dictIterator *dictGetIterator(dict *d) {
    dictIterator *iter = zmalloc(sizeof(*iter));

    iter->d = d;
    iter->table = 0;
    iter->index = -1;
    iter->safe = 0;
    iter->entry = NULL;
    iter->nextEntry = NULL;
    return iter;
}

获取安全迭代器

安全迭代器跟普通迭代器的区别只有 safe 字段，并保证使用期间不会进行 Rehashing

dictIterator *dictGetSafeIterator(dict *d) {
    dictIterator *i = dictGetIterator(d);
    i->safe = 1;
    return i;
}

遍历迭代器

dict 提供了迭代器机制，以便对其中的元素进行遍历的。具体的使用只需如一个循环般，一直调用 dictNext 直到返回 NULL 即可。

dictEntry *dictNext(dictIterator *iter) {
    while (1) {

        if (iter->entry == NULL) {
            // 如果第一次调用 dictNext, 则初始化对应的标志
            dictht = *ht = &iter->d->ht[iter->table];
            if (iter->index == -1 && iter->table == 0) {
                if (iter->safe)
                    iter->d->iterators++;
                else
                    iter->fingerprint = dictFingerprint(iter->d);
            }
            // 更新指向下一个元素的索引
            iter->index++;

            // 如果超过了当前 ht 的尺寸，则判断是否正在 Rehashing，是的话，切换到新的
            // ht，因为新元素不会在插入到原有的 ht[0]
            if (iter->index >= (long)ht->size) {
                if (dictIsRehashing(iter->d)) && iter->table == 0) {
                    iter->table++;
                    iter->index = 0;
                    ht = &iter->d->ht[1];
                }
                else { // 到这里说明已经迭代到最后了
                    break;
                }
            }
            iter->entry - ht->table[iter->index];
        }
        else {
            // 如果当前槽仍有元素，则指向下一个
            iter->entry = iter->nextEntry;
        }

        // 如果当前元素不为空，则返回给用户，并准备好下一个
        if (iter->entry) {
            iter->nextEntry = iter->entry->next;
            return iter->entry;
        }
    }
    return NULL;
}

释放迭代器

迭代器用完了就得释放，特别是对于安全迭代器，因为他会导致 Rehashing 无法执行（除非是 Dict 严重超负荷：5倍）

void dictReleaseIterator(dictIterator *iter) {
    if (!(iter->index == -1 && iter->table ==0)) {
        if (iter->safe)
            iter->d->iterators--;
        else
            assert(iter->fingerprint == dictFingetprint(iter->d));
    }
    zfree(iter);
}

指纹验证

最后一提的是，在上面我们看到了 dictFingerprint 这个调用，能够为 dict 的当前状态生成一个指纹，并且在上面的普通迭代器中也保存了遍历开始时的指纹，这个指纹是用来保证，在遍历时用户没有对 dict 进行了非法的操作，比如删除元素或者增加元素。 具体的实现就不说明了。

long long dictFingerprint(dict *d) {
    long long integers[6], hash = 0;
    int j;

    iteragers[0] = (long)d->ht[0].table;
    iteragers[1] = d->ht[0].size;
    iteragers[2] = d->ht[0].used;
    iteragers[3] = (long)d->ht[1].table;
    iteragers[4] = d->ht[1].size;
    iteragers[5] = d->ht[1].used;

    for (j = 0; j < 6; j++) {
        hash += iteraters[j];

        hash = (~hash) + (hash << 21);
        hash = hash ^ (hash >> 24);
        hash = (hash + (hash << 3)) + (hash << 8); // hash * 265
        hash = hash ^ (hash >> 14);
        hash = (hash + (hash << 2)) + (hash << 4); // hash * 21
        hash = hash ^ (hash >> 28);
        hash = hash + (hash << 31);
    }
    return hash;
}