Redis数据结构之——hash

这篇具有很好参考价值的文章主要介绍了Redis数据结构之——hash。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

写在前面

以下内容是基于Redis 6.2.6 版本整理总结

一、Redis 数据结构hash的编码格式

Redis中hash数据类型使用了两种编码格式:ziplist(压缩列表)、hashtable(哈希表)

在redis.conf配置文件中,有以下两个参数,意思为:当节点数量小于512并且字符串的长度小于等于64时,会使用ziplist编码。

hash-max-ziplist-entries 512    
hash-max-ziplist-value 64  

二、压缩链表(ziplist)

ziplist 我们整理在下一篇文章。

三、哈希表(hashtable)

Redis中的字典(dict)使用哈希表作为的底层实现,一个哈希表里可以有多个哈希表的节点,每个节点保存字典中的一个键值对。

哈希表结构定义如下:

typedef struct dictht {
    dictEntry **table;  // 哈希表数组 每个元素都是 dictEntry 的指针,指向 dictEntry;
    unsigned long size; // 哈希表大小
    unsigned long sizemask; // 用来计算索引值 always: sizemask = size - 1
    unsigned long used; // 哈希表已有节点的数量
} dictht;

哈希表节点定义如下:
哈希表节点使用 dictEntry 结构表示,每个 dictEntry 结构都保存着一个键值对和冲突后的链表的下一个节点。

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 保存下一个 dictEntry 的地址,形成链表
} dictEntry;

其中,value 是一个联合体,可以保存多种数据类型。当value类型为 uint64_t 、int64_t 或 double时可以直接存储。其他类型需要在其他位置申请一段空间来存放,并用val指向这段空间来使用。

字典结构定义如下:

// location: dict.h
typedef struct dict {
    dictType *type;  // 指向 dictType 结构的指针
    void *privdata;  // 存储私有数据的指针,在 dictType 里面的函数会用到
    dictht ht[2];    // 两个哈希表,扩容时使用,后面会结合源码详细说明
    long rehashidx;  // 值为-1时,表示没有进行rehash,否则保存rehash执行到那个元素的数组下标 
    int16_t pauserehash; // >0 表示rehash暂停,<0 表示编码错误 
} dict;

dictType 结构定义如下

dictType 结构体定义了一系列操作key-value键值对的方法的函数指针,在实际运行时传入指定函数,就能实现预期的功能,有点运行时多态绑定的味道。

// 操作特性键值对的函数簇
typedef struct dictType {
    uint64_t (*hashFunction)(const void *key); // 计算哈希值的函数
    void *(*keyDup)(void *privdata, const void *key);  // 复制key的函数
    void *(*valDup)(void *privdata, const void *obj);  // 复制value的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 对比key的函数
    void (*keyDestructor)(void *privdata, void *key);  // 销毁key的函数
    void (*valDestructor)(void *privdata, void *obj);  // 销毁value的函数
    int (*expandAllowed)(size_t moreMem, double usedRatio); // 扩容
} dictType;

字典整体结构可以用下图来描述:
Redis数据结构之——hash

3.1 hash冲突

当两个或两个以上的键被分配到哈希数组的同一个索引上面时,我们称这些键发生了冲突。Redis的哈希表使用拉链法解决hash冲突。

3.2 负载因子

负载因子 = used / size ; used 是哈希数组存储的元素个数,size 是哈希数组的长度。
负载因子越小,冲突越小;负载因子越大,冲突越大。

3.3 rehash

随着命令的不断执行,哈希表保存的减值对会逐渐增加或者减少,为了让哈希表的负载因子维持在一个合理的范围内,当哈希表中的键值对过多或过少时,需要对哈希表的大小进行相应的扩展和收缩。而哈希表的扩展和收缩可以通过rehash来执行。rehash 就是将 ht[0] 中的节点,通过重新计算哈希值和索引值放到 ht[1] 哈希表指定的位置上。

扩容

  • 如果负载因子大于1,就会触发扩容,扩容的规则是每次翻倍;
  • 如果正在fork,执行持久化则不会扩容,但是,如果负载因子大于5,会立马扩容。

缩容
如果负载因子小于0.1,就会触发缩容。缩容的规则是:恰好包含used的2^n。

3.4 渐进式rehash

当哈希表中的元素过多时,如果一次性rehash到ht[1],庞大的计算量,可能导致redis服务在一段时间不可用。为了避免rehash对服务器带来的影响,redis分多次、慢慢的将ht[0]哈希表中的键值对rehash到ht[1]哈希表,这就是渐进式rehash。

核心思想:将整个rehash过程均摊到每次命令的执行中。

