HashMap源码分析

oldCap0？

TreeMap： 1. 实现SortedMap，默认按键值的升序排序 2. 构造TreeMap时，key需要实现Comparable接口或传入自定义的Comparator，否则抛ClassCastException异常

tab==null?

LinkedHashMap

N

HashMap

extends

直接覆盖

容量等于预设值

key是否存在

T

Y

扩容前哈希桶数组是否有值？

NavagableMap

链表下标=8?

开始

java.util.Map

链表tail?

HashMap#resize流程图

2. hashCode的高16位和低16位异或运算算出hash值

L

nil

单结点？e.next == null

返回旧值

循环遍历链表

TreeNode?

tab[i]==null?

treeify操作转成树形结构

分别判断两个双向链表长度6？

hash & oldCap == 0?

AbstractMap

结构如下：数组 + 链表 + 红黑树(JDK1.8之后引入)- N：空结点- S：单结点- L：单链表结点- T：红黑树结点- nil：空叶子结点

JDK 1.8之后的HashMap较之前的版本有些不同，主要有以下几个不同点：1. JDK 1.7 HashMap的结构是数组+链表，1.8之后增加红黑树，当链表达到一定长度（默认8）时转成红黑树结构2. resize()算法有些不同： a. 复制结点时，1.7通过hash&newCap-1计算新桶数组下标，而1.8是hash&oldCap检查高一位的bit值，如果是0，保持下标不变，如果是1，下标右移二次幂(oldCap)位 b. 1.7在链表复制后顺序会反转，而1.8保持原有顺序

桶数组遍历结束？

根据key算出数组下标i

结束

红黑树插入结点

容量和阈值都乘以2(位运算1)

3. 取模得下标：(hash & cap - 1)

树形结点的处理

HashMap： 1. 根据hashCode存储数据，访问速度快，但遍历顺序不确定 2. 允许但只能存在一个null键，允许多个null值 3. 线程不安全，需要线程安全的情况可以synchronized或CocurrentHashMap

LinkedHashMap： 1. HashMap子类，增加head和tail字段和linkNodeLast方法记录插入顺序 2. 保存了插入顺序，因此遍历顺序和插入循序一致

Dictionary

链表遍历结束？

oldCap超出最大值130？

遍历链表结点

TreeMap

JDK 1.7 & 1.8的HashMap

下标位置+=oldCap，加入链表尾部

T(root)

Hashtable、TreeMap、HashMap、LinkedHashMap

L(head)

S

遍历结束？

Hashtable

implements

直接插入

遍历树结点

HashMap主要字段和结构

转成红黑树插入结点

阈值等于容量*负载因子(0.75)

记录结构变化次数modCount++

桶数组下标+=oldCap，插入双向链表尾部

L(tail)

链表插入

HashMap#put流程图

SorkedMap

桶数组下标不变，插入双向链表尾部

untreeify操作转成单链表结构

循环遍历旧桶数组

HashMap#index确认流程

下标位置不变，加入链表尾部

resize()

剩下的就是链表结点的处理

下标位置为空tab[i] ==null

根据hash算出新哈希桶数组的位置并插入（hash & newCap-1）

初始化的时候设置了threshold？

Hashtable： 1. 功能和HashMap类似，继承自Dictionary，实现Map接口 2. 线程安全，但并发性不如CocurrentHashMap(引入了分段锁)

1. 获取key的hashCode()

根据新容量和阈值new出新的哈希桶数组

树形结点？instanceof TreeNode

容量和阈值设置完毕

++sizethreshold