运营推广的网站有哪些,网站图片相册代码,网站商城前台模板免费下载,大数据精准获客平台关注公众号#xff1a;后端技术漫谈#xff0c;技术之路不迷路~字典是一种用于保存键值对的抽象数据结构#xff0c;也被称为查找表、映射或关联表。在字典中#xff0c;一个键(key)可以和一个值(value)进行关联#xff0c;这些关联的键和值就称之为键值对。抽象数据结构后端技术漫谈技术之路不迷路~字典是一种用于保存键值对的抽象数据结构也被称为查找表、映射或关联表。在字典中一个键(key)可以和一个值(value)进行关联这些关联的键和值就称之为键值对。抽象数据结构啥意思就是可以需要实际的数据结构是实现这个功能。抽象意味着它这是实现功能的标准凡是能够完成这些功能的都可以是其实现。redis的字典字典作为一种数据结构内置在很多高级编程语言里面但是redis是基于C语言进行开发的所以没有内置这种数据结构redis只能构建自己的字典实现。字典通常可以由两种底层数据结构组成分别是线性表(数组)和hash表。而redis一般是采用hash表的方式进行构建redis字典为啥不用线性表实现字典基于用线性表实现如果我这个字典有200个键值对那么我就开辟一个长度为200的数组对这些元素进行放置。基于线性表实现的字典的优缺点很明显1、实现简单适用于任意关键码类型。2、平均检索效率低(线性时间)表长度n比较大时检索比较耗时。3、删除操作的效率比较低不太适合频繁变动的字典。字典在插入删除上的频繁让线性表无法胜任此任务。哈希如何实现字典之前写过一篇文章关于java中的hashcode解析有兴趣的读者可以回看下一些经典的hash函数和实现面试官问我hashcode 是什么和equals是兄弟吗redis字典所使用的哈希表由dict.h/dictht组成typedef struct dictht { dictEntry **table; //哈希表数组 unsigned long size; //哈希表大小即哈希表数组大小 unsigned long sizemask; //哈希表大小掩码总是等于size-1主要用于计算索引 unsigned long used; //已使用节点数即已使用键值对数}dictht;可以看到redis声明了一个结构体里面由一个哈希表数组哈希表数组大小的long值一个用于计算索引的哈希表大小掩码以及已使用的节点数构成。这个哈希表数组存放的是哈希节点dicEntry我们会将key-value键值对给它放进去。typedef struct dictEntry { void *key; //存放key值 union { void *val; //存放value值 uint64_t u64; //uint64_t整数 int64_t s64; //int64_t整数 }v; struct dictEntry *next; //指向下个哈希表节点形成链表}dictEntry;如图所示就通过next指针来将两个索引相同的键k1和k0连接在一起。Redis 中的字典由 dict.h/dict 结构表示typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当 rehash 不在进行时值为 -1 int rehashidx; /* rehashing not in progress if rehashidx -1 */} dict;可以看到字典里有一个长度为2的哈希表数组那么为啥不是三个四个甚至更多呢感觉哈希表越多不是效率更快吗其实设置2的原因在于h[0]用于存储h[1]用于当容量不足时进行扩充,更多的哈希表也用不上反而可能在扩充时要同步成为性能瓶颈。字典如何增添一个元素当要将一个新的键值对加入到字典中的时候首先要计算这个key的哈希值和索引值然后再根据这个索引值放入字典中h[0]的索引位置举个例子 对于图 4-4 所示的字典来说 如果我们要将一个键值对 k0 和 v0 添加到字典里面 那么程序会先使用语句hash dict-type-hashFunction(k0);计算键 k0 的哈希值。假设计算得出的哈希值为 8 那么程序会继续使用语句index hash dict-ht[0].sizemask 8 3 0;计算出键 k0 的索引值 0 这表示包含键值对 k0 和 v0 的节点应该被放置到哈希表数组的索引 0 位置上 如图 所示。什么时候会进行扩容按照java中hashmap的说法当负载因子loadFactor0.75的情况下会进行扩容在redis中字典里的哈希会根据以下两种情况进行扩容服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令 并且哈希表的负载因子大于等于 1 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令 并且哈希表的负载因子大于等于 5 其中哈希表的负载因子可以通过公式# 负载因子 哈希表已保存节点数量 / 哈希表大小load_factor ht[0].used / ht[0].size渐进式rehash如何实现首先要清楚为什么rehash的时候要渐进式。这就好比去参加高考肯定是初中毕业后读三年高中一点点学习高中知识后才可以参加高考这才可以取得不错的成绩。学习是循序渐进的hash也要不然中考完直接去参加高考这谁顶得住啊。Rehash操作分为两种扩展当负载因子较大时应该扩大 dictht::size 以降低平均长度加快查询速度。收缩当负载因子较小时应该减小 dictht::size 以减少对内存的浪费。当整体的数据量比较少如百八十个key-value对存储的时候hash的过程肯定耗时不会很多。但是在生产换镜下一个数据库下key-value值都是有百万级别的在进行rehash操作的时候势必会达到秒级别的运算。所以这个hash的过程不是一次性集中的完成而是分多次渐进式的完成。以下是哈希表渐进式 rehash 的详细步骤为 ht[1] 分配空间 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。在字典中维持一个索引计数器变量 rehashidx 并将它的值设置为 0 表示 rehash 工作正式开始。在 rehash 进行期间 每次对字典执行添加、删除、查找或者更新操作时 程序除了执行指定的操作以外 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] 当 rehash 工作完成之后 程序将 rehashidx 属性的值增1。随着字典操作的不断执行 最终在某个时间点上 ht[0] 的所有键值对都会被 rehash 至 ht[1] 这时程序将 rehashidx 属性的值设为 -1 表示 rehash 操作已完成。rehash的过程中有数据变化怎么办关于字典的操作无非就是四个增删改查。操作类型过程增加直接将key-value对增加到h[1]中删除先删除h[0]再删除h[1]修改直接修改h[1]查找先在h[0]中查找查询不到再到h[1]中这样就能保证redis在h[0]上是只少不多所有的记录都会被迁移到h[1]上。如何解决哈希碰撞这个问题还是我面试腾讯的时候面试官问我的原题。一开始我说了两个思路一个是无限增大线性表的容量一个是采用数组链表的方式。面试官对这两个都是构成hash的方式但是如果我的两个键值对的hashcode是一样的呢我那就可以将这个hash算法设计的复杂化比如hash里头再嵌套一层hash这样碰撞的几率就会变小了。面试官这种方法其实也是可以的那还有没有其他方法呢我....(支支吾吾中)然后面试就结束了orz其实还有另一种方法我不知道就是公共溢出区法建立一个公共溢出区假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。参考文献《redis设计与实现》https://blog.csdn.net/Time_Limit/article/details/106633269往期精彩文章阔别2020 | 我的年度总结Socket粘包问题的3种解决方案最后一种最完美一条失去where的动态SQL导致的线上故障一枚程序猿的MacBook M1使用体验半夜里有程序从虚拟机里跑出来了
