道冲而用之，或不盈。渊兮，似万物之宗。

挫其锐，解其纷，和其光，同其尘。

湛兮，似或存。

什么是字典

字典也叫散列表，是一种存储键值对（key-value pair）的数据结构。可以将其想象成一个非常有用和有趣的工具箱。就像现实生活中的字典可以帮助我们查找词语的定义一样，字典可以帮助我们通过给定的键来查找、插入、删除和更新相应的值。

字典是一种聪明的数据结构，它以键-值对的形式存储数据。每个键都是特殊且唯一的，与之关联的是对应的值。你可以将字典看作是一个巨大的盒子，里面存放着各种有趣的东西，而每个东西都有一个标签（键）来描述它。

使用字典的好处在于它能够快速地根据键找到对应的值，就像你可以迅速找到一个单词的定义一样。这得益于字典内部采用高效的数据结构（例如哈希表或搜索树）来实现快速的查找操作。

另一个很酷的地方是，字典是灵活的，可以存储各种类型的值，无论是整数、字符串还是对象等。这使得字典成为了处理不同类型数据的理想选择。

现在我们知道字典有几个特性：

1. 字典中的键（key）是唯一的，数据类型可以是字符串、整型、浮点型等。
2. 字典能够存储海量数据。
3. 字典中键（key）对应的值可以是任意类型。
4. 高效查询：能够快速查询到值，O(1)时间复杂度查询或设置值。
5. 动态增长：字典能够根据数据动态调整容量（增加或减少容量）。

字典在Redis中的运用

字典在Redis中可以说是无处不在，Redis中的数据库底层就是用字典来实现的。

比如我们输入以下命令：

127.0.0.1:6379> SET name zhangsanOK

Redis Server 会在数据库中创建一个key为name，value为zhangsan的键值对，并保存在代表当前数据库的字典上。

哈希键也是通过字典实现的（哈希键包含的键值对较少时，redis使用压缩列表作为哈希建的底层实现），此外，Redis的发布订阅、过期键、Lua脚本缓存同样是字典实现的。

说到这里，你一定对Redis是如何实现字典很好奇，别着急，我们先来看下怎么设计一个字典，心急的同学可以直接看Redis中字典实现部分

如何设计一个字典

本部分介绍如何设计一个字典。

选择合适的数据结构

字典作为一种数据结构，首先要能存储海量数据。其次要可以高效查询。要实现这个，可以用数组实现。既可以存储海量数据，又能够根据下标快速定位元素。

所以首先我们需要一个数据结构，这个数据结构里有一个属性data，是数组类型。

问题来了，数组是通过下标定位元素的，但字典的key是可以是字符串、整型、浮点型等类型的。而数组的下标只能是整数，而字符串、浮点型这些是不能作为下标的？要解决这个问题，就要对key对一些特殊处理，这个过程我们把它叫做Hash。

Hash也叫散列，或者音译“哈希”。其作用在于将任意程度的输入，通过一系列的算法，输出固定长度、固定类型的内容，也就是说hash函数可以不同内容输出相同的整型数据，具备以下特点：

1. 固定输出长度：无论输入数据的长度如何，哈希函数都会生成一个固定长度的哈希值。
2. 映射性：对于相同的输入，哈希函数总是生成相同的哈希值。
3. 高效性：哈希函数的计算过程应该是高效的。
4. 雪崩效应：输入数据的微小变化应该导致哈希值的巨大变化。

山外青山楼外楼，Hash函数可以将任意输入的键转换成整型数据输出，但又引出一个新问题，键的Hash值非常大，通常是32位或者64位，直接用来做下标肯定是不合适的。想象一下，仅仅需要字典存储几十个键值对，但却不得不新建一个很大的数组，这无疑是空间的浪费，本着浪费可耻的原则，来看下这个问题该怎么解决。

给数组设置一个大小限制，比如说8，等容量超过一定阈值，再进行扩容。现在一个基本的字典数据结构出来了。

字典基本数据结构

较大的hash值如何跟较小的数组下标关联呢？最简单的办法就是将hash值对数组容量进行取余，这样就能永远得到一个小于数组容量大小的值。这个值就能用来作为数组下标了。

现在是不是就很完美了呢？显然并不是！那就是hash冲突，所谓hash冲突就是不同的输入经过hash计算后得到相同的输出。这是不可避免的，任何算法都不可能是完美的。

