面试官:Redis中集合数据类型的内部实现方式是什么?

面试官:Redis中集合数据类型的内部实现方式是什么?

虽然已经是阳春三月,但骑着共享单车骑了这么远,还有有点冷的。我搓了搓的被冻的麻木的手,对着前台的小姐姐说:“您好,我是来面试的。”小姐姐问:“您好,您叫什么名字?”我回答:“我叫万猫学社。”小姐姐笑出了声,说到:“这名字好怪,谁给你起的啊。”我面无表情地回答:“俺爹。”小姐姐收起了笑容,说到:“跟我来吧。”我被带到了面试间等候,片刻后一个着干净满脸清秀的青年走了进来,一股男士香水的淡香扑面而来。

面试官:Redis中基本的数据类型有哪些?

我:Redis的基本数据类型有:字符串(string)、哈希(hash)、列表(list)、集合(set)、有序集合(zset)。

面试官:集合数据类型的内部实现方式是什么?

我还沉浸在上一个问题的沾沾自喜中,顿时表情凝固了,手心开始冒出冷汗。“这个。。没有太深入了解”,我支支吾吾的说到。

面试官:回去等消息吧。

这句话说的干净利落,然后就没有然后了。失败是成功的妈妈,我不气馁,决定马上恶补一下。

类型和编码

首先,整明白什么是类型?什么是编码?在Redis中使用对象来表示内存中的键和值。每个对象由一个叫做redisObject结构体表示,其中有三个属性:类型(type)、编码(encoding)、指向具体数据的指针(ptr)。

我们通常说的字符串、哈希、列表、集合、有序集合都是redisObject中的类型,实际上针对每一个数据结构在Redis内部都有自己底层的多种内部编码实现,这样是为了在合适的场景选择合适的内部编码,以达到内存空间和处理效率的平衡,这可能就是中庸之道吧。

在面试中,经常被问到的内部实现方式、内部构造、内部原理,一般指的就是redisObject中的编码

集合的编码

集合的编码有两种,分别是:整数集合(intset)和哈希表(hashtable)。

当集合中的所有元素都是整数,并且元素的个数小于set-max-intset-entries(默认为512个)时,使用整数集合作为集合的编码,集合的所有元素都保存在整数集合里面。比如:

127.0.0.1:6379> sadd one-more-set 1 2 3 4 5
(integer) 5
127.0.0.1:6379> smembers one-more-set
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
127.0.0.1:6379> object encoding one-more-set
"intset"

当集合中的所有元素不都是整数,或者元素的个数大于等于set-max-intset-entries(默认为512个)时,使用哈希表作为集合的编码,哈希表的每一个键都是字符串对象,每一个字符串包含一个集合的元素,哈希表的值全部为NULL

比如,集合中的所有元素不是整数:

127.0.0.1:6379> sadd one-more-set one more
(integer) 2
127.0.0.1:6379> smembers one-more-set
1) "more"
2) "one"
127.0.0.1:6379> object encoding one-more-set
"hashtable"

当然,了解以上细节还没能完全“征服”面试官,我们需要更深入一些:)

集合的编码转换

当一个集合是以整数集合为编码时,再向这个集合添加非整数的元素,或向这个集合添加整数的元素使元素个数过多时,就会执行集合的编码转换。

把原来保存在整数集合中的所有元素转移到哈希表中,并且把集合的编码用整数集合修改为哈希表。不过,把非整数的元素从集合中移除,或者减少整数元素的个数,以哈希表为编码的集合也不会转化为整数集合。

举个例子,我们先创建一个以整数集合为编码的集合:

127.0.0.1:6379> sadd one-more-set 1 2 3 4 5
(integer) 5
127.0.0.1:6379> smembers one-more-set
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
127.0.0.1:6379> object encoding one-more-set
"intset"

然后,再向它添加两个字符串元素,它就是转换为以哈希表为编码:

127.0.0.1:6379> sadd one-more-set one more
(integer) 2
127.0.0.16379> smembers one-more-set
1) "one"
2) "5"
3) "1"
4) "2"
5) "more"
6) "4"
7) "3"
127.0.0.1:6379> object encoding one-more-set
"hashtable"

然后,再把那两个字符串元素从集合中移除,集合的编码依然是哈希表:

127.0.0.1:6379> srem one-more-set one more
(integer) 2
127.0.0.1:6379> smembers one-more-set
1) "5"
2) "1"
3) "2"
4) "4"
5) "3"
127.0.0.1:6379> object encoding one-more-set
"hashtable"

总结

在Redis中,集合的内部实现有整数集合(intset)和哈希表(hashtable)两种,当集合中的所有元素都是整数并元素个数较少时,使用整数集合作为内部实现,否则使用哈希表作为内部实现。当条件不满足时,整数集合可以转换为哈希表,但哈希表不能转换为整数集合。

最后,谢谢你这么帅,还给我点赞关注

微信公众号:万猫学社

微信扫描二维码

关注后回复「电子书」

获取12本Java必读技术书籍

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » 面试官:Redis中集合数据类型的内部实现方式是什么?