解剖HashMap 解剖HashMap

HashMap是Java里使用频率非常高的集合类型，基本的组成元素为Bin

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

先看签名，HashMap继承自AbstractMap，实现Map接口，可被序列/反序列化。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 static final int MAXIMUM_CAPACITY = 1 << 30; static final float DEFAULT_LOAD_FACTOR = 0.75f; static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64;

DEFAULT_INITIAL_CAPACITY: 默认初始化大小是16
MAXIMUM_CAPACITY:最大容量是2的30次幂
DEFAULT_LOAD_FACTOR:默认负载因子是0.75，代表如果容量如果超过最大容量的百分之75就会进行resize，对当前HashMap实例进行扩容
TREEIFY_THRESHOLD:顾名思义，在一个桶中大于8个Bin后从List类型转变为Tree类型，推测为自动平衡二叉树，即，红黑树
UNTREEIFY_THRESHOLD:这里考虑到在8这个临界点之间来回变动会有很大的性能开销，所以设置了这个参数，默认为6，在小于这个值的时候才会将Tree转为List
MIN_TREEIFY_CAPACITY: 桶中最小Bin容量，如果大于这个值会进行扩容，这个值最少为TREEIFY_THRESHOLD的4倍，即32

在初始化HashMap的时候，有两个因子对性能影响非常大，一个是初始化的大小，另一个是load factor，负载因子，其中0.75是一个权宜之值，即考虑了查找时间成本也照顾了空间成本。如果有很多不同的keys映射到了相同的hashcode上，那么java 1.8以前会讲这些entry全部放到同一个bucket桶下，按照链表结构来排序，1.8以后做了优化，会采用红黑树的结构在动态平衡查找效率，这里有个小知识点，就是如果这些keys是Comparable的，那么在同一个bucket下会按照排序大小来进行排序。
絮叨完后，我们先简单总结下，HashMap有这么几个很重要的概念：

Node：内部类，用于保存Entry的
Entry：一个由组成的对象，value就是具体的数据，可能是基础类型，也可能是一种对象
Bucket/Bin：中文翻译过来叫桶，桶是用来存储具体Entry的容器，可以把它理解为一个List链表，具体实现在1.7以前就是单纯的以Node为节点的单向链表，1.8以后为了更好的查找性能引入了红黑树，如果链表的长度过长，如上文提到的TREEIFY_THRESHOLD就会自动把这个桶改变成红黑树结构，如果元素被删除过多比如低于UNTREEIFY_THRESHOLD，那么就没有必要保留这种结构，因为红黑树带来的不好的地方是，除了查找效率高，插入删除有可能每次都会做左旋右旋等平衡操作，个数少的时候还是链表比较方便。
Hashcode：哈希码，有两个哈希码，一定要区分，一个是要保存或插入对象本身的hashcode，还有一个是对象要插入到HashMap中计算后得到的hashcode，下面我们通过put，get，remove等增删查操作细细地说。

好，说完HashMap的元素及类型，现在说说它的常规操作：
put 添加记录操作签名为：

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

调用的putVal，倒数第二个false代表着如果插入的key一样，则直接替换，最后一个true代表如果是false，则开启创建模式。
在插入的时候，先根据key计算出key的hash，计算方式是：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

把key的hashcode的低16位与自己的高16位做异或操作返回一个int值。
【解剖HashMap】然后用长度下标和这个hash值做与(&)操作，这样的话就相当于每次对桶做查找操作的时间复杂度始终是O(1)，听我细细来讲，这里是HashMap的一个精髓的地方：
首先HashMap的长度永远都是2的指数倍，这么做的道理就来源于二进制，只有这样，在与key的hash结果做与操作的时候才可能立刻得到一个确定的数，这个数就是桶的编号，比如，长度为16，二进制表示为10000，它再减一就是1111，那么它在和一个int类型的数字&的时候，会把所有为0的位数置为0，1则不动，从而得到一个在0~16之间的数字。看代码：

if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);

tab就是Node组成的数组，n就是数组的长度（永远为2的倍数），如果这里返回null证明该Node还没被人使用，可以创建新Node。
如果这里p不为空，证明该桶已经被人占了，hashcode出现了冲突，注意这里是put的key的hash，而不是value的hash，那么如果有冲突我们怎么解决冲突呢？常见的做法就是把这个桶变成一个链表，我们看下Node的结构就不难发现，它是内部类，并且有一个变量是next，就是用来做链表指向下一个的。
我们接着看代码：

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { ... }

