什么网站能免费做公众号封面,移动互联网开发试卷,创意100图片欣赏,个人网站建设月租抵30元文章目录 1. 引言2. redis 源码下载3. dict 数据结构4. 哈希表扩容与 rehash5. 参考 1. 引言
前情提要#xff1a; 《redis 从0到1完整学习 #xff08;一#xff09;#xff1a;安装初识 redis》 《redis 从0到1完整学习 #xff08;二#xff09;#xff1a;red… 文章目录 1. 引言2. redis 源码下载3. dict 数据结构4. 哈希表扩容与 rehash5. 参考 1. 引言
前情提要 《redis 从0到1完整学习 一安装初识 redis》 《redis 从0到1完整学习 二redis 常用命令》 《redis 从0到1完整学习 三redis 数据结构》 《redis 从0到1完整学习 四字符串 SDS 数据结构》 《redis 从0到1完整学习 五集合 IntSet 数据结构》 本文主要结合源码来介绍 hash 表的数据结构
2. redis 源码下载
Redis 源码可以点击这里下载方便查看其中定义的一些数据结构。
3. dict 数据结构
Dict 由三部分组成分别是哈希表DictHashTable、哈希节点DictEntry、字典Dict数据结构如下 dict、dictht、dictEntry 三者的数据结构关系如下
当 Dict 添加键值对时首先由 key 计算出 hash 值 h通过 h sizemask 等同取模计算提升计算速度 计算元素对应数组中的索引位置。假设哈希值 h 5则 575因此键值对存储到数组索引为5的位置。
如下图第一次插入到下标为5的数组中。
如果第二次插入的 hash 值计算后的下标也是5则第二次插入到链表的头部
4. 哈希表扩容与 rehash
当哈希表中元素越来越多导致哈希冲突增多时链表过长后会查询效率降低由查询的时间复杂度最开始的 O(1) 向 O(n) 移动。
这部分源码在 Redis 的好几个版本都有所变化主要是看看扩容的条件 1Redis 6.0 这里是直接判断 ht-used ht-size。
/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *ht) {/* If the hash table is empty expand it to the initial size,* if the table is full dobule its size. */if (ht-size 0)return dictExpand(ht, DICT_HT_INITIAL_SIZE);if (ht-used ht-size)return dictExpand(ht, ht-size*2);return DICT_OK;
}2Redis 6.2 引入哈希表的负载因子LoadFactor used/size。在每次新增键值对时都会检查负载因子。
/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{// 已经在 rehash 则返回if (dictIsRehashing(d)) return DICT_OK;// 如果为空则初始化 size 为4if (d-ht[0].size 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);// 如果负载因子 dict_force_resize_ratio(定义为5)则扩容if (d-ht[0].used d-ht[0].size (dict_can_resize ||d-ht[0].used/d-ht[0].size dict_force_resize_ratio) dictTypeExpandAllowed(d)){return dictExpand(d, d-ht[0].used 1);}return DICT_OK;
}3Redis 7.2
/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{/* Incremental rehashing already in progress. Return. */if (dictIsRehashing(d)) return DICT_OK;/* If the hash table is empty expand it to the initial size. */if (DICTHT_SIZE(d-ht_size_exp[0]) 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);/* If we reached the 1:1 ratio, and we are allowed to resize the hash* table (global setting) or we should avoid it but the ratio between* elements/buckets is over the safe threshold, we resize doubling* the number of buckets. */if (!dictTypeExpandAllowed(d))return DICT_OK;if ((dict_can_resize DICT_RESIZE_ENABLE d-ht_used[0] DICTHT_SIZE(d-ht_size_exp[0])) ||(dict_can_resize ! DICT_RESIZE_FORBID d-ht_used[0] / DICTHT_SIZE(d-ht_size_exp[0]) dict_force_resize_ratio)){return dictExpand(d, d-ht_used[0] 1);}return DICT_OK;
}下面以 Redis 6.2 源码介绍下扩容的核心方法_dictExpand
/* Expand or create the hash table,* when malloc_failed is non-NULL, itll avoid panic if malloc fails (in which case itll be set to 1).* Returns DICT_OK if expand was performed, and DICT_ERR if skipped. */
int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{if (malloc_failed) *malloc_failed 0;// 如果当前 size 大于要申请的 size或者正在 rehash则报错if (dictIsRehashing(d) || d-ht[0].used size)return DICT_ERR;dictht n; /* the new hash table */// 初始化第一个大于等于 size 的 2^n 数这个数赋值为 realsize但是不会低于4unsigned long realsize _dictNextPower(size);...// 重置 hash 表的大小和掩码并且分配新内存n.size realsize;n.sizemask realsize-1;if (malloc_failed) {n.table ztrycalloc(realsize*sizeof(dictEntry*));*malloc_failed n.table NULL;if (*malloc_failed)return DICT_ERR;} elsen.table zcalloc(realsize*sizeof(dictEntry*));n.used 0;// 第一次初始化则直接返回if (d-ht[0].table NULL) {d-ht[0] n;return DICT_OK;}// 如果不是第一次初始化说明是扩容需要 rehash将 rehashidx 置为0在后续增删改会触发 rehashd-ht[1] n;d-rehashidx 0;return DICT_OK;
}上面代码的最后只是说明了要进行 rehash 操作在 rehash 过程中
每次增、删、改、查都会把 dict.ht[0].table[rehashidx] 的值 rehash 到 dict.ht[1] 中同时 rehashidx这样渐进式地 rehash防止 rehash 阻塞主进程太久影响效率。新增操作直接写入ht[1]删、改、查会在 dict.ht[0]dict.ht[1] 依次查找。
5. 参考
《redis 从0到1完整学习 一安装初识 redis》 《redis 从0到1完整学习 二redis 常用命令》 《redis 从0到1完整学习 三redis 数据结构》 《redis 从0到1完整学习 四字符串 SDS 数据结构》 《redis 从0到1完整学习 五集合 IntSet 数据结构》
