乐趣区

关于java:阿里面试官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]所有键值对都 Rehashht[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。

最初当所有键值对都 rehashht[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,其实能够发现这两者有如此多的类似点。

所以学习这类常识时,不要仅仅去背,咱们要理解其底层原理,知其然知其所以然。

帮忙材料

  1. https://redisbook.readthedocs…

欢送关注我的公众号:程序通事,取得日常干货推送。如果您对我的专题内容感兴趣,也能够关注我的博客:studyidea.cn

退出移动版