要解决hash冲突，因此数组中的元素不仅应该存储值，还要存在一个指针，用来将冲突的数据用链表的形式保存起来。此时数组中的元素字段也就确定了。

冲突后的数据结构

当查询的时候，分以下几个步骤：

1. 先对key进行hash、取余操作，得到数组下标，在数组中找到对应值
2. 判断元素中的key是否一致，一致则返回，不一致则读取next指向的元素重复判断，直到next为空，不存在返回不存在

至于键值对的值可以是任意类型，我们可以将dictEntry中的value属性用指针来表示，指向不同类型的值。

到这一步，对字典的数据结构已经设计完了，现在来看下在Redis关于字典的实现。

Redis中字典实现

数据结构

struct dict {    dictType *type;    dictEntry **ht_table[2];    unsigned long ht_used[2];    long rehashidx; /* rehashing not in progress if rehashidx == -1 */    /* Keep small vars at end for optimal (minimal) struct padding */    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */    signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */};

ht_table，是一个指针数组，有两个元素ht_table[0]和ht_table[1]，分别表示两个哈希表，其中的每个元素都是 dictEntry* 类型的指针。正常情况下，数据是存储在ht_table[0]中的，ht_table[1]用来做扩缩容。

ht_used，分别记录了ht_table中的元素容量。ht_used[0] 表示 "0 号哈希表" 中已使用的槽数量，ht_used[1] 表示ht_table[1]中已使用的槽数量。通过跟踪已使用的槽数量，可以控制哈希表的负载因子，从而在需要时触发 rehashing 过程。

rehashidx，用于标识 rehashing 的进度。如果 rehashidx 的值为 -1，则表示当前没有正在进行的 rehashing 过程。否则，它表示正在进行 rehashing 的索引位置，即 ht_table[0]中要迁移的下一个槽位的索引。

pauserehash，用于暂停 rehashing 过程。当 pauserehash 大于 0 时，表示 rehashing 被暂停。小于 0 则表示存在编码错误。

ht_size_exp，记录哈希表的大小指数值。在 Redis 的字典中，哈希表的大小是通过指数来表示的。具体来说，一个哈希表的大小为 2 的 ht_size_exp 次方。因此，ht_size_exp 字段存储了两个哈希表的大小指数值，分别对应 ht_table[0]和ht_table[1]。

dictType，Redis字典这个数据结构，除了主数据库的K-V数据存储外，还有很多其他地方会用到。例如，Redis的哨兵模式，就用字典存储管理所有的Master节点及Slave节点；再如，数据库中键值对的值为Hash类型时，存储这个Hash类型的值也是用的字典。在不同的应用中，字典中的键值对形态都可能不同，而dictType就是为了实现各种形态的字典而抽象出来的一组操作函数。结构如下：

type def  struct dictType {    uint64_t (*hashFunction)(const void *key);    void *(*keyDup)(dict *d, const void *key);    void *(*valDup)(dict *d, const void *obj);    int (*keyCompare)(dict *d, const void *key1, const void *key2);    void (*keyDestructor)(dict *d, void *key);    void (*valDestructor)(dict *d, void *obj);    int (*expandAllowed)(size_t moreMem, double usedRatio);    /* Allow a dictEntry to carry extra caller-defined metadata.  The     * extra memory is initialized to 0 when a dictEntry is allocated. */    size_t (*dictEntryMetadataBytes)(dict *d);} dictType;

哈希表中的元素都是用dictEntry来封装的，主要作用是存储键值对。v是个联合字段，存储的是键值对中的值，这里用联合字段的好处就是可以在不同场景使用不同字段存储。当存储的值为数值类型的时候，可以直接用联合体中定义的数值类型，而不需要使用val指针分配内存。

typedef struct dictEntry {    void *key;    union {        void *val;        uint64_t u64;        int64_t s64;        double d;    } v;    struct dictEntry *next;     /* Next entry in the same hash bucket. */    void *metadata[];           /* An arbitrary number of bytes (starting at a                                 * pointer-aligned address) of size as returned                                 * by dictType's dictEntryMetadataBytes(). */} dictEntry;

普通状态（没有rehash）下的字典

上图是一个在普通状态（没有rehash）下的字典。

了解完整理结构，下面来看下Redis的hash算法是如何实现的。

#define dictHashKey(d, key) (d)->type->hashFunction(key)#define DICTHT_SIZE_MASK(exp) ((exp) == -1 ? 0 : (DICTHT_SIZE(exp))-1)// 计算key的hash值(d)->type->hashFunction(key)// 计算索引值idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]);

