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;
  1. dictht ht[2] :这是一个哈希表,长度为2。在没有rehash时只有第一个节点在使用,当rehash时会使用到哈希表的第二个节点。
  2. 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;
  1. dictEntry:hash节点 dictEntry
  2. size:hash数组长度。
  3. sizemask:计算索引值 = size -1
  4. used:该hash表已有的节点数量

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

Hash冲突

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

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

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

rehash和渐进式rehash

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

步骤:

  1. 为字典的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。
  2. 将保存在ht[0]中的所有键值对rehash到ht[1]上面:rehash指的是重新计算键的哈希值和索引值,然后将键值对放置到ht[1]哈希表的指定位置上。
  3. 当ht[0]包含的所有键值对都迁移到了ht[1]之后(ht[0]变为空表),释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备。

示例:

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

渐进式hash
  1. 为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表。
  2. 在字典中维持一个索引计数器变量rehashidx,并将它的值设置为0,表示rehash工作正式开始。
  3. 在rehash进行期间,每次对字典执行添加、删除、查找或者更新操作时,程序除了执行指定的操作以外,还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当rehash工作完成之后,程序将rehashidx属性的值增一。
  4. 随着字典操作的不断执行,最终在某个时间点上,ht[0]的所有键值对都会被rehash至ht[1],这时程序将rehashidx属性的值设为-1,表示rehash操作已完成。渐进式rehash的好处在于它采取分而治之的方式,将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上,从而避免了集中式rehash而带来的庞大计算量。
  • 具体的步骤讲解可以看《Redis的设计与实现》4.4rehash

式,将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上,从而避免了集中式rehash而带来的庞大计算量。

  • 具体的步骤讲解可以看《Redis的设计与实现》4.4rehash
上一篇:FME学习之旅---day24