hashmap的分析网上优秀的文章有很多，个人比较推荐美团技术博客上关于hashmap的介绍。由于hashmap广为人知，我在这里就简单的分析一下，关于里面太深层次的算法也不懂。。。
我觉得要了解一个类的第一步一定是要阅读他的doc文档，当读完之后其实就对其已经有了个大概的了解了，基本的使用肯定是没有问题，接下来如果想深入的了解，则可以阅读其源码。因为hashmap的文档实在太长而且还是英文，这里就不贴出来了，希望大家有时间可以去读一下。
我们直接来看他的几个静态常量。
由上至下分别是：默认容量大小，最大容量，负载因子，链表转树的阈值，树转链表的阈值，转成树时的最小容量。我们一一分析他们的用途。
hashmap要求容量大小必须是2的幂次，这个跟他的hash算法有关。负载因子代表着hashmap的使用率，默认是0.75，默认情况下，16*0.75=12，即容量为16的hashmap只能存储12个元素。当hashmap中元素发生hash冲突时，有两种解决方案，分别是开放地址法（继续向后寻找空位置）和拉链法（形成链表），hashmap采用了第二种方案，而当元素冲突过多，会导致链表过长，这时get操作的时间复杂度就会上升为O（n），jdk采用了当链表过长将其转为红黑树的方式优化。
hashmap内部表示:
1.8之前，hashmap采用entry数组实现，1.8之后改成了使用node数组实现，这里我们只看下1.8中node类的实现。这个类比较简单，实现了Map.Entry包含kv对，这个kv即为我们存入hashmap中的kv
接下来我们看下hashmap中的俩个重要的辅助方法，一个是求hash的方法，一个是计算元素在数组中位置的方法。
hash计算方法
加了idea背景后感觉颜色提示看起来费劲所以把背景去掉了。。
具体这俩个方法为什么要这么设计，我觉得这篇博文https://blog.csdn.net/fan2012huan/article/details/51097331写的很详细，大家可以看一下。
接下来看一下hashmap的主要构造函数
我们可以主动指定负载因子和容量，注意对容量赋值的时候调用了tableSizeFor方法，该方法保证容量大小为2的幂次。这里说一下，我们知道，当hashmap中容量不足的时候会进行扩容，扩容涉及到元素的移动，链表的重组等，比较耗费性能，所以当我们预先可以估计map的容量大小时，初始化时最好可以指定容量，避免以后map频繁进行扩容影响效率。
get方法
get方法比较简单，这里主要分析一下他的分支条件。
第一个大的if：判断hashmap是否初始化以及容量是否为0，并通过(n - 1) & hash（通过此算法获取元素在node数组中的位置）取得first节点。那么什么是first节点呢？如果大家对上文有印象的话会记得hashmap处理hash冲突采用的是拉链法+红黑树，这个first就是这个拉链或者树的首节点。
第二个if：这个比较简单，通过hash与equals判断first是否为要寻找的对象
第三个if：判断是否存在hash冲突，再判断链表是否已经转为树，最后依次查找直到找到相应的对象。
最后：若以上条件不满足，返回null值。
put方法：
接上图
put方法相对于get比较复杂，也是hashmap中比较核心的一个方法。和get一样，主要分析下他的分支条件
第一个if：首先判断tab是否已经初始化，没有则进行初始化。
第二个if：通过hash值判断该元素在node数组中的位置是否存在元素，不存在则new一个。这里拓展一下hashmap中关于key为null的处理。我们知道hashmap中是可以存null的，那么他存到哪里呢？首先走第一个if创建node数组，接着来到第二个if，tab[i = (n -1) & hash]，这里的hash是使用hash（key）方法算出来的，翻看上文可知该方法当key为null的时候返回0，那么此时的i = (n -1) & hash=0，则null值被放在了node数组下标为0的位置。
else：第一个if，如果所在node数组位置上已经有元素了，通过该比较hash与equals比较元素是否相等，相等则进行替换。else if，若已经转成了红黑树，则使用putTreeVal方法进行存放。else，若是链表结构，则选择继续加长链表（加长后若到达转换为树节点的门限值，则继续将其转换为树结构）
最后判断元素数量是否超过threshold，超过则需要进行扩容，扩容方法也是一个核心方法。
我们接着来看扩容方法
说到扩容，想必大家都听说过高并发下HashMap cpu100%的问题，这个问题其实在1.8中已经修复了。这里我们先来复习下1.8以前为什么会发生这个问题。
1.7的源码懒得下载了，网图
由代码可知，e的next赋值给了newTabl[I]，这表示新元素总会被加入到链表的头部，即采用的是链表的头插法。具体为什么会导致cpu100%，网上有一幅图总结的很好，总之是产生了闭环。
网图
接下来来看1.8中的扩容方法:
这里我们注意，当oldCap>上文的类常量MAXIMUM_CAPACITY时，threshold会扩容至int的最大值。这里将新的cap与thr都变成原来哦两倍。总之，第一张图片中的代码只是为了确定扩容后tab的threshold与cap。后面的部分是真正扩容的部分，用一张图说明
jdk保证扩容时，要么元素还待在原来的索引上，要么元素待在位于原索引+oldCap处，这个具体如何实现的这里就不详细说了，跟hashmap一些列的hash处理有关。所以呢代码中的loTail和loHead就是扩容后还在原地的链表，hiTail和hiHead就是扩容后位于原索引+oldCap的链表。从图中我们可以清晰的看出，这里链表的重构采用的是尾插法。
remove方法：
和get方法类似，如果直接找到相应的元素，将其赋值给node，如果未直接找到说明元素有可能位于链表与树节点后面，分别通过相应的方法找到对应元素赋值给node。最后再通过树或链表或数组方法将该元素移除。我说的比较啰嗦，方法逻辑还是比较简明易懂的。
clear方法：
清空方法比较简单，就是将node数组中的元素引用置为null，使其能够被GC回收。
结尾
最后那，关于红黑树相关的操作没有贴出来，因为红黑树只有在上学的时候了解过，现在基本上都忘了，那个5大基本性质都记不全了。。。想详细了解的可以去翻翻算法导论。
网友评论