换个数据结构,一不小心节约了 591 台机器! (下)

简介: 换个数据结构,一不小心节约了 591 台机器! (下)

额外一个点


最后,我再给你额外补充一个我看源码时的意外收获。

image.png

image.png

只会在计算 maxSize 的时候用到,是用当前 capacity 乘以这个系数。

如果这个系数是大于 1 的,那么最终算出来的值,也就是 maxSize 会大于 capacity。

假设我们的 loadFactor 设置为 1.5,capacity 设置为 21,那么计算出来的 maxSize 就是 31,都已经超过 capacity 了,没啥意义。

总之:loadFactor 是用来计算 maxSize 的,而前面讲了 maxSize 是用来控制扩容条件的。也就是说 loadFactor 越小,那么 maxSize 也越小,就越容易触发扩容。反之,loadFactor 越大,越不容易扩容。loadFactor 的默认值是 0.5。

接下来我来解释前面注释中有个单词 compaction,翻译过来的话叫做这玩意:

image.png

可以理解为就是一种“压缩”吧,但是“删除实现了压缩”这句话就很抽象。

不着急,我给你讲。

我们先看看删除方法:

image.png

删除方法的逻辑有点复杂,如果要靠我的描述给你说清楚的话有点费解。

所以,我决定只给你看结果,你拿着结果去反推源码吧。

首先,前面的注释中说了:哥们,我推荐你使用小一点的 loadFactor。

那么我就偏不听,直接给你把 loadFactor 拉满到 1。

也就是说当这个 map 满了之后,再往里面放东西才会触发扩容。

比如,我这样去初始化:

new IntObjectHashMap<>(8,1);

是不是说,当前这个 map 初始容量是可以放 9 个元素,当你放第 10 个元素的时候才会触发扩容的操作。

诶,巧了,我就偏偏只想放 9 个元素,我不去触发扩容。且我这 9 个元素都是存在 hash 冲突的。

代码如下:

image.png

image.png

image.png

image.png

image.png

image.png

image.png


但是,你注意这个但是啊。

在 ThreadLocal 里面,用的是“unlike”。

ThreadLocal 针对 hash 冲突也用的是线性探测,但是细节处还是有点不一样。

不细说了,有兴趣的同学自己去探索一下,我只是想表达这部分可以对比学习。

image.png

https://github.com/netty/netty/issues/2659

这个 issues 里面有很多讨论,基于这次讨论,相当于对 IntObjectHashMap 进行了一次很大的改造。

比如从这次提交记录我可以知道,在之前 IntObjectHashMap 针对 hash 冲突用的是“双重散列(Double hashing)”策略,之后才改成线性探测的。

包括使用较小的 loadFactor 这个建议、removeAt 里面采用的算法,都是基于这次改造出来的:


image.png

这个哥们说:I've got carried away,我对这段代码进行了重大改进。

在我看来,这都不算是“重大改进”了,这已经算是推翻重写了。

另外,这个“I've got carried away”啥意思?

英语教学,虽迟但到:

image.png

image.png




Netty 4.1


文章开始的地方,我说在 Netty 4.1 里面,我没有找到 IntObjectHashMap 这个东西。

其实我是骗你的,我找到了,只是藏的有点深。

image.png

image.png

image.png

还记得我前面提到的一个问题吗:我并没有考虑明白为什么偶数的容量会破坏线性探测?

但是从这里有可以看出其实偶数的容量也是可以的嘛。

这就把我给搞懵了。

要是在 4.0 分支的代码中,adjustCapacity 方法上没有这一行特意写下的注释:

Adjusts the given capacity value to ensure that it's odd. Even capacities can break probing.

我会毫不犹豫的觉得这个地方奇偶都可以。但是他刻意强调了要“奇数”,就让我有点拿不住了。

算了,学不动了,存疑存疑!

微信图片_20220429085403.png

目录
相关文章
|
Java
换个数据结构,一不小心节约了 591 台机器! (中)
换个数据结构,一不小心节约了 591 台机器! (中)
116 0
换个数据结构,一不小心节约了 591 台机器! (中)
|
缓存 Java 测试技术
换个数据结构,一不小心节约了 591 台机器! (上)
换个数据结构,一不小心节约了 591 台机器! (上)
233 0
换个数据结构,一不小心节约了 591 台机器! (上)
|
18天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
84 64
|
11天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
16 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
11天前
初步认识栈和队列
初步认识栈和队列
35 10
|
5天前
数据结构(栈与列队)
数据结构(栈与列队)
11 1
|
27天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
|
11天前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
28 3
|
9天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
37 1
|
12天前
|
存储 安全 Java
【用Java学习数据结构系列】探索栈和队列的无尽秘密
【用Java学习数据结构系列】探索栈和队列的无尽秘密
25 2