共计 8551 个字符，预计需要花费 22 分钟才能阅读完成。
你好呀，我是歪歪。
前段时间，我在 B 站上看到一个技术视频，题目叫做《机票报价高并发场景下的一些解决方案》。
up 主是 Qunar 技术大本营，也就是咱们耳熟能详的“去哪儿”。
视频链接在这里：
https://www.bilibili.com/vide…
过后其实我是被他的这个图片给吸引到了（外面的 12 qps 应该是 12k qps）：
他介绍了两个外围零碎在通过一个“数据压缩”的操作之后，别离节约了 204C 和 2160C 的服务器资源。
共计就是 2364C 的服务器资源。
如果依照个别标配的 4C8G 服务器，好家伙，这就是节约了 591 台机器啊，你想想一年就节约了多大一笔开销。
视频中介绍了几种数据压缩的计划，其中计划之一就是用了高性能汇合：
因为他们的零碎设计中大量用到“本地缓存”，而本地缓存大多就是应用 HashMap 来帮忙。
所以他们把 HashMap 换成了性能更好的 IntObjectHashMap，这个类出自 Netty。
为什么换了一个类之后，就节约了这么多的资源呢？
换言之，IntObjectHashMap 性能更好的起因是什么呢？
我也不晓得，所以我去钻研了一下。
拉源码
钻研的第一步必定是要找到对应的源码。
你能够去找个 Netty 依赖，而后找到外面的 IntObjectHashMap。
我这边本地刚好有我之前拉下来的 Netty 源码，只须要同步一下最新的代码就行了。
然而我在 4.1 分支外面找这个类的时候并没有找到，只看到了一个相干的 Benchmark 类：
点进去一看，的确没有 IntObjectHashMap 这个类：
很纳闷啊，我反正也没搞懂为啥，然而我间接就是一个不纠结了，反正我当初只是想找到一个 IntObjectHashMap 类而已。
4.1 分支如果没有的话，那么就 4.0 上看看呗：
于是我切到了 4.0 分支外面去找了一下，很顺利就找到了对应的类和测试类：
能看到测试类，其实也是我喜爱把我的项目源码拉下来的起因。如果你是通过引入 Netty 的 Maven 依赖的形式找到对应类的，就看不到测试类了。
有时候配合着测试类看源码，事倍功半，一个看源码的小技巧，送给你。
而我要拉源码的最重要的一个目标其实是这个：
能够看到这个类的提交记录，察看到这个类的演变过程，这个是很重要的。
因为一次提交绝大部分状况下对应着一次 bug 批改或者性能优化，都是咱们应该关注的中央。
比方，咱们能够看到这个小哥针对 hashIndex 办法提交了三次：
在正式钻研 IntObjectHashMap 源码之前，咱们先看看只关注 hashIndex 这个部分的办法。
首先，这个中央当初的代码是这样的：
我晓得这个办法是获取 int 类型的 key 在 keys 这个数组中的下标，反对 key 是正数的状况。
那么为啥这一行代码就提交了三次呢？
咱们先看第一次提交：
十分清晰，右边是最原始的代码，如果 key 是正数的话，那么返回的 index 就是正数，很显著不合乎逻辑。
所以有人提交了左边的代码，在算出 hash 值为正数的时候，加上数组的长度，最终失去一个负数。
很快，提交代码的哥们，发现了一个更好的写法，进行了一次优化提交：
拿掉了小于零的判断。不论 key%length 算出的值是正还是负，都将后果加上一个数组的长度后再次对数组的长度进行 % 运行。
这样保障算进去的 index 肯定是一个负数。
第三次提交的代码就很好了解了，代入变量：
所以，最终的代码就是这样的：
return (key % keys.length + keys.length) % keys.length;
这样的写法，不比判断小于零优雅的多且性能也好一点吗？而且这也是一个惯例的优化计划。
如果你看不到代码提交记录，你就看不到这个办法的演变过程。我想表白的是：在代码提交记录中能开掘到十分多比源码更有价值的信息。
又是一个小技巧，送给你。
IntObjectHashMap
接下来咱们一起摸索一下 IntObjectHashMap 的神秘。
对于这个 Map，其实有两个相干的类：
其中 IntObjectMap 是个接口。
它们不依赖除了 JDK 之外的任何货色，所以你搞懂原理之后，如果发现自己的业务场景下有适合的场景，齐全能够把这两个类粘贴到本人的我的项目中去，一行代码都不必改，拿来就用。
在钻研了官网的测试用例和代码提交记录之后，我抉择先把这两个类粘进去，本人写个代码调试一下，这样的益处就是能够随时批改其中的源码，以便咱们进行钻研。
在安顿 IntObjectHashMap 源码之前，咱们先关注一下它 javadoc 外面的这几句话：
第一句话就十分的要害，这里解释了 IntObjectHashMap 针对 key 抵触时的解决方案：
它对于 key 应用的是 open addressing 策略，也就是凋谢寻址策略。
为什么应用凋谢寻址呢，而不是采纳和 HashMap 一样挂个链表呢？
这里也答复了这个问题：To minimize the memory footprint，也就是为了最小化内存占用。
怎么就缩小了内存的占用呢？
这个问题上面看源码的时候会说，然而这里提一句：你就想想如果用链表，是不是至多得有一个 next 指针，保护这个货色是不是又得占用空间？
不多说了，说回凋谢寻址。
凋谢寻址是一种策略，该策略也分为很多种实现计划，比方：
- 线性探测办法（Linear Probing）
- 二次探测（Quadratic probing）
- 双重散列（Double hashing）
从下面划线局部的最初一句话就能够晓得，IntObjectHashMap 应用的就是 linear probing，即线性探测。
当初咱们根本理解到 IntObjectHashMap 这个 map 针对 hash 抵触时应用的解决方案了。
接下来，咱们搞个测试用例实操一把。代码很简略，就一个初始化，一个 put 办法：
就这么几行代码，一眼望去和 HashMap 如同没啥区别。然而认真一想，还是发现了一点端倪。
如果咱们用 HashMap 的话，初始化应该是这样的：
HashMap<Integer,Object> hashMap = new HashMap<>(10);
你再看看 IntObjectHashMap 这个类定义是怎么样的？
只有一个 Object：
这个 Object 代表的是 map 外面装的 value。
那么 key 是什么，去哪儿了呢？是不是第一个疑难就产生了呢？
查看 put 办法之后，我发现 key 居然就是 int 类型的值：
也就是这个类曾经限制住了 key 就是 int 类型的值，所以不能在初始化的时候指定 key 的泛型了。
这个类从命名上也曾经明确阐明这一点了：我是 IntObjectHashMap，key 是 int，value 是 Object 的 HashMap。
那么我为什么用了个“居然”呢？
因为你看看 HashMap 的 key 是个啥玩意：
是个 Object 类型。
也就是说，如果咱们想这样初始化 HashMap 是不能够的：
ide 都会揭示你：老弟，别搞事啊，你这里不能放根本类型，你得搞个包装类型进来。
而咱们平时编码的时候能这样把 int 类型放进去，是因为有“装箱”的操作被暗藏起来了：
所以才会有一道上古期间的八股文问：HashMap 的 key 能够用根本类型吗？
想也不必想，不能够！
key，从包装类型变成了根本类型，这就是一个性能优化的点。因为家喻户晓，根本类型比包装类型占用的空间更小。
接着，咱们先从它的构造方法动手，次要关注我框起来的局部：
首先进来就是两个 if 判断，对参数合法性进行了校验。
接着看标号为 ① 的中央，从办法名看是要做容量调整:
从代码和办法上的正文能够看出，这里是想把容量调整为一个奇数，比方我给进来 8，它会给我调整为 9：
至于容量为什么不能是偶数，从正文上给了一个解释：
Even capacities can break probing.
意思是容量为偶数的时候会毁坏 probing，即咱们后面提到的线性探测。
额 …
我并没有思考明确为什么偶数的容量会毁坏线性探测，然而这不重要，先存疑，接着往下梳理次要流程。
从标号为 ② 的中央能够看出这是在做数据初始化的操作。后面咱们失去了 capacity 为 9，这里就是初始两个数组，别离是 key[] 和 values[]，且这两个数组的容量是一样的，都是 9：
两个数组在构造方法中实现初始化后，是这样的：
构造方法咱们就次要关注容量的变动和 key[]、values[] 这两个数组。
构造方法给你铺垫好了，接着咱们再看 put 办法，就会比拟丝滑了：
put 办法的代码也没几行，剖析起来十分的清晰。
首先是标号为 ① 的中央，hashIndex 办法，就是获取本次 put 的 key 对应在 key[] 数组中的下标。
这个办法文章开始的时候曾经剖析过了，咱们甚至晓得这个办法的演变过程，不再多说。
而后就是进入一个 for(;;) 循环。
先看标号为 ② 的中央，你留神看，这个时候的判断条件是 value[index] == null，是判断算进去的 index 对应的 value[] 数组对应的下标是否有值。
后面我专门强调了一句，还给你画了一个图：
key[] 和 values[] 这两个数组的容量是一样的。
为什么不先判断该 index 在 key[] 中是否存在呢？
能够倒是能够，然而你想想如果 value[] 对应下标中的值是 null 的话，那么阐明这个地位上并没有保护过任何货色。key 和 value 的地位是一一对应的，所以基本就不必去关怀 key 是否存在。
如果 value[index] == null 为 true，那么阐明这个 key 之前没有被保护过，间接把对应的值保护上，且 key[] 和 values[] 数组须要别离保护。
假如以我的演示代码为例，第四次循环完结后是这样的：
保护实现后，判断一下以后的容量是否须要触发扩容：
growSize 的代码是这样的：
在这个办法外面，咱们能够看到 IntObjectHashMap 的扩容机制是一次扩充 2 倍。
额定说一句：这个中央就有点 low 了，源码外面扩充二倍必定得上位运算，用 length << 1 才对味儿嘛。
然而扩容之前须要满足一个条件：size > maxSize
size，咱们晓得是示意以后 map 外面放了几个 value。
那么 maxSize 是啥玩意呢？
这个值在构造函数外面进行的初始化。比方在我的示例代码中 maxSize 就等于 4：
也就是说，如果我再插入一个数据，它就要扩容了，比方我插入了第五个元素后，数组的长度就变成了 19：
后面咱们探讨的是 value[index] == null 为 true 的状况。那么如果是 false 呢？
就来到了标号为 ③ 的中央。
判断 key[] 数组 index 下标处的值是否是以后的这个 key。
如果是，阐明要笼罩。先把原来该地位上的值拿进去，而后间接做一个笼罩的操作，并返回原值，这个逻辑很简略。
然而，如果不是这个 key 呢？
阐明什么状况？
是不是阐明这个 key 想要放的 index 地位曾经被其余的 key 先给霸占了？
这个状况是不是就是呈现了 hash 抵触？
呈现了 hash 抵触怎么办？
那么就来到了标号为 ③ 的中央，看这个中央的正文：
Conflict, keep probing …
抵触，持续探测 …
持续探测就是看以后发生冲突的 index 的下一个地位是啥。
如果让我来写，很简略，下一个地位嘛，我闭着眼睛用脚都能敲进去，就是 index+1 嘛。
然而咱们看看源码是怎么写的：
的确看到了 index+1，然而还有一个先决条件，即 index != values.length -1。
如果上述表达式成立，很简略，采纳 index+1。
如果下面的表达式不成立，阐明以后的 index 是 values[] 数组的最初一个地位，那么就返回 0，也就是返回数组的第一个下标。
要触发这个场景，就是要搞一个 hash 抵触的场景。我写个代码给你演示一下：
下面的代码只有当算进去的下标为 8 的时候才会往 IntObjectHashMap 外面放货色，这样在下标为 8 的地位就呈现了 hash 抵触。
比方 100 之内，下标为 8 的数是这些：
第一次循环之后是这样的：
而第二次循环的时候，key 是 17，它会发现下标为 8 的中央曾经被占了：
所以，走到了这个判断中：
返回 index=0，于是它落在了这个中央：
看起来就是一个环，对不对？
是的，它就是一个环。
然而你再细细的看这个判断：
每次计算完 index 后，还要判断是否等于本次循环的 startIndex。如果相等，阐明跑了一圈了，还没找到空位子，那么就抛出“Unable to insert”异样。
有的敌人马上就跳进去了：不对啊，不是会在用了一半空间当前，以 2 倍扩容吗？应该早就在容量满之前就扩容了才对呀？
这位敌人，你很机智啊，你的疑难和我第一次看到这个中央的疑难是一样的，咱们都是心理周密的好孩子。
然而留神看，在抛出异样的中央，源码外面给了一个正文：
Can only happen if the map was full at MAX_ARRAY_SIZE and couldn’t grow.
这种状况只有 Map 曾经满了，且无奈持续扩容时才会产生。
扩容，那必定也是有一个下限才对，再看看扩容的时候的源码：
最大容量是 Integer.MAX_VALUE – 8，阐明是有下限的。
然而，等等，Integer.MAX_VALUE 我懂，减 8 是什么状况？
诶，反正我是晓得的，然而咱就是不说，不是本文重点。你要有趣味，本人去摸索，我就给你截个图完事：
如果我想要验证一下“Unable to insert”怎么办呢？
这还不简略吗？源码都在我手上呢。
两个计划，一个是批改 growSize() 办法的源码，把最长的长度限度批改为指定值，比方 8。
第二个计划是间接严禁扩容，把这行代码给它正文了：
而后把测试用例跑起来：
你会发现在插入第 10 个值的时候，抛出了“Unable to insert”异样。
第 10 个值，89，就是这样似儿的，转一圈，又走回了 startIndex：
满足这个条件，所以抛出异样：
(index = probeNext(index)) == startIndex
到这里，put 办法就讲完了。你也理解到了它的数据结构，也理解到了它的根本运行原理。
那你还记得我写这篇文章要追寻的问题是什么吗?
IntObjectHashMap 性能更好的起因是什么呢？
后面提到了一个点是 key 能够应用原生的 int 类型而不必包装的 Integer 类型。
当初我要揭示第二个点了：value 没有一些乌七八糟的货色，value 就是一个纯正的 value。你放进来是什么，就是什么。
你想想 HashMap 的构造，它外面有个 Node，封装了 Hash、key、value、next 这四个属性：
这部分货色也是 IntObjectHashMap 节约进去的，而这部分节约进去的，才是占大头的中央。
你不要看不起着一点点内存占用。在一个微小的基数背后，任何一点小小的优化，都能被放大有数倍。
不晓得你还记不记得《深刻了解 Java 虚拟机》一书外面的这个案例：
.png)
不失当的数据结构导致内存在占用过大。这个问题，就齐全能够应用 Netty 的 LongObjectHashMap 数据结构来解决，只须要换个类，就能节俭十分多的资源。
情理，是同样的情理。
额定一个点
最初，我再给你额定补充一个我看源码时的意外播种。
Deletions implement compaction, so cost of remove can approach O(N) for full maps, which makes a small loadFactor recommended.
删除实现了 compaction，所以对于一个满了的 map 来说，删除的老本可能靠近 O(N)，所以咱们举荐应用小一点的 loadFactor。
外面有两个单词，compaction 和 loadFactor。
先说 loadFactor 属性，是在构造方法外面初始化的：
为什么 loadFactor 必须是一个 (0,1] 之间的数呢？
首先要看一下 loadFactor 是在什么时候用的：
只会在计算 maxSize 的时候用到，是用以后 capacity 乘以这个系数。
如果这个系数是大于 1 的，那么最终算进去的值，也就是 maxSize 会大于 capacity。
假如咱们的 loadFactor 设置为 1.5，capacity 设置为 21，那么计算出来的 maxSize 就是 31，都曾经超过 capacity 了，没啥意义。
总之：loadFactor 是用来计算 maxSize 的，而后面讲了 maxSize 是用来管制扩容条件的。也就是说 loadFactor 越小，那么 maxSize 也越小，就越容易触发扩容。反之，loadFactor 越大，越不容易扩容。loadFactor 的默认值是 0.5。
接下来我来解释后面正文中有个单词 compaction，翻译过去的话叫做这玩意：
能够了解为就是一种“压缩”吧，然而“删除实现了压缩”这句话就很形象。
不焦急，我给你讲。
咱们先看看删除办法：
删除办法的逻辑有点简单，如果要靠我的形容给你说分明的话有点费解。
所以，我决定只给你看后果，你拿着后果去反推源码吧。
首先，后面的正文中说了：哥们，我举荐你应用小一点的 loadFactor。
那么我就偏不听，间接给你把 loadFactor 拉满到 1。
也就是说当这个 map 满了之后，再往里面放货色才会触发扩容。
比方，我这样去初始化：
new IntObjectHashMap<>(8,1);
是不是说，以后这个 map 初始容量是能够放 9 个元素，当你放第 10 个元素的时候才会触发扩容的操作。
诶，巧了，我就偏偏只想放 9 个元素，我不去触发扩容。且我这 9 个元素都是存在 hash 抵触的。
代码如下：
这些 value 原本都应该在下标为 8 的地位放下，然而通过线性探测之后，map 外面的数组应该是这个状况：
此时咱们移除 8 这个 key，失常来说应该是这样的：
然而实际上却是这样的：
会把后面因为 hash 抵触导致产生了位移的 value 全副往回挪动。
这个过程，我了解就是正文外面提到的“compaction”。
下面程序的理论输入是这样的：
合乎我后面画的图片。
然而，我要阐明的是，我的代码进行了微调：
如果不做任何批改，输入应该是这样的：
key=8 并不在最初一个，因为在这个过程外面波及到 rehash 的操作，如果在解释“compaction”的时候加上 reHash，就简单了，会影响你对于“compaction”的了解。
另外在 removeAt 办法的正文外面提到了这个货色：
这个算法，其实就是我后面解释的“compaction”。
我全局搜寻关键字，发现在 IdentityHashMap 和 ThreadLocal 外面都提到了：
然而，你留神这个然而啊。
在 ThreadLocal 外面，用的是“unlike”。
ThreadLocal 针对 hash 抵触也用的是线性探测，然而细节处还是有点不一样。
不细说了，有趣味的同学本人去摸索一下，我只是想表白这部分能够比照学习。
这一部分的题目叫做“额定一个点”。因为我原本打算中是没有这部分内容的，然而我在翻提交记录的时候看到了这个：
https://github.com/netty/nett…
这个 issues 外面有很多探讨，基于这次探讨，相当于对 IntObjectHashMap 进行了一次很大的革新。
比方从这次提交记录我能够晓得，在之前 IntObjectHashMap 针对 hash 抵触用的是“双重散列（Double hashing）”策略，之后才改成线性探测的。
包含应用较小的 loadFactor 这个倡议、removeAt 外面采纳的算法，都是基于这次革新进去的：
援用这个 issues 外面的一个对话：
这个哥们说：I’ve got carried away，我对这段代码进行了重大改良。
在我看来，这都不算是“重大改良”了，这曾经算是颠覆重写了。
另外，这个“I’ve got carried away”啥意思？
英语教学，虽迟但到：
这个短语要记住，托福书面语考试的时候可能会考。
Netty 4.1
文章开始的中央，我说在 Netty 4.1 外面，我没有找到 IntObjectHashMap 这个货色。
其实我是骗你的，我找到了，只是藏的有点深。
其实我这篇文章只写了 int，然而其实根本类型都能够基于这个思维去革新，且它们的代码都应该是大同小异的。
所以在 4.1 外面用了一个骚操作，基于 groovy 封装了一次：
要编译这个模板之后：
才会在 target 目录外面看到咱们想找的货色：
然而，你认真看编译进去的 IntObjectHashMap，又会发现一点不一样的中央。
比方构造方法外面调整 capacity 的办法变成了这样：
从办法名称咱们也晓得这里是找一个以后 value 的最近的 2 的倍数。
等等，2 的倍数，不是一个偶数吗？
在 4.0 分支的代码外面，调整容量还非得要个奇数：
还记得我后面提到的一个问题吗：我并没有思考明确为什么偶数的容量会毁坏线性探测？
然而从这里有能够看出其实偶数的容量也是能够的嘛。
这就把我给搞懵了。
要是在 4.0 分支的代码中，adjustCapacity 办法上没有这一行特意写下的正文：
Adjusts the given capacity value to ensure that it’s odd. Even capacities can break probing.
我会毫不犹豫的感觉这个中央奇偶都能够。然而他刻意强调了要“奇数”，就让我有点拿不住了。
算了，学不动了，存疑存疑！
文章首发于公众号 [why 技术], 欢送大家关注，第一工夫看到最新文章。
