iis服务器助手广告广告
返回顶部
首页 > 资讯 > 数据库 >Redis中内部数据结构dict的作用是什么
  • 376
分享到

Redis中内部数据结构dict的作用是什么

2024-04-02 19:04:59 376人浏览 八月长安
摘要

本篇文章为大家展示了Redis中内部数据结构dict的作用是什么,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。dict的数据结构定义为了实现增量式重哈希(incre

本篇文章为大家展示了Redis中内部数据结构dict的作用是什么,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。

dict的数据结构定义

为了实现增量式重哈希(incremental rehashing),dict的数据结构里包含两个哈希表。在重哈希期间,数据从第一个哈希表向第二个哈希表迁移。

dict的C代码定义如下(出自Redis源码dict.h):

typedef struct dictEntry {
    void *key;
    uNIOn {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;
typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; 
    int iterators; 
} dict;

为了能更清楚地展示dict的数据结构定义,我们用一张结构图来表示它。如下。

Redis中内部数据结构dict的作用是什么

结合上面的代码和结构图,可以很清楚地看出dict的结构。一个dict由如下若干项组成:

  • 一个指向dictType结构的指针(type)。它通过自定义的方式使得dict的key和value能够存储任何类型的数据。

  • 一个私有数据指针(privdata)。由调用者在创建dict的时候传进来。

  • 两个哈希表(ht[2])。只有在重哈希的过程中,ht[0]和ht[1]才都有效。而在平常情况下,只有ht[0]有效,ht[1]里面没有任何数据。上图表示的就是重哈希进行到中间某一步时的情况。

  • 当前重哈希索引(rehashidx)。如果rehashidx = -1,表示当前没有在重哈希过程中;否则,表示当前正在进行重哈希,且它的值记录了当前重哈希进行到哪一步了。

  • 当前正在进行遍历的iterator的个数。这不是我们现在讨论的重点,暂时忽略。

dictType结构包含若干函数指针,用于dict的调用者对涉及key和value的各种操作进行自定义。这些操作包含:

  • hashFunction,对key进行哈希值计算的哈希算法

  • keyDup和valDup,分别定义key和value的拷贝函数,用于在需要的时候对key和value进行深拷贝,而不仅仅是传递对象指针。

  • keyCompare,定义两个key的比较操作,在根据key进行查找时会用到。

  • keyDestructor和valDestructor,分别定义对key和value的析构函数。

私有数据指针(privdata)就是在dictType的某些操作被调用时会传回给调用者。

需要详细察看的是dictht结构。它定义一个哈希表的结构,由如下若干项组成:

  • 一个dictEntry指针数组(table)。key的哈希值最终映射到这个数组的某个位置上(对应一个bucket)。如果多个key映射到同一个位置,就发生了冲突,那么就拉出一个dictEntry链表

  • size:标识dictEntry指针数组的长度。它总是2的指数。

  • sizemask:用于将哈希值映射到table的位置索引。它的值等于(size-1),比如7, 15, 31, 63,等等,也就是用二进制表示的各个bit全1的数字。每个key先经过hashFunction计算得到一个哈希值,然后计算(哈希值 & sizemask)得到在table上的位置。相当于计算取余(哈希值 % size)。

  • used:记录dict中现有的数据个数。它与size的比值就是装载因子(load factor)。这个比值越大,哈希值冲突概率越高。

dictEntry结构中包含k, v和指向链表下一项的next指针。k是void指针,这意味着它可以指向任何类型。v是个union,当它的值是uint64_t、int64_t或double类型时,就不再需要额外的存储,这有利于减少内存碎片。当然,v也可以是void指针,以便能存储任何类型的数据。

dict的创建(dictCreate)
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));
    _dictInit(d,type,privDataPtr);
    return d;
}
int _dictInit(dict *d, dictType *type,
        void *privDataPtr)
{
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = -1;
    d->iterators = 0;
    return DICT_OK;
}
static void _dictReset(dictht *ht)
{
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

dictCreate为dict的数据结构分配空间并为各个变量赋初值。其中两个哈希表ht[0]和ht[1]起始都没有分配空间,table指针都赋为NULL。这意味着要等第一个数据插入时才会真正分配空间。

dict的查找(dictFind)
#define dictIsRehashing(d) ((d)->rehashidx != -1)
dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    unsigned int h, idx, table;
    if (d->ht[0].used + d->ht[1].used == 0) return NULL; 
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

上述dictFind的源码,根据dict当前是否正在重哈希,依次做了这么几件事:

  • 如果当前正在进行重哈希,那么将重哈希过程向前推进一步(即调用_dictRehashStep)。实际上,除了查找,插入和删除也都会触发这一动作。这就将重哈希过程分散到各个查找、插入和删除操作中去了,而不是集中在某一个操作中一次性做完。

  • 计算key的哈希值(调用dictHashKey,里面的实现会调用前面提到的hashFunction)。

  • 先在第一个哈希表ht[0]上进行查找。在table数组上定位到哈希值对应的位置(如前所述,通过哈希值与sizemask进行按位与),然后在对应的dictEntry链表上进行查找。查找的时候需要对key进行比较,这时候调用dictCompareKeys,它里面的实现会调用到前面提到的keyCompare。如果找到就返回该项。否则,进行下一步。

  • 判断当前是否在重哈希,如果没有,那么在ht[0]上的查找结果就是最终结果(没找到,返回NULL)。否则,在ht[1]上进行查找(过程与上一步相同)。

下面我们有必要看一下增量式重哈希的_dictRehashStep的实现。

static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; 
    if (!dictIsRehashing(d)) return 0;
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        
        while(de) {
            unsigned int h;
            nextde = de->next;
            
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }
    
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }
    
    return 1;
}

