Redis（字典hash表）

字典也可以称为Map、关联数组、映射、符号表。字典表在C语言中没有实现，所以Redis知己实现了字典。

在字典中一个key对应一个value。key是唯一的。这些关联的键和值称为键值对。

字典的应用非常广泛，Redis数据库的底层实现就是字典，对数据库的增删改查都是使用的字典。

字典的结构

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

dictht ht[2] ：这是一个哈希表，长度为2。在没有rehash时只有第一个节点在使用，当rehash时会使用到哈希表的第二个节点。
trehashidx：当rehash不在进行时，值为-1。后面会说到rehash。、

hash节点结构

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

hash节点中存储的是key和value。假如存储的是String类型。则存储的数据如下 set s hello

在这里插入图片描述

同理以字典表为基础也能够实现集合、hash、列表、有序列表这些数据结构。我就不一一列举了。

Hash表

结构：

typedef struct dictht {
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码，用于计算索引值
    //总是等于size-1
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
} dictht;

dictEntry：hash节点 dictEntry
size：hash数组长度。
sizemask：计算索引值 = size -1
used：该hash表已有的节点数量

示例结构：
在这里插入图片描述

Hash冲突

Hash表存储数据首先是要进行hash计算。计算规则是根据键的先计算一个hash值然后再根据hash表数组长度size和sizemask计算该键值对需要放到那个索引下面。

如果两个键计算的索引位置时一样的则会用hash节点的next进行连接生成一个hash链表的方式。

示例：
在这里插入图片描述

rehash和渐进式rehash

字典表中的ht是长度为2的hash数组。上面的介绍都没有提及ht[1]的用处。ht[1]是为了在数据越来越多时进行rehash使用的，你可以理解为把hash表的数组增长然后再把原来的数据移动到增长后的数组上去。

步骤：

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

示例：

在这里插入图片描述

渐进式hash

为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键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。