rehash的详细步骤

  1. 为 ht[1] 哈希表分配空间,此时字典同时拥有ht[0] 和 ht[1] 两个字典
  2. 将字典中的rehashidx设置为0,表示开始rehash
  3. 在rehash期间,每次对字典的增删改查,除了执行指定的命令外,还会顺带将ht[0] 中 rehashidx 索引上的所有键值对都rehash到ht[1]中,执行完rehash,rehashidx属性加一。注意:新增的键值对只能插入到ht[1]哈希表中,保证ht[0]的键值对只减不增。
  4. 随着操作的不断进行,最终ht[0]哈希表中的所有键值对都被rehash到ht[1]中。此时,将ht[0]释放掉,让ht[0] 指向ht[1],并设置rehashidx 为 -1,表示rehash完成。

四、字典常用 API

// 创建字典
dict *dictCreate(dictType *type, void *privDataPtr);
// 将键值对 key-val 插入到字典
int dictAdd(dict *d, void *key, void *val);
// 删除字典中指定 key 的键值对
int dictDelete(dict *d, const void *key);
// 获取指定key的value值
void *dictFetchValue(dict *d, const void *key);
// 将键值对 key-val 插入到字典,如果该key已经存在,则只更新val
int dictReplace(dict *d, void *key, void *val);

五、Rehash源码分析

5.1 添加元素步骤
// 1. 通过hash函数得到hash值
hash = dict->type->hashFunction(key);
// 2. 将hash值与对应哈希表的sizemask 进行 & 操作得到index
index= hash & d->ht[x].sizemask; // x = 0 or 1
// 3. 创建 dictEntry 节点,头插法插入到对应哈希表的index的位置
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
添加元素源码分析

redis使用 dictAdd() 方法往哈希表中添加元素。dictAdd 调用的是 dictAddRaw 方法,它会先通过_dictKeyIndex() 函数计算出table的index;再通过头插法将该节点插入到目标位置。

dictAdd() 函数

/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;

	// 将 val 保存到 entry 节点
    dictSetVal(d, entry, val);
    return DICT_OK;
}

dictAddRaw() 函数

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    // 计算index
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    /* Allocate the memory and store the new entry.
     * Insert the element in top, with the assumption that in a database
     * system it is more likely that recently added entries are accessed
     * more frequently. */
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    // 头插法 最快
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    // 将 key 保存在 entry 节点中
    dictSetKey(d, entry, key);
    return entry;
}

其中,在_dictKeyIndex() 函数计算index的时候,会调用 _dictExpandIfNeeded() 函数判断是否满足扩容的条件。其中有个条件是依赖于 dictTypeExpandAllowed(d) 的返回值。

_dictKeyIndex() 函数

static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;

    /* Expand the hash table if needed */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    for (table = 0; table <= 1; table++) {
        idx = hash & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                if (existing) *existing = he;
                return -1;
            }
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

_dictExpandIfNeeded() 函数

/* 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 (d->ht[0].size == 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 (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;
}

dictTypeExpandAllowed() 函数

static int dictTypeExpandAllowed(dict *d) {
    if (d->type->expandAllowed == NULL) return 1;
    return d->type->expandAllowed(
                    _dictNextPower(d->ht[0].used + 1) * sizeof(dictEntry*),
                    (double)d->ht[0].used / d->ht[0].size);
}

可以看到,如果 dictType 中没有设置 expandAllowed 函数,则直接返回真;如果设置了expandAllowed 函数,就需要执行完相应的函数才能确定是否可以扩缩容。这就是 dictType 的一个典型的应用场景。

5.2 rehash 源码分析

该函数每次从rehashidx开始的位置,固定扫描 10 个bucket,如果对应的bucket中有数据就 rehash 到 ht[1]中。

static void _dictRehashStep(dict *d) {
    if (d->pauserehash == 0) dictRehash(d,1);
}

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);

        // 跳过空的槽位
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            // 如果 经过 n*10 次,还是为空,本次rehash结束
            if (--empty_visits == 0) return 1;
        }

        // 找到要rehash的bucket
        de = d->ht[0].table[d->rehashidx];
       
        // 遍历该bucket对应的dictEntry链表
        while(de) {
            uint64_t h;

            nextde = de->next;
            // 为该dictEntry 获取在ht[1]中的index 
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;

            // 头插法 de->next 指向 ht[1].table[h]的第一个元素 (可能为NULL,可能有元素)
            de->next = d->ht[1].table[h];

            // 更新ht[1].table[h]的值指向该 dictEntry
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;

            de = nextde; // 更新de,继续遍历,直至为空
        }
        // 将ht[0]中 d->rehashidx 对应的bucket清空
        d->ht[0].table[d->rehashidx] = NULL;
        // 更新rehashidx
        d->rehashidx++;
    }

    // 检查整个ht[0]表,rehash是否完成
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table); // 释放ht[0]
        d->ht[0] = d->ht[1];   // 让ht[0] 指向 rehash后的 ht[1]
        _dictReset(&d->ht[1]); // 重置 ht[0], 以备下次rehash
        d->rehashidx = -1;
        return 0;
    }

    /* More to rehash... */
    return 1;
}

