精华内容
下载资源
问答
  • redis 字典

    2020-10-13 23:11:55
    redis 字典结构 字典在一般情况下,只有ht[0]表有数据 字典解决hash冲突的方法时开链法 redis 字典rehash rehash的时机 当字典没有执行BGSAVE或者BGREWRITEAOF的时候,哈希表的负载因子大于等于1 当

    字典类图

    1、字典中保存一个函数表头列表,ht[0] 平时存储数据,ht[1]空闲,当rehash的时候ht[1]分配rehash的空间
    2、type中存储字典中的各种函数
    3、treashindex为-1,标示没有进行rehash,不为零标示rehash的进度
    在这里插入图片描述

    redis 字典结构

    字典在一般情况下,只有ht[0]表有数据
    字典解决hash冲突的方法时开链法
    在这里插入图片描述

    redis 字典rehash

    rehash的时机

    • 当字典没有执行BGSAVE或者BGREWRITEAOF的时候,哈希表的负载因子大于等于1
    • 当字典执行BGSAVE或BGREWRITEAOG的时候,哈希表负载因子大于等于5

    rehash的方式

    • 为ht[1]分配空间,如果是扩容新容量大小为第一个大于ht[0].used*2的2的n次幂,如果是缩容操作,新容量为第一个大于ht[0].used的2的n次幂
    • 将ht[0]上的值rehash到ht[1]上去
    • 当所有的值rehash完后,释放ht[0],将ht[1]设置为ht[0],重新分配ht[1]
    • rehash是渐进式的,每次用户增删改查时,将rehashidx上的所有值rehash到ht[1],然后rehashidx+=1;这个过程中增加的值直接增加到ht[1]上;这个过程中查询操作,可以先判断rehashidx,如果小于rehashidx则在旧表查,否则,在新表查。
    展开全文
  • Redis字典

    2021-03-03 14:43:48
    Redis字典使用哈希表作为底层实现。 哈希表 Redis哈希表的结构如下 /* This is our hash table structure. Every dictionary has two of this as we * implement incremental rehashing, for the old to the new

    参考《Redis设计与实现》第四章 和 Redis6 源码
    参考笔记链接

    • Redis的数据库是用字典来作为底层实现的,字典也是哈希键的底层实现之一。字典中每个键都是独一无二的。
    • Redis字典使用哈希表作为底层实现。

    哈希表

    Redis哈希表的结构如下

    /* This is our hash table structure. Every dictionary has two of this as we
     * implement incremental rehashing, for the old to the new table. */
     // 哈希表
    typedef struct dictht {
        // 哈希表数组,不是二维数组,而是dictEntry指针的一维数组。
        dictEntry **table;
    
        // 哈希表大小
        unsigned long size;
    
        // 哈希表大小掩码,用于计算索引值
        // 总是等于size - 1
        unsigned long sizemask;
    
        // 该哈希表已有节点的数量
        unsigned long used;
    } dictht;
    

    哈希表节点

    typedef struct dictEntry {
        
        // 键
        void *key;
    
        // 值
        
        // union是共用体结构,成员之间会相互影响,
        union {
            void *val;
            uint64_t u64;
            int64_t s64;
            double d;
        } v;
    
        // 指向下一个哈希表节点,形成链表
        struct dictEntry *next;
    } dictEntry;
    

    其中,对键值对的值v赋值时,该值可以是void*指针,也可以是uint64_t整数,又或者是一个int64_t整数,也可以是double类型。

    字典

    // 字典
    typedef struct dict {
        
        // 类型特定函数
        dictType *type;
    
        // 私有数据
        void *privdata;
    
        // 哈希表
        dictht ht[2];
    
        // rehash索引,指向下一个要rehash的bucket(节点链表)
        // 当rehash不在进行时,值为-1
        long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    
        // 如果>0暂停rehasing,<0表示编码错误
        int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    } dict;
    
    typedef struct dictType {
        // 计算哈希值的函数
        uint64_t (*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);
    
        // 字典内存扩展的函数
        int (*expandAllowed)(size_t moreMem, double usedRatio);
    } dictType;
    
    • Redis会为用途不同的字典设置不同的类型特定函数。
    • ht[1]一般只会在对ht[0]哈希表进行rehash时使用。

    rehash

    具体见《Redis设计与实现》第四章 4.4 rehash。

    为了让哈希表的负载因子(load factor)维持在一个合理的范围之内,需要对哈希表的大小进行相应的扩展或收缩。

    负载因子的计算:
    在这里插入图片描述

    扩展和收缩哈希表的工作可以通过执行rehash (重新散列) 操作来完成。第一步就是为ht[1]分配内存空间:
    在这里插入图片描述
    例如ht[0].used = 5,如果执行扩展操作, 5 * 2 = 10;因此ht[1]的大小就是16;如果执行收缩操作,ht[1]的大小就是8。

    渐进式rehash

    • 为了避免rehash对服务器性能造成影响(键值对数量太多),服务器分多次、渐进式地将ht[0]里地键值对慢慢地rehash到ht[1]。
    • 渐进式rehash期间,新添加的键值对一律保存到ht[1]中,ht[0]不再进行任何添加操作,保证ht[0]在这期间包含的键值对数量只减不增。

    这期间在字典里面查找一个键,程序会先到ht[0]找,再到ht[1]找,具体实现如下:

    // 根据键key查找哈希表节点
    dictEntry *dictFind(dict *d, const void *key)
    {
        dictEntry *he;
        uint64_t h, idx, table;
    
        if (dictSize(d) == 0) return NULL; /* dict is empty */
        // 如果字典正在rehash,则执行rehash的步骤。
        if (dictIsRehashing(d)) _dictRehashStep(d);
        // 得到key对应的hash值
        h = dictHashKey(d, key);
    
        /* 先在ht[0]里找,再到ht[1]里去找 */
        for (table = 0; table <= 1; table++) {
            // 根据hash值得到在表中对应的索引值
            idx = h & d->ht[table].sizemask;
            // 根据索引值得到表中对应索引值的哈希表头节点
            he = d->ht[table].table[idx];
            // he为NULL,则该hash值对应的节点不在该表中(已经迁移)
            // 否则,访问表中对应索引值的节点链表找到节点
            while(he) { 
                if (key==he->key || dictCompareKeys(d, key, he->key))
                    return he;
                he = he->next;
            }
    
            /* 如果字典已经停止rehash了,那么就意味着ht[1]为空了,
            在ht[0]没找到,也不用去ht[1]中找了*/
            if (!dictIsRehashing(d)) return NULL;
        }
        return NULL;
    }
    

    rehash过程

    /* Performs N steps of incremental rehashing. Returns 1 if there are still
     * keys to move from the old to the new hash table, otherwise 0 is returned.
     *
     * Note that a rehashing step consists in moving a bucket (that may have more
     * than one key as we use chaining) from the old to the new hash table, however
     * since part of the hash table may be composed of empty spaces, it is not
     * guaranteed that this function will rehash even a single bucket, since it
     * will visit at max N*10 empty buckets in total, otherwise the amount of
     * work it does would be unbound and the function may block for a long time. */
    
     // n为rehash的bucket数量,bucket即表索引对应的链表
     // dickFind()调用该函数每次都只rehash一个bucket,即n = 1
     // 返回0表示Rehash结束,返回1表示还得继续
    int dictRehash(dict *d, int n) {
        // 允许访问空bucket的最大数量
        // 如果n = 1, 最多只能访问10个空bucket,超过就不访问直接返回。
        // 即rehashidx最多加10 (n * 10)
        int empty_visits = n*10; /* Max number of empty buckets to visit. */
        if (!dictIsRehashing(d)) return 0;
    
        // 表的节点数量不能为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);
            // 找到非空bucket,empty_visits次数后找不到就返回了
            while(d->ht[0].table[d->rehashidx] == NULL) {
                d->rehashidx++;
                if (--empty_visits == 0) return 1;
            }
            de = d->ht[0].table[d->rehashidx];
            /* Move all the keys in this bucket from the old to the new hash HT */
            // bucket(链表)节点全部迁移,即一次迁移整个bucket(链表)
            while(de) {
                uint64_t h;
    
                nextde = de->next;
                /* Get the index in the new hash table */
                // 得到节点在ht[1]中的索引值
                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;
            // rehashidx是下一个要rehash的bucket(节点链表)的索引
            d->rehashidx++;
        }
    
        /* Check if we already rehashed the whole table... */
        // 如果ht[0]中的节点已经全部迁移
        if (d->ht[0].used == 0) {
            // 清空ht[0]的哈希表
            zfree(d->ht[0].table);
            // ht[1]赋给ht[0]
            d->ht[0] = d->ht[1];
            // 重新初始化一个ht[1]供下次rehash使用
            _dictReset(&d->ht[1]);
            // rehashidx为-1表示rehash结束
            d->rehashidx = -1;
    
            return 0;
        }
    
        /* More to rehash... */
        return 1;
    }
    
    展开全文
  • redis字典

    2021-04-03 20:04:28
    本篇文章假设读者知道HashMap的实现原理。包括 HashMap的底层数据结构:数组+链表 ...Redis字典 Redis中的字典其实跟Java中的HashMap实现都差不多,如果你研究过HashMap的底层实现原理,那么你将会很容易理解Redis.

    本篇文章假设读者知道HashMap的实现原理。包括

    1. HashMap的底层数据结构:数组+链表
    2. HashMap如何解决哈希冲突。
    3. 往HashMap放入一个键值对的时候,如何确定这个键在数组中的位置
    4. 为什么HashMap要求数组的长度为2的幂次方?
    5. HashMap如何进行rehash

    如果对于上面几点你都清楚的话,那么Redis的字典结构就会很好理解。

    Redis字典

    Redis中的字典其实跟Java中的HashMap实现都差不多,如果你研究过HashMap的底层实现原理,那么你将会很容易理解Redis的字典。

    我们都知道Redis是一个K-V键值对的数据库,因此我们很容易猜到Redis就是使用字典作为底层实现的,对数据库的增删改查,也是建立在对字典上的操作。对于键值对最大的特点就是能够以O(1)的时间复杂度查找到对应的目标。

    字典的实现

    哈希表

    哈希表的结构定义如下:

    typedef struct dictht {
        // 哈希表数组
        dictEntry **table;
        // 哈希表大小
        unsigned long size;
        // 哈希表大小掩码,用于计算索引值,总是等于 size - 1
        unsigned long sizemask;
        // 该哈希表已有节点的数量
        unsigned long used;
    } dictht;
    

    其中哈希表table是一个数组,数组中的每一个元素都是一个dictEntrydictEntry包含一个键值对,以及一个指向下一个dictEntry的指针,构成一个链表。dictEntry的结构定义如下:

    typedef struct dictEntry {
        // 键
        void *key;
        // 值,可以是一个指针、uint64_t整数,或者是一个int64_t的整数
        union {
            void *val;
            uint64_t u64;
            int64_t s64;
            double d;
        } v;
        // 指向下个哈希表节点,形成链表
        struct dictEntry *next;
    } dictEntry;
    

    哈希表dicthtdictEntry的关系如下:
    在这里插入图片描述
    如果你有研究过HashMap的实现原理,相信这张图你能很轻松的看懂。

    其实到这里就已经实现了数组+链表的数据结构了,但是为了对rehash进行优化,Redis在这基础上还使用了dict字典进一步抽象。dict的结构如下:

    typedef struct dict {
        dictType *type;
        void *privdata;
        // 内部有两个 dictht 结构
        dictht ht[2];
        //记录了rehash的状态,如果目前没有进行rehash的话,它的值为-1
        long rehashidx; 
        unsigned long iterators; /* number of iterators currently running */
    } dict;
    

    我们可以看到在dict中有一个dictht ht[2],这意味着一个dict字典拥有俩个哈希表,之所以需要俩个哈希表是因为rehash需要(下面会说到)。接下来我们看看dictdicthtdictEntry三者间的关系。
    在这里插入图片描述
    在没有进行rehash的时候,字典只会使用到一个哈希表ht[0]。

    rehash

    rehash的情况

    • 扩容:当哈希表中元素的个数等于哈希表数组的长度(由于哈希表中的数组元素是链表,所以理论上可以一直往里面放数据,只不过随着数据量的增长,查询速度会降低,这是因为链表的时间复杂度为O(n),因为为了避免链表过长,我们需要扩容),且Redis没在执行bgsave命令的时候,会触发扩容,扩容成原来数组的俩倍。或者当hash表的元素非常满,达到哈希表数组长度的5倍时,此时及时在执行bgsave命令也会强制扩容。
    • 缩容:当哈希表中的元素越来越少,直到元素个数为哈希表长度的10%的时候,程序会自动对hash表进行缩容操作,缩容不会考虑Redis是否在做bgsave

    为什么要在服务器没执行BGSAVE命令的时候才扩容?
    书上说bgsave的时候,Redis会fork一个子进程来进行持久化操作,而大多数的操作系统都会采用写时复制的技术来优化子进程的使用效率,此时如果进行哈希表扩展操作,将会造成不必要的内存写入操作。
    其实这一段我不是很理解,如果有大神知道的话,可以在评论区给我解解惑的( ̄︶ ̄)↗

    如何进行rehash

    我们之前说过,在dict中之所以有俩个哈希表ht[0]和ht[1],是因为rehash需要。现在我们就来看看这俩个哈希表在rehash过程中是如何起作用的。下面以扩容为例,过程如下:

    1. 初始化ht[1],哈希表长度为ht[0]的俩倍
    2. 将ht[0]的所有键值对进行rehash,迁移到ht[1]中
    3. 当ht[0]中的所有元素都迁移到ht[1]后,ht[0]变成空表,释放ht[0],将ht[1]设置成ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备。

    渐进式rehash

    在将ht[0]的键值对搬到ht[1]中并不是一步到位的,因为在大数据量的情况下,rehash是非常耗时的,是一个O(n)时间复杂度的操作,对于单线程的Redis来说,很难承受这种耗时的过程,因此Redis采用了渐进式的rehash小步迁移。

    rehash的步骤:

    1. 为哈希表ht[1]分配空间,此时字典持有俩个哈希表ht[0]和ht[1]
    2. 将字典中的rehashidx设置为0,表示开始进行rehash
    3. 在rehash期间,对于字段的添加、删除、查找和更新操作,程序除了会执行指定的操作意外,还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]中,当rehash工作完成,程序将rehashidx属性的值增加1
    4. 随着字典操作的不断执行,最终某个时间点上,ht[0]的所有键值都会被rehash到ht[1]中,此时将rehashidx设置成-1表示rehash结束

    渐进式rehash的好处在于,它将对键的rehash操作平摊到了对字典的每个添加、删除、查找和修改操作上,避免了集中式rehash带来的庞大计算。

    需要注意的是在rehash期间,对于字典的删除、查找、修改操作会在ht[0]和ht[1]俩个哈希表同时进行,以查找为例,程序会现在ht[0]中查找这个键是否存在,如果不存在再到ht[1]中查找。

    同时为了保证ht[0]的元素只减不增,并伴随着rehash操作最终变成空表,渐进式rehash期间,新增的键值对只能被保存在ht[1]中,而ht[0]则不再进行任何添加操作。

    参考资料:
    https://mp.weixin.qq.com/s/MT1tB2_7f5RuOxKhuEm1vQ
    Redis设计与实现

    展开全文
  • Redis 字典

    2019-03-09 20:11:33
    key value 数据结构 哈希键类型 在1 元素超过一定数目 或 2key或value中...Redis 字典通过哈希表实现 哈希表: typedef struct dictht { dictEntry **table; unsigned long size; unsigned long sizemark;...

    key value  数据结构

    哈希键类型  在1 元素超过一定数目  或  2key或value中存储的串过长时  将会由压缩列表转为字典进行存储

    Redis  字典通过哈希表实现

    哈希表:

    typedef struct dictht {
        dictEntry **table;
        unsigned long size;
        unsigned long sizemark; //等于size-1,用于计算索引值 避免-1操作
        unsigned long used; //已有节点数目
    } dictht;
    

    哈希表节点:

    typedef struct dictEntry{
        void *key;
        union{
            void *val;
            uint64_t u64;
            int64_t s64;
        } v;
        struct dictEntry *next;  //拉链解决hash冲突
    } dictEntry;

    值 v  可以为  1 指针  2 uint64_t 的整数  3 int64_t的整数

    字典:

    typedef struct dict {
    
        dictType *type; // 函数指针
        void *privdata; // 传给上述函数的可选参数
        dictht ht[2]; // 哈希表  2个的原因是进行rehash 不能一次完成,又不能阻塞需要满足可读写,用空间换时间  保证rehash时依然可读
        int trehashidx; // rehash索引   当没有rehash时值为-1
    
    }

    type是指向 dictType的指针  dictType结构体中定义了计算哈希值函数、复制键函数、复制值函数、对比键函数、销毁键函数、销毁值的函数

    为不同类型的字典  设置不同 的特定类型函数

    hash算法:

    1 调用dictType中的哈希值函数计算出当前键的哈希值

    2 hash&sizemask

    出现hash冲突的时候使用拉链法 解决hash冲突

    rehash

    哈希表在扩展或收缩的时候会进行rehash:

    扩展的条件:

    1 哈希表负载因子大于等于1且未执行BGSAVE且未执行BGREWRITEAOF命令

    2 负载因子大于等于5

    负载因子=已保存节点数目/哈希表大小

    收缩的条件:

    负载因子小于等于0.1

    渐进式rehash读写逻辑:

    查找、更新、删除:先在ht[0]上查找,没有再查找ht[1]

    增加:在ht[1]进行

    展开全文
  • Redis字典实现

    2020-04-21 13:54:47
    Redis字典 2.1 Redis字典的实现 Redis字典使用散列表最为底层实现,一个散列表里面有多个散列表节点,每个散列表节点就保存了字典中的一个键值对。 2.1.1 字典 typedef struct dict{ //类型特定函数 void *type; //...
  • Redis字典扩容

    2021-03-29 19:57:42
    Redis字典扩容/压缩——渐进式rehash字典结构集中式rehash渐进式rehash参考资料 字典结构 redis字典结构是整个数据库和hash类型数据的底层实现,是一种用于保存键值对的数据结构,redis中一个未处于扩容状态的含有两...
  • Redis字典对象

    2018-11-22 22:03:43
    Redis 字典对象 字典对象,可以对应java中的map 即保存key-value键值对的一类对象 set k1 v1 在执行完上述命令后就在数据库中产生了一个键为 k1 值为 v1的键值对 字典实现 哈希表 数组 size 掩码 已用数量 ...
  • 上篇博客我简单介绍了 redis 哈希表相关知识,本篇博客我打算在哈希表的基础上,简单整理一下 redis 字典的实现原理 字典 字典又称为符号表、关联数组,映射等,它是一种保存键值对的抽象数据结构。 键值对:字典中...
  • python redis 字典 存取

    2020-05-19 11:12:27
    python redis 字典 存取 ''' redis存取字典 ''' student = [{'name':'张三','content':'不会时间管理'},{'name':'罗志祥','content':'运动达人'}] redis.set('student',student)#key-value存 print(redis.get('...
  • Redis字典的用途 Redis中 hash结构的数据会使用到字典,整个Redis数据库中所有的key和value也组成了一个全局字典,带过期时间的key集合也是一个字典。zset集合中存储value和score值的映射关系也是通过dict结构实现...
  • Redis字典结构数据的rehash过程哈希表扩展收缩条件执行rehash的步骤扩展示例 Redis字典的数据实现方式是使用哈希表。 先解释一下Redis字典中负载因子的概念,负载因子描述字典容量的负载程度,它的计算公式为: 负载...
  • redis字典操作 import redis conn = redis.Redis(host='192.168.131.129', port=6379, password='123456') # 存值 # conn.hset('k4', 'name', 123) # conn.hset('k4', 'age', 66) # 取值 # 取单个值 #...
  • 通过上一篇对dictScan函数的分析,我们引出了两个问题,就是Redis字典在进行扩容的时候,会从size=8直接扩容到size=64吗?那段代码块真的有用吗?下面我们就通过查看源码,逐步来探索一下这个问题。 想要探索这个...
  • 文章目录1 什么是字典2 Redis 字典的特点3 Redis字典的结构3.1 哈希表节点3.2 哈希表3.3 字典结构4 哈希算法5 解决键冲突6 rehase7 哈希表的扩展与收缩8 渐进式rehash 1 什么是字典 字典,又称为符号表(symbol ...
  • Redis 字典 dict 用途有两个,首先实现数据库键空间(Key space),Redis 是一个保存键值对的数据库,数据库的键值对由字典保存,每个数据库都有一个对应的字典, 这个字典被称之为键空间(key space)。 其次字典 ...
  • Redis 字典的遍历过程逻辑比较复杂,互联网上对这一块的分析讲解非常少。我也花了不少时间对源码的细节进行了整理,将我个人对字典遍历逻辑的理解呈现给各位读者。也许读者们对字典的遍历过程有比我更好的理解,还请...
  • Redis 字典的遍历过程逻辑比较复杂,互联网上对这一块的分析讲解非常少。我也花了不少时间对源码的细节进行了整理,将我个人对字典遍历逻辑的理解呈现给各位读者。也许读者们对字典的遍历过程有比我更好的理解,还请...
  • Redis字典记录

    2020-06-22 15:54:59
    字典 ...字典作为一种数据结构内置在很多高级编程语言中,但Redis所使用的C语言并没有内置这种数据结构,因此Redis构建了自己的字典实现。 字典Redis中的应用十分广泛,比如Redis的数据库就是使用字
  • Redis 字典的遍历过程逻辑比较复杂,互联网上对这一块的分析讲解非常少。我也花了不少时间对源码的细节进行了整理,将我个人对字典遍历逻辑的理解呈现给各位读者。也许读者们对字典的遍历过程有比我更好的理解,还请...
  • Redis 字典结构 介绍 字典又称为符号表(symbol table)、关联数组(associative array)或映射(map),是一种用于保存键值对(key-value pair)的抽象数据结构。例如:redis中的所有key到value的映射,就是通过...
  • Redis字典所使用的哈希表结构定义如下: typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码,用于计算索引值 // 总是等于 size - 1 ...
  • redis字典(dict.h/dict.c)(一) redis中的字典 目前很多语言中都封装了字典,但是C语言中没有字典,所以redis自己底层实现了字典 redis的字典底层是通过hash实现的,使用的是哈希链地址法 redis字典的数据结构 ...
  • redis字典结构

    2019-05-15 06:20:10
    目录前言结构介绍解决冲突重新散列渐进式散列...今天学习redis中的字典。结构介绍字典,C语言中没有内置这种数据结构,所以redis自己构建了实现。hash类型的数据底层就是字典。哈希表:typedef struct dictht { ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,339
精华内容 2,135
关键字:

redis字典

redis 订阅