前段时间在B站看到一个技术视频，叫《机票报价高并发场景下的一些解决方案》。最主要的up是去哪儿科技总部，也就是我们熟悉的“去哪儿”。视频链接在这里：www.bilibili.com/video/BV1eX...当时其实是被他的图吸引了（里面的12qps应该是12kqps）：他在一个“数据”之后介绍了两个核心系统经过“压缩”操作后，分别节省了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这个方法提交了3次：在正式研究IntObjectHashMap的源码之前，先来看看只关注hashIndex的partial方法。首先这里现在的代码是这样的：我知道这个方法是获取keys数组中int类型key的下标，支持key为负数的情况。那么为什么这行代码要提交三次呢？先看第一次提交：很清楚，左边是最原始的代码，如果key是负数，那么返回的index也是负数，显然不合逻辑。于是有人提交了右边的??代码，在计算出hash值为负数的时候，加上数组的长度，最后得到一个正数。很快，提交代码的小伙伴找到了更好的写法，做了优化提交：去掉了小于零的判断。不管key%length计算出来的值是正数还是负数，都会把结果加到一个数组的长度上，然后再对数组的长度进行%运算。这确保计算出的索引必须是正数。第三次提交的代码很容易理解。代入变量：所以，最后的代码是这样的：return(key%keys.length+keys.length)%keys.length;这种写法还不如判断小于零那么优雅，有没有更多更好的表现呢？这也是一种常规的优化方案。如果看不到代码提交，就看不到方法的演变。我想表达的是：在代码提交记录中可以挖掘出很多比源代码更有价值的信息。另一个小提示给你。IntObjectHashMap接下来我们一起来探秘IntObjectHashMap。关于这个Map，其实有两个相关的类：其中IntObjectMap是一个接口。它们不依赖JDK以外的任何东西，所以当你明白了原理之后，如果你在你的业务场景中找到合适的场景，你可以把这两个类粘贴到你的项目中，一行代码都不用改，直接用就行了。研究了官方的测试用例和代码提交记录后，我选择先贴这两个类，写个代码调试一下。这样做的好处是可以随时修改源代码，方便我们进行研究。在整理IntObjectHashMap的源码之前，先看一下它的javadoc中的这几句：第一句很关键，这里解释一下IntObjectHashMap对于key冲突的解决方法：它对key采用开放寻址策略，也就是开放寻址策略.为什么要用开放寻址而不是用像HashMap这样的链表呢？这里也回答了这个问题：Tominimizethememoryfootprint，即最小化内存占用。如何减少内存使用？这个问题下面看源码的时候会讨论，不过这里有一句话：如果用链表，是不是至少要有一个next指针，维护这个东西占用空间吗？话不多说，先说开放寻址。Openaddressing是一种策略，它也分为很多实现方案，比如：LinearProbing,Quadraticprobing,Doublehashing，从上面划线部分的最后一句话可以知道IntObjectHashMap使用的是linearprobing，即线性探测。现在我们基本了解了mapIntObjectHashMap对哈希冲突的解决方案。下面我们来做一个测试用例进行实操。代码很简单，一个初始化，一个put方法：就那么几行代码，乍一看好像和HashMap没什么区别。不过仔细一想，还是发现了一点端倪。如果我们使用HashMap，初始化应该是这样的：HashMaphashMap=newHashMap<>(10);IntObjectHashMap的类定义怎么样？只有一个对象：这个对象代表地图中包含的值。那么钥匙是什么，它去了哪里？第一个问题出现了吗？查看put方法后，发现key其实是一个int类型的值：也就是说，这个类已经把key限制为int类型的值，所以在初始化的时候不能指定key的泛型类型。这个类从命名上已经明确说明了这一点：我是IntObjectHashMap，key是int，value是Object的HashMap。那我为什么用“没想到”呢？因为你看HashMap的key是什么：它是一个Object类型。也就是说，如果我们要这样初始化HashMap，是不允许的：ide会提醒你：兄弟，别闹了，这里不能放基本类型，得做一个wrapper类型进来.而我们平时编码的时候可以把int类型这样放，因为隐藏了“装箱”操作：所以有一篇古八卦问：HashMap的key可以用基本类型吗？想都别想，不行！关键，从包装类型到基本类型，这是性能优化的一个点。因为已知原始类型比包装类型占用更少的空间。下面开始说说它的构造方法，重点关注我框架的部分：首先是两个if判断，验证参数的有效性。然后看标有①的地方。从方法名来看，需要调整容量：从代码和方法的注释可以看出，这里是将容量调整为奇数。例如，如果我输入8，它会为我调整。对于9：至于为什么capacity不能是偶数，评论中给出了解释：Evencapacitiescanbreakprobing。意思是当容量为偶数时，探测就会断线，也就是我们前面说的线性探测。呃……没想到为什么偶数容量会破坏线性检测，不过这不重要，先怀疑，再梳理一下主要流程。从标②的地方可以看出这是数据初始化的操作。前面我们得到了一个容量9，这里是初始的两个数组，分别是key[]和values[]，这两个数组的容量是一样的，都是9：在构造方法中初始化两个数组后，是这样的：在构造方法中，我们主要关注capacity的变化以及key[]和values[]这两个数组。构造方法已经给你铺好了路，接下来我们看put方法，会比较顺手：put方法的代码只有几行，分析的很清楚。首先是标注①的地方，hashIndex方法是获取key[]数组中这个put的key对应的下标。这个方法在文章开头已经分析过了，我们甚至知道这个方法的演进过程，就不多说了。然后它进入一个for(;;)循环。先看标有②的地方，注意一下。此时的判断条件是value[index]==null，也就是判断计算出来的index对应的value[]数组对应的下标是否有值。前面强调了一句话，给大家画了一张图：key[]和values[]这两个数组的容量是一样的。为什么不先判断索引在key[]中是否存在呢？是的，是可以的，但是仔细想想，如果value[]对应的下标中的值为null，那么说明这个位置没有维护任何东西。key和value的位置是一一对应的，所以不需要关心key是否存在。如果value[index]==null为true，说明之前没有维护过key，直接维护对应的value，需要单独维护key[]和values[]数组。假设以我的demo代码为例，第4次循环后，是这样的：维护完成后，判断当前容量是否需要触发扩容：growSize的代码是这样的：在这个方法中，我们可以看到IntObjectHashMap的扩容机制是每次扩容2倍。还有一点：这个地方有点低，源码中的双展开肯定是需要高位运算的。使用length<<1才对。但是在展开前需要满足一个条件：size>maxSizesize，我们知道它表示当前map中放了多少个值。那么什么是maxSize？该值在构造函数中初始化。比如我的示例代码中，maxSize等于4：也就是说，如果我再插入一条数据，它就会被展开。比如我插入第五个元素后，数组的长度就变成了19：之前我们讨论的是value[index]==null为true的情况。那万一是假的呢？你来到标有③的地方。判断key[]数组索引下标处的值是否为当前key。如果是，指定覆盖。先取出原位置的值，然后直接进行覆盖操作，返回原值。这个道理很简单。但如果不是这把钥匙呢？现在是什么状况？是不是说这个key要放的索引位置已经被其他key先占了呢？这种情况是哈希冲突吗？hash冲突怎么办？然后我们来到标有③的地方，看到这个地方的注释：Conflict,keepprobing...conflict,continueprobing...continueprobing就是看当前冲突索引的下一个位置是什么。如果我要写它，那将非常简单。我闭着眼睛用脚就能敲出下一个位置，也就是index+1。但是我们看看源码是怎么写的：确实看到了index+1，但是还有一个前提，那就是index!=values.length-1。如果上面的表达式为真，很简单，使用index+1。如果上述表达式不成立，则表示当前索引是values[]数组的最后一个位置，则返回0，即返回数组的第一个下标。要触发这个场景，就需要搞一个哈希冲突的场景。我写个代码给大家看一下：上面的代码只会在计算出的下标为8的时候往IntObjectHashMap里放东西，所以在下标8处会出现hash冲突。比如100以内，下标为8的数是如下：第一次循环后是这样的：而第二次循环时，key为17，会发现下标8的地方已经被占用了：所以，得出这样的判断：returnindex=0,所以它落在这个地方：它看起来像一个戒指，对吧？是的，它是一枚戒指。但是你仔细看这个判断：每个index计算完之后，需要判断是否等于本次循环的startIndex。如果相等，说明跑了一圈没找到空位，所以会抛出“Unabletoinsert”异常。有小伙伴立马跳了出来：这不，用了一半的空间不就翻倍容量了吗？应该早就扩容了吧？我的朋友，你很机智。你的问题和我第一次看到这个地方时的问题一样。我们都是有思想的好孩子。但是注意，在抛出异常的地方，源码中有注释：CanonlyhappenifthemapwasfullatMAX_ARRAY_SIZEandcouldn'tgrow。只有当Map已满且无法继续扩展时才会发生这种情况。扩容是有上限的。我们看一下扩容的源码：最大容量是Integer.MAX_VALUE-8，说明是有上限的。但是等等，Integer.MAX_VALUE我明白了，负8怎么样？哎，反正我知道，不过先不说，不是本文的重点。有兴趣的可以自己去探索，我截图给你：验证“无法插入”怎么办？是不是很简单？源码都在我手里。两种方案，一种是修改growSize()方法的源码，修改最长长度限制为指定值，比如8。第二种方案是直接禁止扩容，注释掉这行代码：然后运行测试用例：你会发现当插入第10个值时，抛出“Unabletoinsert”异常。第10个值89是这样的，转一圈，回到startIndex：满足这个条件，所以抛出异常：(index=probeNext(index))==startIndex到这里，put方法就结束了。您还了解了它的数据结构和基本操作原理。那么你还记得我写完这篇文章后追逐的问题是什么吗？IntObjectHashMap性能更好的原因是什么？前面提到的一点是key可以使用原生的int类型，而不是包装的Integer类型。现在我要揭示第二点：价值没有乱七八糟的东西，价值是纯粹的价值。放什么就放什么，想想HashMap的结构，里面有一个Node，里面封装了Hash、key、value、next这四个属性：这部分也是IntObjectHashMap保存的，和这部分储蓄是最重要的地方。不要小看一点内存占用。面对庞大的基数，任何一个小的优化都可以被放大无数倍。不知道大家是否还记得书中的这个案例《深入理解Java虚拟机》：数据结构不当导致内存占用过大。使用Netty的LongObjectHashMap数据结构完全可以解决这个问题。你只需要改变类就可以节省大量资源。道理是一样的。加分项最后，再给大家看源码的时候一个意想不到的收获。删除实现压缩，因此对于完整映射，删除成本可以接近O(N)，这使得建议使用较小的loadFactor。Delete实现了compaction，所以对于一个fullmap，删除的代价可能接近O(N)，所以我们推荐使用较小的loadFactor。里面有两个词，compaction和loadFactor。先说一下loadFactor这个属性，它在构造函数中初始化：为什么loadFactor一定要是(0,1]之间的数字？首先我们看一下loadFactor是什么时候使用的：只有在计算maxSize的时候才会用到，是将这个系数乘以当前容量，如果这个系数大于1，那么最后计算出来的值，也就是maxSize会大于capacity，假设我们的loadFactor设置为1.5，capacity设置为21，那么计算出来的maxSize是31，已经超过了容量，没有意义，简单来说：loadFactor是用来计算maxSize的，前面说了maxSize是用来控制扩容条件的，也就是说loadFactor越小，maxSize越小越容易触发扩容，相反loadFactor越大越难扩容，loadFactor的默认值是0.5，接下来要说明的是，其中有一个词compaction之前的评论，翻译过来就叫这个东西：可以理解为一种“压缩”，但是“删除实现压缩”这句话很抽象。别担心，让我告诉你。我们先来看看删除方法：删除方法的逻辑有点复杂。如果非要靠我的描述才能给你解释清楚的话，就有点乱了。所以，我决定只给你看结果，你可以用结果反演源码。首先，前面的评论说：哥们，我建议你使用较小的loadFactor。那我就不听了，直接给你填loadFactor为1。也就是说，当地图满了的时候，往里面加东西就会触发扩容。例如，我这样初始化：newIntObjectHashMap<>(8,1);是不是说这个map当前的初始容量可以放9个元素，放第10个元素的时候就会触发扩容操作。哎，巧了，我就是想放9个元素，不想触发展开。而我的9个元素都有hash冲突。代码如下：这些值本来应该放在下标8的位置，但是经过线性检测之后，map中的数组应该是这样的：此时我们去掉key8，正常情况下应该是像这样：但是实际上面是这样的：所有之前因为哈希冲突而被置换的值都会被移回。这个过程，按照我的理解，就是评论中提到的“compaction”。上面程序的实际输出是这样的：和我之前画的图相符。不过，我要说明的是，我的代码做了微调：如果不做任何修改，输出应该是这样的：key=8不是最后一个，因为这个过程中涉及到rehash操作，如果你解释“compaction加上reHash的时候，会很复杂，会影响你对compaction的理解。另外removeAt方法的注释中提到了这个东西：这个算法其实就是我解释的”compaction前面全局搜索关键字，发现IdentityHashMap和ThreadLocal都提到了：But，注意这个but。在ThreadLocal中，使用的是“unlike”，ThreadLocal对hash冲突也采用了线性检测，但是细节还是有点不同的，我就不细说了，有兴趣的同学可以自己去探索，我只是想表达一下，这部分可以通过对比来学习。这部分的标题是“额外的一点”。因为我没有这部分在我原本的计划中，但是在查看提交记录的时候看到了这个：github.com/netty/netty...这个issue有很多讨论。基于这个讨论，它等同于IntObjectHashMap。一个大改造。比如我从这个提交记录可以知道，IntObjectHashMap之前对哈希冲突使用的是“双重哈希（Doublehashing）”策略，后来改成了线性检测。包括建议使用更小的loadFactor和removeAt中使用的算法都是基于这个改造：引用本期的一段对话：这位哥们说：我得意忘形了，我对这段代码进行了重大改进。在我看来，这不算是“重大改进”，这已经算是推翻重写了。另外，这个“我被带走了”是什么意思？英语教学，虽然晚了，但在这里：这句话要记住，托福口语考试的时候可能会考到。Netty4.1的文章开头说了，在Netty4.1中，我没有找到IntObjectHashMap这个东西。事实上，我骗了你。我找到了，只是藏得有点深。其实这篇文章我只写了int，但其实基本类型都可以按照这个思路修改，他们的代码应该是差不多的。所以在4.1中，使用了一个show操作，基于groovy封装了一次：编译完这个模板：我们会在目标目录中看到我们要找的东西：但是，仔细看编译后的IntObjectHashMap，你会发现不同的地方。比如构造方法中调整容量的方法就变成了这样：从方法名我们也知道这是为当前值找最接近的2的倍数。等等，2的倍数不是偶数吗？在4.0分支的代码中，调整容量还是要为奇数：还记得我之前提到的问题：我没有想过为什么容量为偶数会破坏线性检测？但是从这里，我们可以看出偶数的容量也是可以的。这让我很困惑。如果在4.0分支的代码中，没有写adjustCapacity方法的注释：调整给定的容量值，保证为奇数。甚至容量也可以破坏探测。我会毫不犹豫地认为这个地方可以是奇数也可以是偶数。但是他故意强调需要“奇数”，这让我有点不安。算了，学不会了，有疑惑有疑惑！
