字典 API ----------------- 表 4-1 列出了字典的主要操作 API 。 ---- 表 4-1 字典的主要操作 API +-----------------------+---------------------------------------------------+-----------------------------------+ | 函数 | 作用 | 时间复杂度 | +=======================+===================================================+===================================+ | ``dictCreate`` | 创建一个新的字典。 | :math:`O(1)` | +-----------------------+---------------------------------------------------+-----------------------------------+ | ``dictAdd`` | 将给定的键值对添加到字典里面。 | :math:`O(1)` | +-----------------------+---------------------------------------------------+-----------------------------------+ | ``dictReplace`` | 将给定的键值对添加到字典里面， | :math:`O(1)` | | | 如果键已经存在于字典，那么用新值取代原有的值。 | | +-----------------------+---------------------------------------------------+-----------------------------------+ | ``dictFetchValue`` | 返回给定键的值。 | :math:`O(1)` | +-----------------------+---------------------------------------------------+-----------------------------------+ | ``dictGetRandomKey`` | 从字典中随机返回一个键值对。 | :math:`O(1)` | +-----------------------+---------------------------------------------------+-----------------------------------+ | ``dictDelete`` | 从字典中删除给定键所对应的键值对。 | :math:`O(1)` | +-----------------------+---------------------------------------------------+-----------------------------------+ | ``dictRelease`` | 释放给定字典，以及字典中包含的所有键值对。 | :math:`O(N)` ， | | | | ``N`` 为字典包含的键值对数量。 | +-----------------------+---------------------------------------------------+-----------------------------------+ ---- .. 本节将对字典的主要操作 API 进行介绍， 它们包括： .. 对内容进行修改之后，记得更改这里 - 创建字典 - 添加键值对到字典 - 添加/替换键值对 - 获取键对应的值 - 删除键值对 - 删除字典 创建字典 """"""""""""" ``dictCreate`` 函数创建并返回一个空白的字典： :: dict *dictCreate(dictType *type, void *privDataPtr); ``type`` 参数指定了字典所使用的类型特定函数， ``privDataPtr`` 参数指定了供类型特定函数使用的私有数据。 下图展示了一个用 ``dictCreate`` 创建的空白字典的样子： .. graphviz:: image/dict-create.dot ``dictCreate`` 的工作就是创建并初始化一个新的 ``dict`` 结构， 而所有这些工作都可以在常数时间内完成， 因此 ``dictCreate`` 的复杂度为 :math:`O(1)` 。 添加键值对到字典 """""""""""""""""""" ``dictAdd`` 函数用于将键值对 ``key`` 和 ``val`` 添加到字典 ``d`` 中： :: int dictAdd(dict *d, void *key, void *val); ``dictAdd`` 只有在键 ``key`` 不存在于字典 ``d`` 时， 添加操作才能成功， 函数返回 ``dict.h/DICT_OK`` ； 如果键 ``key`` 已经存在于字典 ``d`` ， 那么添加操作将失败， 函数返回 ``dict.h/DICT_ERR`` 。 ``dictAdd`` 函数的工作可以分为两部分： 1. 根据需要， 为哈希表分配空间： 包括在字典空白时为 ``ht[0].table`` 分配空间， 以及在进行大小调整时， 为 ``ht[1].table`` 分配空间。 2. 将新键值对添加到哈希表中。 比如说， 如果字典 ``d`` 是一个刚刚使用 ``dictCreate`` 函数创建的空白字典的话， 那么 ``dictAdd`` 将根据 ``dict.h/DICT_HT_INITIAL_SIZE`` 常量的值， 对哈希表 ``ht[0]`` 的 ``table`` 数组进行初始化， 然后才将键值对添加到 ``ht[0]`` 哈希表中。 在当前版本中， ``DICT_HT_INITIAL_SIZE`` 的值为 ``4`` ， 也即是说， 函数会创建一个大小为 ``4`` 的哈希表。 举个例子， 假设字典 ``d`` 是一个空白字典， 那么在执行调用 ``dictAdd(d, k0, v0);`` 之后， 字典将变成这个样子： .. graphviz:: image/dict-after-insert.dot 在一般情况下， ``dictCreate`` 函数只执行一个 :math:`O(1)` 复杂度的添加操作， 而在最坏情况下， 函数除了执行添加操作以外， 还需要对哈希表执行 :math:`O(N)` 复杂度的空间分配操作， 因此， ``dictCreate`` 函数的最坏复杂度为 :math:`O(N)` ， 而平均复杂度则为 :math:`O(1)` 。 添加/替换键值对 """"""""""""""""""" :: int dictReplace(dict *d, void *key, void *val); ``dictReplace`` 函数可以执行以下两种操作的其中一种： - 添加操作： 当键 ``key`` 不存在于字典 ``d`` 时， 它将键值对 ``key`` 和 ``val`` 添加到 ``d`` 中， 作用和 ``dictAdd`` 完全一样。 - 替换操作： 当键 ``key`` 已经存在于字典 ``d`` 时， 它用 ``val`` 替换键 ``key`` 原来所关联的值。 当 ``dictReplace`` 执行的是添加操作时， 函数返回 ``1`` ； 当 ``dictReplace`` 执行的是更新操作时， 函数返回 ``0`` 。 比如说， 对于以下字典 ``d`` ： .. graphviz:: image/dict-replace.dot 执行 ``dictReplace(d, k2, v2);`` 会将键值对 ``k2`` 和 ``v2`` 添加到字典 ``d`` 中， 因为键 ``k2`` 并不存在于字典中： .. graphviz:: image/dict-replace-insert-case.dot 然后， 对字典 ``d`` 执行 ``dictReplace(d, k2, new_v2);`` ， 因为这时键 ``k2`` 已经存在， 所以键 ``k2`` 原来关联的值 ``v2`` 将被新值 ``new_v2`` 替代： .. graphviz:: image/dict-replace-update-case.dot 因为 ``dictReplace`` 执行的工作和 ``dictAdd`` 类似， 所以它的复杂度同样是最坏 :math:`O(N)` ， 平均 :math:`O(1)` 。 获取键对应的值 """""""""""""""""" ``dictFetchValue`` 返回键 ``key`` 在字典 ``d`` 中所对应的值： :: void *dictFetchValue(dict *d, const void *key); 当键存在于字典时， 函数返回键所关联的值； 如果键不存在于字典， 那么函数返回 ``NULL`` 。 以字典 ``d`` 来做例子： .. graphviz:: image/dict-fetch-value.dot 以下是一些 ``dictFetchValue`` 函数的执行示例： - 执行 ``dictFetchValue(d, k0);`` 将返回值 ``v0`` ； - 执行 ``dictFetchValue(d, k1);`` 将返回值 ``v1`` ； - 执行 ``dictFetchValue(d, k2);`` 将返回值 ``v2`` ； - 执行 ``dictFetchValue(d, k10086);`` 将返回值 ``NULL`` ，因为键 ``k10086`` 不存在于字典中。 在最坏情况下， ``dictFetchValue`` 为了查找某个键值对， 需要遍历哈希表某个索引上的所有节点， 所以这一操作的最坏复杂度为 :math:`O(N)` ； 另一方面， 在平均情况下， 哈希表的每个索引上都只有常数个节点， 因此， ``dictFetchValue`` 的平均复杂度为 :math:`O(1)` 。 删除键值对 """""""""""""""""""" ``dictDelete`` 函数用于删除字典中包含键 ``key`` 的节点， 并释放节点中的键和值： :: int dictDelete(dict *d, const void *key); 如果键 ``key`` 存在于字典中， 那么函数在执行删除操作之后返回 ``DICT_OK`` ; 如果键 ``key`` 不存在于字典中， 那么删除操作将失败， 函数返回 ``DICT_ERR`` 。 举个例子， 对以下字典 ``d`` 执行 ``dictDelete(d, k1);`` ， 字典中包含键值对 ``k1`` 和 ``v1`` 的节点将被删除： .. graphviz:: image/dict-delete-1.dot 以下是删除操作执行之后， 字典的样子： .. graphviz:: image/dict-delete-2.dot 删除操作的最坏复杂度为 :math:`O(N)` ， 平均复杂度为 :math:`O(1)` 。 .. 清空字典中的键值对 """""""""""""""""""""" ``dictEmpty`` 删除字典里的所有键值对， 释放哈希表 ``ht[0].table`` 和 ``ht[1].table`` 的空间， 但会保留字典本身的 ``dict`` 结构： :: void dictEmpty(dict *d); 对于以下字典 ``d`` ： .. graphviz:: image/dict.dot 执行 ``dictEmpty(d);`` 之后， 字典 ``d`` 将被更新为以下状态： .. graphviz:: image/dict-create.dot 可以看到， 被 ``dictEmpty`` 处理过的字典和 ``dictCreate`` 新创建的空白字典是完全一样的。 这说明， 如果你想清空并重用一个已有的字典， 而不是新创建一个字典的话， 那么就可以使用 ``dictEmpty`` 。 对于包含 :math:`N` 个键值对的字典， ``dictEmpty`` 需要删除 :math:`N` 个键值对， 因此， ``dictEmpty`` 的复杂度为 :math:`O(N)` 。 删除字典 """""""""""""""""" ``dictRelease`` 删除字典中的所有键值对， 并释放代表字典的 ``dict`` 结构： :: void dictRelease(dict *d); 对于带有 :math:`N` 个键值对的字典来说， ``dictRelease`` 需要删除 :math:`N` 个键值对， 因此， ``dictRelease`` 的复杂度为 :math:`O(N)` 。 .. 字典抽象 API ^^^^^^^^^^^^^^ :: /* * 针对字典抽象 */ /* * 返回节点 */ // 返回字典中包含键 key 的节点 dictEntry * dictFind(dict *d, const void *key); // 随机返回字典中的一个节点 dictEntry *dictGetRandomKey(dict *d); /* * 大小 */ // 缩小字典比率接近 1:1 int dictResize(dict *d); // 扩大字典 int dictExpand(dict *d, unsigned long size); // rehash N 个桶索引上的所有节点 // 普通程序用 int dictRehash(dict *d, int n); // 在给定时间内 rehahs 节点 // serverCron 调用 int dictRehashMilliseconds(dict *d, int ms);