首先判断当前这个桶中第一个节点，即表头的hash和要插入的key的hash一样不一样，如果一样并且两个key相等，就先暂时保留为变量e。
接下来如果发现这个桶是个红黑树结构，则进行红黑树的值插入操作，这里先暂不展开。
最后如果以上都不满足，那么会遍历这个链表，如果遇到相同的key的就做值替换，如果没有就在尾部插入一个新节点（如果超过TREEIFY_THRESHOLD则把链表转变为红黑树）。
这里有个点需要提一下，就是
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
除了先判断两个hash相等外，还要判断这两个key到底是不是相等，这么做的目的应该就是先做粗略比较，两个key的摘要一样吗，如果一样说明要么哈希算法冲突，要么这俩就是一模一样，所以才有后续继续比较值的操作。
最后的最后：

if (e != null) { // existing mapping for key V oldValue = https://www.it610.com/article/e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } ++modCount; if (++size> threshold) resize(); afterNodeInsertion(evict); return null;

判断这个e是不是不为null，不为空那么就意味着key相等，那么就可以根据参数做替换value的操作了。
++modCount，如果这个值变了会导致对map做遍历的时候fast-fail，立刻抛出ConcurrentModificationException异常
threshold就是一个阈值，大于它则需要做resize操作，即扩容。关于扩容以及扩容导致的死锁我们在下文讲。
resize()

/** * Initializes or doubles table size.If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */

resize用来初始化或者double表的大小，此处的table就是前文提到桶的引用，即那个Node数组。如果为空的话则按照指定的容量进行初始化，否则就扩容到之前的两倍，并且原有HashMap中的元素还要保留在原有的index，或者移动到2的指数倍的偏移位置。先上流程图，我们再细细讲里面的难点。

文章图片
hashmap_resize.png
其中在对老的数据做迁移的时候有一些技术点需要注意，就是怎么迁移过去。

如果这个桶中只有一个元素，不是一个链表或者红黑树的话，最简单，用这个元素的hash值和新大小减一做与&操作，得到一个数据下标index，直接放入即可。
如果这个桶下面挂的是一个树，那么把树做拆分，由于这是1.8新引入的改进，是一个优化手段，所以这里先暂不讨论。
如果桶下面是一个链表，那么由于新的容量是老的容量的两倍，先把新HashMap的桶数据，分成两半，一个叫high，高位区，另一个叫low，低位区。再用循环遍历这个桶下的每个元素，如果遍历到的元素的hash哈希值对老的容量oldCap做与&操作得到0，则证明这个元素的哈希值不需要移位，直接放入低位区即可，否则放入高位区。这里需要举个例子，假如之前a值是17，b的值是1，这两个数在容量为16的HashMap中的哈希值都是1，都会被安排到index为1的这个桶中，而在扩容到32的时候，则会把17放到高位区。
直接看核心代码：

Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }

最后有一个小知识点就是，HashMap在resize的时候可能会出现死循环，这个很好理解，比如之前桶1下的节点本来是A -> B -> C，一个并发的resize就很有可能导致死循环，比如可能会变为A -> B 而resize过程中B被移到了另一个桶并指向了C，而原来的C也做了resize操作并且指向了B，这样遍历的时候就变成了死循环。
get 查看记录 HashMap的get返回是有可能为null的，而这个null，可能代表这个key没有找到，也可能代表这个key对应的就是null，为了区分这俩可以用containsKey。

首先计算key的hash值，按照HashMap中的老办法，高位下移，与低位异或得到hash值。
做null值判断，如果匹配到了桶再做处理

(tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null

table，即HashMap内部桶数组不为空，并且长度大于0，并且tab[(n - 1) & hash]是有值的，就是说这个hash对应的桶里是有货的，至于是一个还是多个，还得接着走。

这不接着就来了个是否为多个的判断(e = first.next) != null，如果多个就遍历，最后判断是否为要取的对象还是通过e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))，即要找的key的hash值和当前的hash值一样，到这步了，那么肯定是一样的，再判断key的值是一样或者一模一样的引用，比如都是"AAA"或指向同一个实例之类的。

remove() 删除节点这里就不再赘述了，有了put和resize的功底，再理解remove就不再难了，无非就是找到这个节点，如果是单个，就直接删除，如果是链表或者树，就利用树的删除节点操作和链表的删除节点操作，干点这个节点即可。最后modCount和size都要相应的变化。如果找到并删除了则返回这个节点，如果没有则返回null。
这里最后留几个问题给自己：
1. 为什么hash的算法是这样的，要对高位做移位操作然后XOR异或？
2. 为什么再resize后，有些节点会被移到高位区，而有些节点会保留原有的位置？
下篇回答这个问题！