北京市中科医院好不好 https://wapjbk.39.net/yiyuanzaixian/bjzkbdfyy/jzpj_p2/HashMap作为最常用的集合类之一，有必要深入浅出地了解一下。这篇文章会深入到HashMap源码，刨析它的存储结构以及工作机制。
1.HashMap的存储结构
HashMap的数据存储结构是一个NodeK,V数组，在（Java7中是EntryK,V数组，但结构相同）
存储结构主要是数组加链表，像下面的图。
2.HashMap的put()
在Java8中HashMap的put方法如下，我已经详细注释了重要代码。
举个例子，如果put的key为字母a，当前HashMap容量是初始容量16，计算出位置是1。
总结HashMapput过程。
计算key的hash值。计算方式是(key==null)？0：(h=key.hashCode())^(h16);检查当前数组是否为空，为空需要进行初始化，初始化容量是16，负载因子默认0.75。计算key在数组中的坐标。计算方式：(容量-1)hash.因为容量总是2的次方，所以-1的值的二进制总是全1。方便与hash值进行与运算。如果计算出的坐标元素为空，创建节点加入，put结束。如果当前数组容量大于负载因子设置的容量，进行扩容。如果计算出的坐标元素有值。如果next节点为空，把要加入的值和key加入next节点。如果next节点不为空，循环查看next节点。如果发现有next节点的key和要加入的key一样，对应的值替换为新值。如果循环next节点查找超过8层还不为空，把这个位置元素转换为红黑树。如果坐标上的元素值和要加入的值key完全一样，覆盖原有值。如果坐标上的元素是红黑树，把要加入的值和key加入到红黑树。如果坐标上的元素和要加入的元素不同（尾插法增加）。3.HashMap的get()
在Java8中get方法源码如下，我已经做了注释说明。
get方法流程总结。
计算key的hash值。如果存储数组不为空，且计算得到的位置上的元素不为空。继续，否则，返回Null。如果获取到的元素的key值相等，说明查找到了，返回元素。如果获取到的元素的key值不相等，查找next节点的元素。如果元素是红黑树，在红黑树中查找。不是红黑树，遍历next节点查找，找到则返回。4.HashMap的Hash规则
计算hash值inthash=key.hashCode()。与或上hash值无符号右移16位。hash=hash^(hash16)。位置计算公式index=(n-1)hash，其中n是容量。5.HashMap的初始化大小
初始化大小是16，为什么是16呢？这可能是因为每次扩容都是2倍。而选择2的次方值16作为初始容量，有利于扩容时重新Hash计算位置。为什么是16我想是一个经验值，理论上说只要是2的次方都没有问题。6.HashMap的扩容方式
负载因子是多少？负载因子是0.75。
扩容方式是什么？看源码说明。
扩容时候怎么重新确定元素在数组中的位置，我们看到是由if((e.hasholdCap)==0)确定的。
通过上面的分析也可以看出，只有在每次容量都是2的次方的情况下才能使用if((e.hasholdCap)==0)判断扩容后的位置。
7.HashMap中的红黑树
HashMap在Java8中的实现增加了红黑树，当链表节点达到8个的时候，会把链表转换成红黑树，低于6个的时候，会退回链表。究其原因是因为当节点过多时，使用红黑树可以更高效的查找到节点。毕竟红黑树是一种二叉查找树。
节点个数是多少的时候，链表会转变成红黑树。链表节点个数大于等于8时，链表会转换成树结构。节点个数是多少的时候，红黑树会退回链表。节点个数小于等于6时，树会转变成链表。为什么转变条件8和6有一个差值。如果没有差值，都是8，那么如果频繁的插入删除元素，链表个数又刚好在8徘徊，那么就会频繁的发生链表转树，树转链表。8.为啥容量都是2的幂？
容量是2的幂时，key的hash值然后
(容量-1)
确定位置时碰撞概率会比较低，因为容量为2的幂时，减1之后的二进制数为全1，这样与运算的结果就等于hasｈ值后面与1进行与运算的几位。
下面是个例子。
如果是其他的容量值，假设是9，进行与运算结果碰撞的概率就比较大。
另外，每次都是2的幂也可以让HashMap扩容时可以方便的重新计算位置。
9.快速失败（fail—fast）
HashMap遍历使用的是一种快速失败机制，它是Java非安全集合中的一种普遍机制，这种机制可以让集合在遍历时，如果有线程对集合进行了修改、删除、增加操作，会触发并发修改异常。
它的实现机制是在遍历前保存一份modCount，在每次获取下一个要遍历的元素时会对比当前的modCount和保存的modCount是否相等。
快速失败也可以看作是一种安全机制，这样在多线程操作不安全的集合时，由于快速失败的机制，会抛出异常。
10.线程安全的Map
