第四章 字典

字典，又称为符号表，关联数组，或映射，是一种用于保存键值对的抽象数据结构。
字典中每个键都是独一无二的，可以根据键查找与之关联的值，或者通过键来更新值，或者根据键来删除整个键值对。

应用：

• 字典在Redis中应用相当广泛，Redis数据库就是使用字典来作为底层的实现，对数据库进行增、删、改、查构建在字典的操作之上。（在数据库中创建一个键为“msg”，值为“hello word”的键值对时，这个键值对就是保存在代表数据库的字典里面的。）�
• 字典还是哈希键的底层实现之一，哈希键包含的键值对比较多，或者键值对中的元素都是比较长的字符串时；

4.1字典的实现

底层使用的是哈希表，一个哈希表可以有多个哈希表节点，而每个哈希表节点就保存了一个键值对；

4.1.1哈希表

结构

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数组的哪个索引上面。

WechatIMG56.jpeg

�

4.1.2哈希表节点

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存一个键值对；

结构

typedef struct dictEntry{
    //键
    void *key;
    //值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    //指向下一个哈希表节点，形成链表
    struct dictEntry *next;
}dictEntry;

• key属性保存键
• v属性保存值，其中v属性可以是一个指针，或者是一个uint64_t整数，或者是一个int64_t整数；
• next属性指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，来解决键冲突问题。

WechatIMG57.jpeg

4.1.3 字典

结构

 typedef struct dict{
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
�
    //rehash 索引
    //当rehash不在进行时，值为-1；
    int rehashidx;
} dict;

typedef struct dictType{
    //计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
    //复制键的函数
     void *(*keyDup) (void *privdata , const void *key);
    //复制值的函数
    void *(*valDup) (void *privdata , const void *obj);
    //对比键的函数
    void (*keyCompare) (void *privdata , const void *key1, const void *key2 );
    //销毁键的函数
    void (*keyDestructor) (void *privadata , void *key );
    //销毁值的函数
    void (*valDestructor) (void *privdata , void *obj );
} dictType;

• type属性是一个指向dictType结构的指针，保存了一簇用于操作特定类型键值对的函数
• privdata属性，保存了需要传给那些类型特定函数的可选参数
• ht属性包含两个项数组，数组中每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1] 哈希表只会在对ht[0]哈希表进行rehash时使用
• 除了ht[1]之外，另一个和rehash有关的属性就是rehashidx，记录了rehash目前的进度，如果目前没有在进行rehash，那么他的值就是-1;

WechatIMG58.jpeg

4.2 哈希算法

将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引，然后在根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

计算方法：

// 使用字典设置哈希函数，计算键key的哈希值
hash = dict -> type -> hashFunction(key);

//使用哈希表的sizemask属性和哈希值，计算出索引值
//根据情况不同，ht[x]可以是ht[0]或ht[1]；
index = hash & dict -> ht[x].sizemask;

当字典被用作数据库，或哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值；该算法的优点在于即使输入的键是有规律的，算法仍能给一个很好地随机分配性，并且算法的计算速度也很快。�

4.3 解决键冲突

当有两个或两个以上的的键被分配到哈希表数组的同一个索引上面时，称为键冲突

Redis的哈希表使用链地址法来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来。

因为dictEntry节点组成的链表没有指向链表表尾的指针，为了速度考虑，程序总是将新节点添加到链表表头位置(复杂度为O(1)),排在已有节点的前面。

WechatIMG61.jpeg

4.4 rehash

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

主要通过执行rehash操作完成，步骤如下（详情见书30）：

1. 为字典ht[1]哈希表分配空间，哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（ht[0].used属性）
   • 扩展操作：ht[1]的大小为第一个大于等于ht[0].used*2的2^n(2的n次方幂)
   • 收缩操作：ht[1]的大小为第一个大于等于ht[0].used的2^n(2的n次方幂)
2. 将保存在ht[0]中所有的键值对rehash到ht[1]上面: rehash指的是重新计算键的哈希值和索引值，然后将键值对放到ht[1]哈希表的指定位置上。
3. 当ht[0] 上所有的键值对都迁移到了ht[1]之后，释放ht[0],将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下次rehash做准备。

哈希表的扩展与收缩

满足任意条件时，程序会自动对哈希表执行扩展操作：

• 服务器没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1.
• 服务器正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5.

哈希表的负载因子公式：
负载因子 = 哈希表已保存的节点数(ht[0].used) / 哈希表大小(ht[0].size)

根据是否执行BGSAVE命令或者BGREWRITEAOF命令，服务器执行扩展操作所需的负载因子不同，因为在执行该命令的过程中，Redis需要创建当前服务器的子进程，大多数的操作系统都采用写时复制技术来优化子进程的使用效率！在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而避免在子进程存在期间进行哈希表的扩展操作，可以避免不必要的内存写入操作，最大限度的节约内存。

当哈希表的负载因子小于0.1时，程序会自动开始对哈希表执行收缩操作。�

渐进式rehash

rehash动作不是一次性，集中式的完成，而是分多次的渐进式的完成。原因在于保存的键值对数量是百万级，千万级时，一次性将这些键值对全部rehash到ht[1]的话，庞大的计算量会导致服务器在一段时间内停止服务。

详细步骤：

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

渐进式rehash执行期间的哈希表操作

在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所有，字典的删除，查找，更新，等操作都会在两个表上进行。例如在字典里查找一个键的话，会先在ht[0]里面进行查找，没有找到的话会继续到ht[1]里面进行查找。另外，新添加到字典里面的键值对，一律会保存到ht[1]里面，ht[0]不会进行任何添加操作。

4.6 字典API

函数：作用	时间复杂度
dictCreate：创建一个新的字典	O(1)
dictAdd：将给定的键值对添加到字典里面	O(1)
dictReplace：将给定的键值对添加到字典里面，如果键已存在，那么新值将取代原有的值	O(1)
dictFetchValue：返回给定的键的值	O(1)
dictGetRandomKey：从字典里面随机返回一个键值对	O(1)
dictDelete：从字典里面删除给定键所对应的键值对	O(1)
dictRelease：释放给定字典，以及字典中包含所有键值对	O(n)