dictRehash每次将重哈希至少向前推进n步(除非不到n步整个重哈希就结束了),每一步都将ht[0]上某一个bucket(即一个dictEntry链表)上的每一个dictEntry移动到ht[1]上,它在ht[1]上的新位置根据ht[1]的sizemask进行重新计算。rehashidx记录了当前尚未迁移(有待迁移)的ht[0]的bucket位置。

如果dictRehash被调用的时候,rehashidx指向的bucket里一个dictEntry也没有,那么它就没有可迁移的数据。这时它尝试在ht[0].table数组中不断向后遍历,直到找到下一个存有数据的bucket位置。如果一直找不到,则最多走n*10步,本次重哈希暂告结束。

最后,如果ht[0]上的数据都迁移到ht[1]上了(即d->ht[0].used == 0),那么整个重哈希结束,ht[0]变成ht[1]的内容,而ht[1]重置为空。

根据以上对于重哈希过程的分析,我们容易看出,本文前面的dict结构图中所展示的正是rehashidx=2时的情况,前面两个bucket(ht[0].table[0]和ht[0].table[1])都已经迁移到ht[1]上去了。

dict的插入(dictAdd和dictReplace)

dictAdd插入新的一对key和value,如果key已经存在,则插入失败。

dictReplace也是插入一对key和value,不过在key存在的时候,它会更新value。

int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key);
    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}
dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    if ((index = _dicTKEyIndex(d, key)) == -1)
        return NULL;
    
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;
    
    dictSetKey(d, entry, key);
    return entry;
}
static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;
    
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

以上是dictAdd的关键实现代码。我们主要需要注意以下几点:

  • 它也会触发推进一步重哈希(_dictRehashStep)。

  • 如果正在重哈希中,它会把数据插入到ht[1];否则插入到ht[0]。

  • 在对应的bucket中插入数据的时候,总是插入到dictEntry的头部。因为新数据接下来被访问的概率可能比较高,这样再次查找它时就比较次数较少。

  • _dictKeyIndex在dict中寻找插入位置。如果不在重哈希过程中,它只查找ht[0];否则查找ht[0]和ht[1]。

  • _dictKeyIndex可能触发dict内存扩展(_dictExpandIfNeeded,它将哈希表长度扩展为原来两倍,具体请参考dict.c中源码)。

dictReplace在dictAdd基础上实现,如下:

int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, auxentry;
    
    if (dictAdd(d, key, val) == DICT_OK)
        return 1;
    
    entry = dictFind(d, key);
    
    auxentry = *entry;
    dictSetVal(d, entry, val);
    dictFreeVal(d, &auxentry);
    return 0;
}

在key已经存在的情况下,dictReplace会同时调用dictAdd和dictFind,这其实相当于两次查找过程。这里Redis的代码不够优化

dict的删除(dictDelete)

dictDelete的源码这里忽略,具体请参考dict.c。需要稍加注意的是:

  • dictDelete也会触发推进一步重哈希(_dictRehashStep)

  • 如果当前不在重哈希过程中,它只在ht[0]中查找要删除的key;否则ht[0]和ht[1]它都要查找。

  • 删除成功后会调用key和value的析构函数(keyDestructor和valDestructor)。


上述内容就是Redis中内部数据结构dict的作用是什么,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注编程网数据库频道。

您可能感兴趣的文档:

--结束END--

本文标题: Redis中内部数据结构dict的作用是什么

