中小型企业网站开发,如何加强网站信息建设,深圳市住房和建设局官方网站,中装建设算力租赁1. Dict基本结构 Redis的键与值的映射关系是通过Dict来实现的。
Dict是由三部分组成#xff0c;分别是哈希表#xff08;DictHashTable#xff09;#xff0c;哈希节点#xff08;DictEntry#xff09;#xff0c;字典#xff08;Dict#xff09;
哈希表结构如下图所…1. Dict基本结构 Redis的键与值的映射关系是通过Dict来实现的。
Dict是由三部分组成分别是哈希表DictHashTable哈希节点DictEntry字典Dict
哈希表结构如下图所示由于会发生哈希冲突所以entry个数可能会大于size size总是2的n次方
哈希节点的结构如下图所示
当我们向Dict添加键值对时Redis首先根据key计算出hash值h然后利用hsizemask其实就是h对数组长度取余计算元素应该存储到数组中哪个索引位置
建立一个哈希表以及哈希节点数组【1】中存入的是dictEntry的地址
如果遇到哈希冲突之后就会进行头插法将新插入的节点放入首节点位置因为新放入的数据预计会在较近的时间被访问其次头插法的时间复杂度低
dictEntry中的key和value大部分都是指针指向String类型的对象
Dict字典的结构如下图所示核心是dictht ht【2】用于在rehash时
所以整体Dict结构如下图所示
2. Dict渐进式rehash Dict中的hashtable就是数组结合单向链表的表现当集合中元素较多时必然会导致哈希冲突变多链表过长则查询效率大大降低。
Dict在每次新增键值对时都会检查负载因子LoadFactorused/size满足以下两种情况就会出发哈希表扩容
哈希表的LoadFactor1并且服务器并没有执行BGSAVE或者BGREWRITEAOF等后台进程哈希表的LoadFactor5 Dict除了扩容以外每次删除元素时也会对负载因子做检查当LoadFactor0.1时size4会做哈希表收缩
Dict的rehash并不是一次性完成的如果Dict中包含数百万的entry要在依次rehash完成极有可能导致主线程阻塞。因此Dict的rehash是分多次渐进式的完成因此称为渐进式rehash流程如下
计算新hash表的size值取决于当前要做的是扩容还是收缩
如果是扩容则新size为第一个大于等于dict.ht[0].used1的2^n如果是收缩则新size为第一个大于等于dict.ht[0].used的2^n不得小于4
按照新的size申请内存空间创建dictht并赋值给dict.ht[1]设置dict.rehashidx0标示开始rehash每次执行新增查询修改删除操作时也就是说每次访问dict时执行一次rehash都检查一下dict.rehashidx是否大于-1如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]并且将rehashidx直到dict.ht[0]的所有数据都rehash到dict.ht[1]将dict.ht[1]赋值给dict.ht[0],给dict.ht[1]初始化为空的哈希表释放原来的dict.ht[0]将rehashidx赋值为-1代表rehash结束在rehash过程中新增操作直接写入ht[1]查询修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行这样可以确保ht[0]的数据只减不增随着rehash最终为空
