[TOC] ### **基本原理** ***** #### **什么是字典** `字典`，又称为`符号表`（symbol table）、`关联数组`（associative array）或`映射`（map），是一种用于保存键值对（key-value pair）的`抽象数据结构` 在字典中，一个键（key）可以和一个值（value）进行关联（或者说将键映射为值），这些关联的键和值就称为键值对。 #### **字典底层的实现** Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。 #### **哈希表** Redis字典所使用的哈希表由dict.h/dictht结构定义： ``` typedef struct dictht {     // 哈希表数组     dictEntry **table;     // 哈希表大小     unsigned long size;     // 哈希表大小掩码，用于计算索引值      // 总是等于size-1     unsigned long sizemask;     // 该哈希表已有节点的数量     unsigned long used; } dictht; ``` `table`属性是一个数组，数组中的每个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对。 `size`属性记录了哈希表的大小，也即是table数组的大小， `used`属性则记录了哈希表目前已有节点（键值对）的数量。 `sizemask`属性的值总是等于size-1，这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面。 下图展示了一个大小为4的空哈希表（没有包含任何键值对）：  #### **哈希表节点** 哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对： ``` typedef struct dictEntry {     //键     void *key;  //值     union{         void *val;         uint64_tu64;         int64_ts64;     } v;     //指向下个哈希表节点，形成链表     struct dictEntry *next; } dictEntry; ``` `key`属性保存着键值对中的键，而v属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_t整数，又或者是一个int64_t整数。 **next**属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来`解决键冲突`（collision）的问题。 下图展示了如何通过next指针，将两个索引值相同的键k1和k0连接在一起。  #### **字典的定义** Redis中的字典由dict.h/dict结构表示： ``` typedef struct dict {     //类型特定函数     dictType*type;     //私有数据     void *privdata;    // 哈希表      dictht ht[2];    //rehash 索引    // 当rehash 不在进行时，值为-1     in trehashidx; /* rehashing not in progress if rehashidx == -1 */ } dict; ``` `type`属性和`privdata`属性是针对不同类型的键值对，为创建多态字典而设置的： ``` ·type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作 特定类型键值对的函数， Redis会为用途不同的字典设置不同的类型特定函数。 ·privdata属性则保存了需要传给那些类型特定函数的可选参数。 ``` ``` typedef struct dictType {     // 计算哈希值的函数    unsigned int (*hashFunction)(const void *key);     // 复制键的函数     void *(*keyDup)(void *privdata, const void *key);     // 复制值的函数     void *(*valDup)(void *privdata, const void *obj);     //对比键的函数     int (*keyCompare)(void *privdata, const void *key1, const void *key2);     //  销毁键的函数     void (*keyDestructor)(void *privdata, void *key);     // 销毁值的函数     void (*valDestructor)(void *privdata, void *obj); } dictType; ``` `ht属性`是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht\[0\]哈希表，ht\[1\]哈希表只会在对ht\[0\]哈希表进行rehash时使用。 除了ht\[1\]之外，另一个和`rehash`有关的属性就是`rehashidx`，它记录了rehash目前的进度，如果目前没有在进行rehash，那么它的值为-1。 下图展示了一个普通状态下（没有进行rehash）的字典：  ### **哈希算法** ***** 当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。 **哈希算法详情** 参见：[哈希算法](%E7%AC%AC%E5%9B%9B%E8%8A%82%EF%BC%9A%E5%AD%97%E5%85%B8%E7%9A%84%E5%AE%9E%E7%8E%B0%E4%BA%8C-%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95.md) ### **哈希冲突的解决** ***** 当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突（collision）。 **字典哈希冲突解决方案** 参见 :[哈希冲突解决方案](%E7%AC%AC%E4%BA%94%E8%8A%82%EF%BC%9A%E5%AD%97%E5%85%B8%E7%9A%84%E5%AE%9E%E7%8E%B0%E4%B8%89-%E8%A7%A3%E5%86%B3%E9%94%AE%E5%86%B2%E7%AA%81.md) ### **rehash的原理** ***** 随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。 `rehash操作详情` 参见：[rehash原理](%E7%AC%AC%E5%85%AD%E8%8A%82%EF%BC%9A%E5%AD%97%E5%85%B8%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%9B%9B-rehash%E5%8E%9F%E7%90%86.md)