大数据&云计算|炸裂，大神图解JDK容器三大将之——哈希表 |哈希|大神|

作者：JackpotDC
链接：https://juejin.im/post/6861544032859127822
JDK容器三大将
任何一项新的技术、一种新的语言本质上都是算法+数据结构。任何技术的选型本质上都是在基于业务和硬件条件的充分理解，采用合适的数据结构、适当的算法以达到资源和效率的最优解。 Java开发亦是如此，工欲善其事，必先利其器，想要使用Java这种语言开发好程序，就必须选择合适的数据结构来进行开发。 JDK容器则是所有Java应用开发的基础，不论是业务代码，还是各种知名的Java开源项目（如异步网络框架netty、容器管理框架Spring、分布式计算框架Hadoop、搜索引擎框架Elastic Search），全都是大量在JDK容器的基础上进行开发。而JDK容器作为这些优秀开源项目的默认选择，必然有其优势，本文将分析下JDK容器三大将之哈希表。

本文插图

JDK容器三大将：List、Set、Map
HashMap介绍

所有编程语言都躲不开数据结构原理中的几种经典结构，链表、线性表、哈希表等。哈希表以其O(1) 的查找耗时在查找速度方面傲视群雄， Java中哈希表的实现即HashMap类。（原JDK中还有一个Hashtable类，由于put和get操作都加了synchronized锁导致单线程性能差，多线程又有基于分段锁的ConcurrentHashMap作为更好的选择，官方已经声明不再维护）
先来看下HashMap的继承关系图如下

本文插图

Map接口为实现类暴露了一系列方法， AbstractMap抽象类为Map的一些基础功能提供了简单实现
Cloneable表示该类支持通过java.lang.Object#clone()方法克隆， clone方法相关的细节（浅拷贝、深拷贝）读者可以搜索相关关键字阅读
Serializable接口表示该类支持Java自带序列化功能进行序列化
HashMap的数据结构
HashMap的数据结构如下图

本文插图
【大数据&云计算|炸裂，大神图解JDK容器三大将之——哈希表】

下面分别来介绍下图中的几个概念：
size ，存着HashMap当前的大小，执行hashMap.size()时直接在O(1)的时间返回哈希表的大小，如图有着三个键值对，所以size=3
modCount ，记录哈希表结构变更的次数，用于在HashMap结构变更时能够快速失败，后面会详细介绍