文章参考与<零声教育>的C/C++linux服务期高级架构系统教程学习文章来源地址https://www.toymoban.com/news/detail-425469.html

到了这里,关于Redis数据结构之——hash的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Redis五种数据结构底层编码结构

    Redis中的 任意数据类型的键和值都会被封装为一个RedisObject ,也叫做Redis对象,源码如下: 对象头不包含数据就已经占16字节,如果数据存string型,一个string一个对象头比较浪费空间,存大量数据时还是建议使用集合,这样可以共用一个对象头更加节省空间 Redis中会根据存储

    2024年02月11日
    浏览(38)
  • Redis常见数据结构

    Redis是一个key-value的数据库,key一般是String类型,但是value的类型多种多样 在学习Redis不同数据类型时,我们可以在官网( Redis官网)查看不同的命令: 也可以使用使用help @xxx 命令的方式查看 通用命令是部分数据类型都可以使用的指令,常见的有: KEYS:查看符合模板的所有k

    2024年02月13日
    浏览(41)
  • Redis - 底层数据结构

    Redis 的底层数据结构主要以下几种: SDS(Simple Dynamic String, 简单动态字符串) ZipList(压缩列表) QuickList(快表) Dict(字典) IntSet(整数集合) ZSkipList(跳跃表) 在 Redis 中,并不会直接使用 C 语言自带的字符串结构作为实际的存储结构,而只是将字符串作为字面量使用,大多数情况使用自

    2023年04月12日
    浏览(44)
  • Redis 数据结构详解

    Redis 数据类型分为:字符串类型、散列类型、列表类型、集合类型、有序集合类型。 Redis 这么火,它运行有多块?一台普通的笔记本电脑,可以在1秒钟内完成十万次的读写操作。 原子操作:最小的操作单位,不能继续拆分。即最小的执行单位,不会被其他命令插入。高并发

    2024年02月05日
    浏览(43)
  • redis核心数据结构

    redis下载地址:Download | Redis linux进入redis目录首先使用make命令进行c++的编译,修改redis.conf文件: 启动退出相关命令: redis五种数据结构图: 1、常用命令 2、应用场景 1)、单值缓存 2)、对象缓存 3)、分布式锁  4)、计数器 5) 、计数器 6) 、分布式系统全局序列号 1、

    2024年02月09日
    浏览(39)
  • Redis底层数据结构

    SDS全称是Simple Dynamic String,具有如下显著的特点: 常数复杂度获取字符串长度:C语言获取一个字符串的长度需要遍历整个字符串时间复杂度为O(N),而SDS在属性len中记录了字符串长度,获取字符串长度的时间复杂度为O(1)。 杜绝缓冲区溢出:C字符串在执行拼接字符串时,如果

    2024年02月13日
    浏览(41)
  • Redis的数据结构

    Redis是一款高性能的键值存储数据库,支持多种数据结构。在Redis中,数据结构是指在Redis中存储和操作数据的方式。Redis支持的数据结构包括字符串、哈希表、列表、集合和有序集合。 字符串是Redis中最基本的数据结构,可以存储任何类型的数据,包括数字、文本和二进制数

    2024年02月09日
    浏览(39)
  • redis 数据结构(二)

    整数集合是  Set 对象的底层实现之一。当一个 Set 对象只包含整数值元素,并且元素数量不时,就会使用整数集这个数据结构作为底层实现。 整数集合本质上是一块连续内存空间,它的结构定义如下: 可以看到,保存元素的容器是一个 contents 数组,虽然 contents 被声明为 i

    2024年02月09日
    浏览(38)
  • Redis数据结构简介

    对redis来说,所有的key(键)都是字符串。     1.String 字符串类型 是redis中最基本的数据类型,一个key对应一个value。   String类型是二进制安全的,意思是 redis 的 string 可以包含任何数据。如数字,字符串,jpg图片或者序列化的对象。   使用:get 、 set 、 del 、 incr、 decr 等

    2024年02月07日
    浏览(45)
  • Redis学习路线(2)—— Redis的数据结构

    一、Redis的数据结构 Redis是一个Key-Value的数据库,key一般是String类型,不过Value的类型却有很多: String: Hello World Hash: {name: \\\"jack\\\", age: 21} List: [A - B - C - C] Set: {A, B, C} SortedSet: {A: 1, B: 2, C: 3} GEO: {A: (120.3, 30.5)} BitMap: 0110110101110101011 HyperLog: 0110110101110101011 由于Redis对数据

    2024年02月15日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包