添加元素

dictAdd的作用就是添加键值对，详细见下面代码。代码比较简单，且做了注释，就不解释了。

/* Add an element to the target hash table */int dictAdd(dict *d, void *key, void *val){    // 添加key，如果key已经存在，则返回NULL，否则将key添加到新节点并将新节点返回    dictEntry *entry = dictAddRaw(d,key,NULL);    // key 存在，直接返回错误    if (!entry) return DICT_ERR;    // 设置值    dictSetVal(d, entry, val);    return DICT_OK;}

接下来看下dictAddRaw是如何添加和查找key的。

dictAddRaw 函数是用于添加新键值对的函数。它首先检查是否正在进行 rehashing，然后通过调用 _dictKeyIndex 函数获取要插入的新元素的索引。接下来，它根据当前是否正在进行 rehashing 决定将新元素插入到哪个哈希表中，然后分配内存创建新的 dictEntry 并插入到哈希槽中。最后，它设置新元素的键值并返回插入的 dictEntry结构体。

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing){    long index;    dictEntry *entry;    int htidx;    // 判断是否在进行rehash，如果是，再做一次。确保在添加新元素之前，字典已经完成了可能正在进行的 rehashing 过程    if (dictIsRehashing(d)) _dictRehashStep(d);    // 判断key是否存在，存在则返回-1，否则返回新元素的索引    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)        return NULL;    // 根据当前是否在rehash，确定新元素插入到ht_table[0]还是ht_table[1].    htidx = dictIsRehashing(d) ? 1 : 0;    // 通过使用 zmalloc 函数分配内存来创建新的 dictEntry 结构体，    // 并设置其 next 字段指向当前哈希槽的第一个元素。    // 然后，将新的 dictEntry 插入到哈希槽中，并将 ht_used 计数加一，表示该哈希槽已被使用    size_t metasize = dictMetadataSize(d);    entry = zmalloc(sizeof(*entry) + metasize);    if (metasize > 0) {        memset(dictMetadata(entry), 0, metasize);    }    entry->next = d->ht_table[htidx][index];    d->ht_table[htidx][index] = entry;    d->ht_used[htidx]++;    /* Set the hash entry fields. */    dictSetKey(d, entry, key);    return entry;}

下图展示了添加一个元素后的字典结构

添加一个元素的数据结构

hash冲突

当存在两个或者两个以上的key被分配在哈希表的同一个索引上时，我们称之为发生了冲突（collision），解决冲突主流有两种方式：链地址法和开放地址法。

1. 链地址法（Chaining）：每个哈希表节点维护一个链表，当有冲突发生时，将键值对添加到对应节点的链表中。这样，相同哈希值的键值对可以按顺序链接起来。
2. 开放地址法（Open Addressing）：
3. 线性探测（Linear Probing）：当发生冲突时，依次检查下一个槽位，直到找到一个空闲槽位。
4. 二次探测（Quadratic Probing）：当发生冲突时，通过一系列二次方的增量来查找下一个槽位。
5. 双重哈希（Double Hashing）：通过使用第二个哈希函数，在发生冲突时计算另一个增量来查找下一个槽位。

Redis采用的是链地址法，每个哈希表节点维护了一个单向链表，当有冲突时，将链表最后一个元素的next指针指向新的元素。示意图如下：

冲突后的数据结构

rehash

随着操作的不断执行，字典中的哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

扩展或者收缩是通过执行rehash来完成的。过程如下：

1. 为dict的ht_table[1]分配空间，ht_table[1]空间的大小取决于当前执行的操作，比如扩容时，Redis 首先会根据当前字典中已使用的槽位数量和负载因子等信息计算出新的哈希表大小。
2. 将ht_table[0]rehash到ht_table[1]上，释放ht_table[0]，将ht_table[1]设置为ht_table[0]，并在ht_table[1]新创建一个空白哈希表，为下一次rehash做准备。

要注意的是rehash的动作不是一次性完成的，而是分多次、渐进式完成的。假设ht_table[0]中的元素有几百万，几千万甚至是几亿个时，一次性把这些数据rehash到ht_table[1]的话，庞大的计算量可能会导致服务器在一段时间内停止服务。

因此为避免rehash对服务器性能造成影响，服务器不是一次性将ht_table[0]里面的所有键值对全部rehash到ht_table[1]，而是分多次、渐进式地将ht_table[0]里面的键值对慢慢地rehash到ht_table[1]。具体操作如下：

1. 为ht_table[1]分配空间，让字典同时持有ht_table[0]和ht_table[1]两个哈希表。
2. 在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
3. 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht_table[0]哈希表在rehashidx索引上的所有键值对rehash到ht_table[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。
4. 随着字典操作的不断执行，最终在某个时间点上，ht_table[0]的所有键值对都会被rehash至ht_table[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

渐进式rehash的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。

int dictRehash(dict *d, int n) {    int empty_visits = n * 10; /* 最多访问的空桶数 */    if (!dictIsRehashing(d)) return 0;  // 如果字典没有进行rehash，则直接返回    while (n-- && d->ht_used[0] != 0) {  // 迭代n个桶位或者直到ht[0]为空        dictEntry *de, *nextde;        // 确保rehashidx不会溢出，因为ht[0].used != 0，所以一定存在更多的元素        assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx);        // 查找下一个非空桶位        while (d->ht_table[0][d->rehashidx] == NULL) {            d->rehashidx++;            if (--empty_visits == 0) return 1;  // 达到最大空桶访问次数，返回1表示还有剩余元素需要迁移        }                de = d->ht_table[0][d->rehashidx];        // 将当前桶位中的所有键从旧哈希表迁移到新哈希表        while (de) {            uint64_t h;            nextde = de->next;            // 在新哈希表中计算键的索引位置            h = dictHashKey(d, de->key) & DICTHT_SIZE_MASK(d->ht_size_exp[1]);            // 将键值对插入新哈希表的对应索引位置            de->next = d->ht_table[1][h];            d->ht_table[1][h] = de;            d->ht_used[0]--;            d->ht_used[1]++;            de = nextde;        }                // 将旧哈希表中的当前桶位设为NULL，表示迁移完成        d->ht_table[0][d->rehashidx] = NULL;        d->rehashidx++;    }    // 检查是否已经完成了整个哈希表的rehash    if (d->ht_used[0] == 0) {        // 释放旧哈希表的内存空间        zfree(d->ht_table[0]);                // 将新哈希表复制到旧哈希表        d->ht_table[0] = d->ht_table[1];        d->ht_used[0] = d->ht_used[1];        d->ht_size_exp[0] = d->ht_size_exp[1];        // 重置新哈希表        _dictReset(d, 1);        d->rehashidx = -1;  // rehash过程完成，重置rehashidx        return 0;  // 返回0，表示rehash过程结束    }    return 1;  // 还有剩余元素需要迁移，返回1继续进行rehash}

一些api

下表列出了 Redis 中 dict 数据结构的主要 API，包括其作用和时间复杂度。

这些 API 提供了对 Redis 字典（dict）数据结构进行操作的常见方法。它们包括创建和释放字典、添加、替换、删除键值对、查找键值对、调整大小、执行 rehashing 过程、检查状态、迭代键值对等功能。

大多数 API 的时间复杂度都是 O(1)，即平均情况下具有常数时间复杂度。但在某些情况下，如执行 rehashing 或调整大小时，时间复杂度可能为 O(N) 或 O(M)，其中 N 表示字典中的元素数量，M 表示迁移的元素数量。

需要注意的是，虽然大多数操作的时间复杂度是常数级别的，但实际性能还受到其他因素（如哈希函数的质量、哈希冲突的情况、字典的负载因子等）的影响，因此具体的性能可能会有所不同。

写在最后

Redis中的字典是一种基于哈希表的数据结构，广泛用于实现不同功能，如数据库和哈希键。

• 字典内部使用哈希表作为底层数据结构，每个字典包含两个哈希表。其中一个哈希表在正常操作时使用，另一个仅在进行rehash（扩容）时使用。
• 在Redis中，当字典被用作数据库的底层实现或者哈希键的底层实现时，会使用MurmurHash2算法来计算键的哈希值。这种哈希算法能够快速并且均匀地分布键的哈希值，减少冲突的可能性。
• 哈希表使用链地址法来解决键冲突。如果多个键被映射到相同的索引位置，它们将按顺序连接成一个单向链表。通过链地址法，可以在同一个槽位上存储多个键值对。
• 在对哈希表进行扩展或收缩操作时，需要将现有哈希表中的所有键值对逐步迁移到新的哈希表中。这个迁移过程称为rehash，它是渐进式的，逐步完成的。渐进式rehash使得Redis能够平滑地进行哈希表的扩展和收缩，避免了一次性大规模的数据迁移。