table ，是一个Node数组（默认大小16）， Node是HashMap的内部定义类，结构如图，保存着一对键值对。当执行map.put(k, v)命令时会根据k的哈希值映射到Node数组的某个位置，并且通过拉链法处理哈希冲突
loadFactor、threshold ，分别为装载因子（默认0.75）和阈值（Node.length * 装载因子），当HashMap的容量（即size）超过阈值时会触发rehash ，对Node数组进行扩容
HashMap的put/get操作执行过程 put()
HashMap的put操作的执行过程伪代码如下
void put(key, value) { index = hash(key) if(table[index] == null) table[index] = newNode(key, value) // 节点没有hash冲突时将该kv录入节点 else insertIntoLastNode(table[index], key, value) // 节点hash冲突时写入拉链的最后}复制代码
当hash冲突写入拉链时， HashMap有着一个常量TREEIFY_THRESHOLD=8 ，当拉链长度超过阈值后链表会升级为红黑树
上文提到过的参数threshold = Node.length * 装载因子，当put完的哈希表节点总数达到Node数组容量的0.75时会触发扩容
get()
HashMap的get操作执行过程的伪代码如下，都是经典的拉链法哈希查找的步骤

V get(key) { index = hash(key) if(table[index].key.hash == key.hash &amp&amp table[index] == key) return table[index].value // 如上图中Node[2]定位到的第一个Node ，如果对比相等，则返回value else return findNodeOrNullFromList(key) // 从拉链中查找该key的值}复制代码
查找时同样也会需要根据当前是链表还是红黑树走不同的查询逻辑
HashMap的扩容过程
接下来重点看下HashMap的扩容过程，上文提到， HashMap在put的时候，如果put完的哈希表节点总数达到threshold ，则会进行HashMap的扩容，扩容的操作过程如下图：

本文插图

resize的展开过程如下：
开辟一个新的table数组，大小是原来的2倍，即table[32]
如果当前节点没有哈希冲突，则直接重新计算该节点的table[]数组下标位置并且放入
如果当前节点是红黑树，则执行红黑树的split操作将红黑树拆成两半，如果拆分后的大小小于了TREEIFY_THRESHOLD阈值的话，降级为链表
如果当前节点是链表，则根据当前节点的hash &amp oldTable.size（如本例中为16），根据结果为0（low链表）或1（high链表）拆分为两个链表，也就是根据16的二进制位（1_0000）从右往左数第5位
low链表，即节点.hash &amp 16 == 0 ，即节点.hash第5位为0的节点保持原下标

high链表，即节点.hash &amp 16 == 1 ，即节点.hash第5位为1的节点下标=原下标+16
下图展示了扩容时链表的大致拆分过程

本文插图

HashMap的modCount以及使用注意

如前文所述， HashMap内部维护着一个成员变量modCount ，在HashMap每次进行可能影响HashMap结构的操作时都会导致modCount++（例如put、remove）这样做是因为HashMap是不支持线程安全的，如果你的代码在遍历HashMap的同时又在修改影响着HashMap的内容，必然会导致遍历出的结果不正确，与其拿到不正确结果导致后续基于这个错误结果的一系列错误，不如快速掀桌子抛出异常ConcurrentModificationException结束这次遍历，这个就是快速失败（FailFast），其它相关的异常容错机制还有failover（失效转移）、failback（失效自动回复）等，感兴趣的读者可以自行搜索。

本文插图

通过上文可以知道， modCount主要是遍历请求受到影响时的处理方式，但是我们的代码中经常会遇到一种经典的执行情况，如下

for(K key : map.keySet()) { if(key == xxx) map.remove(key) // 执行完后下一轮for循环抛出ConcurrentModificationException}复制代码

这种时候我们是在一个单线程中，我们的目的是删掉符合判断条件的节点然后继续遍历Map ，但是这样会导致代码抛出ConcurrentModificationException异常，就是因为在执行了map.remove(key)之后modCount++ ，进而导致遍历开始前记录的 expectModCount != modCount ，从而抛出异常解决的办法是通过iterator.remove()删除节点

Iterator iter = map.entrySet().iterator()while(iter.hasNext()) { Entry entry = iter.next() if(entry.key == xxx) iter.remove()}复制代码

HashMap的keySet和entrySet
在我们日常开发中经常需要对HashMap进行遍历，常用遍历方式有两种：keySet()和entrySet() 。这两种遍历方式返回的Set集合本质上都是HashMap的一个视图，这个Set本身是不存储数据的，只是它覆写了相关的iterator、contains等方法，这些方法又会去对HashMap中的table数组进行相关的查询等操作。当我们对keySet()和entrySet()返回的Set集合进行add操作时会抛出UnsupportedOperationException 。

本文插图

高性能的并发哈希表--ConcurrentHashMap

以上讨论的HashMap是JDK在Hashtable的改进上实现了高性能的单线程版的哈希实现，这在我们日常其实已经能够处理很多场景，甚至于当你所需的HashMap需要实现线程隔离的时候也可以通过ThreadLocal来实现（详见图解分析ThreadLocal的原理与应用场景）
但是某些场景的哈希表不得不在多个线程之间共享，这些线程有可能同时读某一个key ，同时改某一个key ，一个在读某个key的时候另一个却在改这个key ，面对这种情况HashMap只能掀桌子了，但是我们总还是需要一种支持多线程的高效的哈希数据结构，
ConcurrentHashMap：“没错，正式在下” 。
关于ConcurrentHashMap的高并发哈希实现原理会在下篇文章分析。
【来源：涛涛娱乐团队】
声明：转载此文是出于传递更多信息之目的。若有来源标注错误或侵犯了您的合法权益，请作者持权属证明与本网联系，我们将及时更正、删除，谢谢。邮箱地址：newmedia@xxcb.cn