本文链接: https://www.lsjlt.com/news/58631.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • Redis中内部数据结构dict的作用是什么
    本篇文章为大家展示了Redis中内部数据结构dict的作用是什么,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。dict的数据结构定义为了实现增量式重哈希(incre...
    99+
    2024-04-02
  • Redis中内部数据结构intset的作用是什么
    本篇文章为大家展示了Redis中内部数据结构intset的作用是什么,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。intset数据结构简介intset顾名思义,是由...
    99+
    2024-04-02
  • Redis中内部数据结构ziplist的作用是什么
    本篇文章为大家展示了Redis中内部数据结构ziplist的作用是什么,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。什么是ziplistRedis官方对于zipli...
    99+
    2024-04-02
  • Redis中内部数据结构quicklist的作用是什么
    Redis中内部数据结构quicklist的作用是什么,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。quicklist概述Redis对外暴露的...
    99+
    2024-04-02
  • Redis中内部数据结构sds的作用是什么
    Redis中内部数据结构sds的作用是什么,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。sds的数据结构定义我们知道,在C语言...
    99+
    2024-04-02
  • Redis内部数据结构Dict的实现方法
    目录一、dict是什么二、dict数据结构1.结构梳理2. 扩容条件3. 缩容条件我们平时用Redis的时候,只是了解到了它对外的一些结构,如:string、list、set、has...
    99+
    2024-04-02
  • Redis中数据结构是什么
    这篇文章主要介绍了Redis中数据结构是什么,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。在实际开发,Redis使用会频繁,那么在使用过程中...
    99+
    2024-04-02
  • Redis 5大数据结构是什么
    这篇文章主要介绍“Redis 5大数据结构是什么”,在日常操作中,相信很多人在Redis 5大数据结构是什么问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Redis 5大数据...
    99+
    2024-04-02
  • Redis基本数据结构是什么
    这篇文章给大家分享的是有关Redis基本数据结构是什么的内容。小编觉得挺实用的,因此分享给大家做个参考。一起跟随小编过来看看吧。Redis基础数据结构Redis有5种基本数据结构:String(字符串)、l...
    99+
    2024-04-02
  • Redis数据结构原理是什么
    本篇内容介绍了“Redis数据结构原理是什么”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!RedisDbRedis服务器默认有16个数据库,...
    99+
    2023-07-05
  • Oracle数据库中的内存结构是什么
    Oracle数据库中的内存结构主要包括SGA(System Global Area)和PGA(Program Global Area...
    99+
    2024-03-02
    Oracle
  • Redis常用数据结构哈希表是什么
    这篇文章主要介绍“Redis常用数据结构哈希表是什么”,在日常操作中,相信很多人在Redis常用数据结构哈希表是什么问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Redis常用数据结构哈希表是什么”的疑惑有所...
    99+
    2023-07-06
  • redis缓存用什么数据结构
    redis 缓存支持多种数据结构,包括:字符串、哈希表、列表、集合、有序集合、地理空间数据类型、hyperloglog 和位图。每种数据结构都针对特定应用场景进行了优化,从而提高了 re...
    99+
    2024-04-02
  • Redis的六种底层数据结构是什么
    本篇内容介绍了“Redis的六种底层数据结构是什么”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!1、简单动...
    99+
    2024-04-02
  • Oracle数据库的内存结构是什么
    这篇文章主要介绍“Oracle数据库的内存结构是什么”,在日常操作中,相信很多人在Oracle数据库的内存结构是什么问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Oracle...
    99+
    2024-04-02
  • Redis数据结构之跳跃表是什么
    小编给大家分享一下Redis数据结构之跳跃表是什么,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!前言跳跃表是一种有序的数据结构,...
    99+
    2024-04-02
  • C#中的数据结构是什么
    小编给大家分享一下C#中的数据结构是什么,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!一、数组(Array)数组具有以下的特点:数组属于线性结构,在内存中是连续存...
    99+
    2023-06-29
  • Redis数据结构是怎样的
    这篇文章主要介绍“Redis数据结构是怎样的”,在日常操作中,相信很多人在Redis数据结构是怎样的问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Redis数据结构是怎样的”的疑惑有所帮助!接下来,请跟着小编...
    99+
    2023-06-27
  • redis内部运作机制是什么
    本篇内容主要讲解“redis内部运作机制是什么”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“redis内部运作机制是什么”吧!redis 就是一个数据库,不过与传统数据库不同的是 redis 的...
    99+
    2023-06-27
  • redis的五种数据类型底层数据结构是什么
    redis 提供了五种数据类型,每种类型对应特定的底层数据结构:字符串:简单动态字符串(sds),优化二进制安全字符串存储。哈希:哈希表(dict),快速键值对存储。列表:双向链表或压缩...
    99+
    2024-04-08
    键值对
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作