刘军连治疗白癜风 https://yiyuan.99.com.cn/bjzkbdfyy/yyzj/263946.html字典是一种用于保存键值对的抽象数据结构,也被称为查找表、映射或关联表。
在字典中,一个键(key)可以和一个值(value)进行关联,这些关联的键和值就称之为键值对。
抽象数据结构,啥意思?就是可以需要实际的数据结构是实现这个功能。抽象,意味着它这是实现功能的标准,凡是能够完成这些功能的都可以是其实现。
redis的字典
字典作为一种数据结构内置在很多高级编程语言里面,但是redis是基于C语言进行开发的,所以没有内置这种数据结构,redis只能构建自己的字典实现。
字典通常可以由两种底层数据结构组成,分别是线性表(数组)和hash表。而redis一般是采用hash表的方式进行构建
redis字典为啥不用线性表实现
字典基于用线性表实现,如果我这个字典有个键值对,那么我就开辟一个长度为的数组对这些元素进行放置。
基于线性表实现的字典的优缺点很明显:
1、实现简单,适用于任意关键字类型。
2、平均检索效率低(线性时间),表长度n比较大时,检索比较耗时。
3、删除操作的效率比较低,不太适合频繁变动的字典。
字典在插入删除上的频繁让线性表无法胜任此任务。
哈希如何实现字典
之前写过一篇文章,关于java中的hashcode解析,有兴趣的读者可以回看下一些经典的hash函数和实现
面试官问我:hashcode是什么?和equals是兄弟吗?
redis字典所使用的哈希表由dict.h/dictht组成
typedefstructdictht{dictEntry**table;//哈希表数组unsignedlongsize;//哈希表大小,即哈希表数组大小unsignedlongsizemask;//哈希表大小掩码,总是等于size-1,主要用于计算索引unsignedlongused;//已使用节点数,即已使用键值对数}dictht;可以看到redis声明了一个结构体,里面由一个哈希表数组,哈希表数组大小的long值,一个用于计算索引的哈希表大小掩码以及已使用的节点数构成。
这个哈希表数组,存放的是哈希节点dicEntry,我们会将key-value键值对给它放进去。
typedefstructdictEntry{void*key;//存放key值union{void*val;//存放value值uint64_tu64;//uint64_t整数int64_ts64;//int64_t整数}v;structdictEntry*next;//指向下个哈希表节点,形成链表}dictEntry;
如图所示就通过next指针来将两个索引相同的键k1和k0连接在一起。
Redis中的字典由dict.h/dict结构表示:
typedefstructdict{//类型特定函数dictType*type;//私有数据void*privdata;//哈希表dicththt[2];//rehash索引//当rehash不在进行时,值为-1intrehashidx;/*rehashingnotinprogressifrehashidx==-1*/}dict;可以看到字典里有一个长度为2的哈希表数组,那么为啥不是三个四个甚至更多呢?感觉哈希表越多不是效率更快吗?
其实设置2的原因在于,h[0]用于存储,h[1]用于当容量不足时进行扩充,更多的哈希表也用不上,反而可能在扩充时要同步成为性能瓶颈。
字典如何增添一个元素
当要将一个新的键值对加入到字典中的时候,首先要计算这个key的哈希值和索引值,然后再根据这个索引值放入字典中h[0]的索引位置
举个例子,对于图4-4所示的字典来说,如果我们要将一个键值对k0和v0添加到字典里面,那么程序会先使用语句:
hash=dict-type-hashFunction(k0);计算机k0的哈希值。
假设计算得出的哈希值为8,那么程序会继续使用语句:
index=hashdict-ht[0].sizemask=83=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]用以存储发生冲突的记录。
如果觉得本文对你有帮助,可以点赞