阿里面试官:HashMap 熟悉吧?好的,那就来聊聊 Redis 字典吧!
最近,阿粉的一个朋友出去面试,回来跟阿粉抱怨,面试官不按套路出牌,直接打乱了他的节奏。
事情是这样的,前面面试问了几个 Java 的相关问题,我朋友回答还不错,接下来面试官就问了一句:看来 Java 基础还不错,Java HashMap 你熟悉吧?
我朋友回答。工作经常用,有看过源码。
我朋友本来想着,你随便来吧,这个问题之前已经准备好了,随便问吧。
谁知道,面试官下面一句:
「那好的,我们来聊聊 Redis 字典吧。」
直接将他整蒙逼。
阿粉的朋友由于没怎么研究过 Redis 字典,所以这题就直接回答不知道了。
「当然,如果面试中真不知道,那就回答不了解,直接下一题,不要乱答。」
不过这一题,阿粉觉得还是很可惜,其实 Redis 字典基本原理与 HashMap 差不多,那我们其实可以套用这其中的原理,不求回答满分,但是怎么也可以得个及格分吧~
面试过程真要碰到这个问题,我们可以从下面三个方面回答。
-
数据结构 -
元素增加过程 -
扩容
字典数据结构
说起字典,也许大家比较陌生,但是我们都知道 Redis 本身提供 KV 查询的方式,这个 KV 就是其实通过底层就是通过字典保存。
另外,Redis 支持多种数据类型,其中一种类型为 Hash 键,也可以用来存储 KV 数据。
阿粉刚开始了解的这个数据结构的时候,本来以为这个就是使用字典实现。其实并不是这样的,初始创建 Hash 键,默认使用另外一种数据结构-「ZIPLIST」(压缩列表),以此节省内存空间。
不过一旦以下任何条件被满足,Hash 键的数据结构将会变为字典,加快查询速度。
-
哈希表中某个键或某个值的长度大于 server.hash_max_ziplist_value
(默认值为64
)。 -
压缩列表中的节点数量大于 server.hash_max_ziplist_entries
(默认值为512
)。
Redis 字典新建时默认将会创建一个哈希表数组,保存两个哈希表。
其中 ht[0]
哈希表在第一次往字典中添加键值时分配内存空间,而另一个 ht[1]
将会在下文中扩容/缩容才会进行空间分配。
字典中哈希表其实就等同于Java HashMap,我们知道 Java 采用数组加链表/红黑树的实现方式,其实哈希表也是使用类似的数据结构。
哈希表结构如下所示:
其中 table
属性是个数组, 其中数组元素保存一种 dictEntry
的结构,这个结构完全类似与 HashMap 中的 Entry
类型,这个结构存储一个 KV 键值对。
同时,为了解决 hash 碰撞的问题,dictEntry
存在一个 next 指针,指向下一个dictEntry
,这样就形成 dictEntry
的链表。
现在,我们回头对比 Java 中 HashMap,可以发现两者数据结构基本一致。
只不过 HashMap 为了解决链表过长问题导致查询变慢,JDK1.8 时在链表元素过多时采用红黑树的数据结构。
下面我们开始添加新元素,了解这其中的原理。
元素增加过程
当我们往一个新字典中添加元素,默认将会为字典中 ht[0]
哈希表分配空间,默认情况下哈希表 table 数组大小为 4(「DICT_HT_INITIAL_SIZE」)。
新添加元素的键值将会经过哈希算法,确定哈希表数组的位置,然后添加到相应的位置,如图所示:
继续增加元素,此时如果两个不同键经过哈希算法产生相同的哈希值,这样就发生了哈希碰撞。
假设现在我们哈希表中拥有是三个元素,:
我们再增加一个新元素,如果此时刚好在数组 3 号位置上发生碰撞,此时 Redis 将会采用链表的方式解决哈希碰撞。
「注意,新元素将会放在链表头结点,这么做目的是因为新增加的元素,很大概率上会被再次访问,放在头结点增加访问速度。」
这里我们在对比一下元素添加过程,可以发现 Redis 流程其实与 JDK 1.7 版本的 HashMap 类似。
当我们元素增加越来越多时,哈希碰撞情况将会越来越频繁,这就会导致链表长度过长,极端情况下 O(1) 查询效率退化成 O(N) 的查询效率。
为此,字典必须进行扩容,这样就会使触发字典 rehash 操作。
扩容
当 Redis 进行 Rehash 扩容操作,首先将会为字典没有用到 ht[1]
哈希表分配更大空间。
❝画外音:
❞ht[1]
哈希表大小为第一个大于等于ht[0].used*2
的 2^2(2的n 次方幂)
然后再将 ht[0]
中所有键值对都迁移到 ht[1]
中。
当节点全部迁移完毕,将会释放 ht[0]
占用空间,并将 ht[1]
设置为 ht[0]
。
扩容 操作需要将 ht[0]
所有键值对都 Rehash
到 ht[1]
中,如果键值过多,假设存在十亿个键值对,这样一次性的迁移,势必导致服务器会在一段时间内停止服务。
另外如果每次 rehash
都会阻塞当前操作,这样对于客户端处理非常不友好。
为了避免 rehash
对服务器的影响,Redis 采用渐进式的迁移方式,慢慢将数据迁移分散到多个操作步骤。
这个操作依赖字典中一个属性 rehashidx
,这是一个索引位置计数器,记录下一个哈希表 table 数组上元素,默认情况为值为 「-1」。
假设此时扩容前字典如图所示:
当开始 rehash 操作,rehashidx
将会被设置为 「0」 。
这个期间每次收到增加,删除,查找,更新命令,除了这些命令将会被执行以外,还会顺带将 ht[0]
哈希表在 rehashidx
位置的元素 rehash 到 ht[1]
中。
假设此时收到一个 「K3」 键的查询操作,Redis 首先执行查询操作,接着 Redis 将会为 ht[0]
哈希表上table
数组第 rehashidx
索引上所有节点都迁移到 ht[1]
中。
当操作完成之后,再将 rehashidx
属性值加 1。
最后当所有键值对都 rehash
到 ht[1]
中时,rehashidx
将会被重新设置为 -1。
虽然渐进式的 rehash 操作减少了工作量,但是却带来键值操作的复杂度。
这是因为在渐进式 rehash
操作期间,Redis 无法明确知道键到底在 ht[0]
中,还是在 ht[1]
中,所以这个时候 Redis 不得不查找两个哈希表。
以查找为例,Redis 首先查询 ht[0]
,如果没找到将会继续查找 ht[1]
,除了查询以外,更新,删除也会执行如上的操作。
添加操作其实就没这么麻烦,因为ht[0]
不会在使用,那就统一都添加到 ht[1]
中就好了。
最后我们再对比一下 Java HashMap 扩容操作,它是一个一次性操作,每次扩容需要将所有键值对都迁移到新的数组中,所以如果数据量很大,消耗时间就会久。
总结
Redis 字典使用哈希表作为底层实现,每个字典包含两个哈希表,一个平时使用,一个仅在 rehash 操作中使用。
哈希表总的来说,跟 Java HashMap 真的很类似,底层实现也是一个数组加链表数据结构。
最后,当对哈希表进行扩容操作时间,将会采用渐进性 rehash 操作,慢慢将所有键值对迁移到新哈希表中。
其实了解 Redis 字典的其中的原理,再去比较 Java HashMap ,其实可以发现这两者有如此多的相似点。
所以学习这类知识时,不要仅仅去背,我们要了解其底层原理,知其然知其所以然。
帮助资料
-
https://redisbook.readthedocs.io/en/latest/internal-datastruct/dict.html
< END >
如果大家喜欢我们的文章,欢迎大家转发,点击在看让更多的人看到。也欢迎大家热爱技术和学习的朋友加入的我们的知识星球当中,我们共同成长,进步。
SpringBoot2.x 整合 shiro 权限框架
本文分享自微信公众号 - Java极客技术(Javageektech)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
一篇文章教会你什么是Python模仿强类型
前言 Hi,各位小伙伴,你们好,今天我们来说一个Python未来趋势的并且一个好玩的东西。 我们可能多多少少都听过一句话,动态一时爽,重构火葬场。从生产角度出发,Python确实是一门很优秀的语言,但是当多人协作时,或者接手别人Python代码时,估计是有些头疼的。 Python虽然生产力高,语法强大,具备动态语言的灵活性,但是也正是因为这样,估计每个人写的代码有很大差别,那有没有什么办法尽可能的避免这种情况呢? 关于这个,Python前辈也发现这个弊病,所以,在Python3.6之后,推出了"Python类型注释"。 来吧,各位,上车吧,我们一起看一下。 环境 Python解释器 3.6+ 关于Python版本,尽可能的选择Python3.6+,因为在Python3.6+之后,在Python的异步彻底崛起,虽然目前处于测试阶段,但是我相信,用不了多久,Python一定会更加优秀。 一个简单的例子 def speak(name,age): print(name,age) speak("张三","18") 我们可以很清晰的知道,speak函数的name参数,接收的一定是个字...
- 下一篇
大厂高频面试题-连续登录问题
1 背景 对于数据开发人员来说,手写sql是比较熟悉的了,就有这样一道题,面试时需要手写sql,这就是非常经典的连续登录问题,大厂小厂都爱问,这种题说简单也不简单,说难也不难,关键是要有思路。 2 真题 hql统计连续登陆的三天及以上的用户 这个问题可以扩展到很多相似的问题:连续几个月充值会员、连续天数有商品卖出、连续打车、连续逾期。 数据提供 用户ID、登入日期 user01,2018-02-28 user01,2018-03-01 user01,2018-03-02 user01,2018-03-04 user01,2018-03-05 user01,2018-03-06 user01,2018-03-07 user02,2018-03-01 user02,2018-03-02 user02,2018-03-03 user02,2018-03-06 输出字段 +---------+--------+-------------+-------------+--+| uid | times | start_date | end_date |+---------+------...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- 设置Eclipse缩进为4个空格,增强代码规范
- CentOS8安装Docker,最新的服务器搭配容器使用
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS8编译安装MySQL8.0.19
- SpringBoot2整合Redis,开启缓存,提高访问速度
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Hadoop3单机部署,实现最简伪集群
- CentOS7,CentOS8安装Elasticsearch6.8.6