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

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 。