图解JDK容器三大将之--哈希表（HashMap）

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的继承关系图如下

HashMap的继承关系图

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

HashMap的数据结构

HashMap的数据结构如下图

HashMap的数据结构

下面分别来介绍下图中的几个概念：

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 && 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 & oldTable.size（如本例中为16），根据结果为0（low链表）或1（high链表）拆分为两个链表，也就是根据16的二进制位（1_0000）从右往左数第5位

low链表，即节点.hash & 16 == 0，即节点.hash第5位为0的节点保持原下标
high链表，即节点.hash & 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。

keySet与entrySet

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

以上讨论的HashMap是JDK在Hashtable的改进上实现了高性能的单线程版的哈希实现，这在我们日常其实已经能够处理很多场景，甚至于当你所需的HashMap需要实现线程隔离的时候也可以通过ThreadLocal来实现（详见图解分析ThreadLocal的原理与应用场景）

但是某些场景的哈希表不得不在多个线程之间共享，这些线程有可能同时读某一个key，同时改某一个key，一个在读某个key的时候另一个却在改这个key，面对这种情况HashMap只能掀桌子了，但是我们总还是需要一种支持多线程的高效的哈希数据结构，

ConcurrentHashMap：“没错，正式在下”。

关于ConcurrentHashMap的高并发哈希实现原理会在下篇文章分析。

reference

[1] JDK8源码
[2] 《算法导论》

本文的分析都是基于JDK8