HashMap源码解析(一) HashMap源码解析(一)

1 序 【HashMap源码解析(一)】以键值对(key-value)的形式保存数据的容器，map中不允许出现重复key，并且每一个key也最多指向一个value。
Map接口提供三种集合视图，分别允许以视图的形式，查看key的set集合、value的collection集合或者key-value键值对的set集合。map中的元素次序与其在各个视图中展现出来的次序是一致的。有些特殊的实现(比如TreeMap)能保证插入元素的顺序，有些则不能(比如HashMap)。
关于对key类型限制的要求，不同类型的数据类型作为key会对的hashCode以及equals方法产生影响。有一条建议是不要使用map本身作为key传入。
关于构造函数，这里的特点与collection集合接口类似，标准来说需要提供两个构造函数。一个是默认的无参构造，另一个是以map为入参的构造函数。新创建的map实例可以方便得包含入参map里面的所有持有内容。
map接口也包含了类似于collection接口的“可选”方法，某些实现类没有实现这些方法，但是被调用到了。会抛出一样的“UnsupportedOperationException”。

相关文章推荐
- oracle-HashMap简介
- 美团点评技术博客-Hashmap
- JDK版本为1.8
注这一篇主要讲解hashmap中put方法及其扩容机制

1.2 HashMap 基于哈希表的map的一种标准实现。提供了大多数的可选操作并且允许插入null作为key或者value。注意hashMap不能保证元素的顺序，并且也不保证已有的顺序随着时间的推移不发生改变。
允许null作为key，亦允许null作为value。
hashMap对put和get操作提供稳定的性能表现。如果散列函数在bucket间正确地散列，那么迭代集合视图所消耗的时间与bucket容量和键值对数量成正比。所以，如果在意检索性能的话，就不要把hashMap的初始容量设置得太高，或者把负载因子设置得太低。
影响HashMap性能的有两个关键因素：初始容量(initial capacity)和装载因子(load factor)。容量是哈希表中桶的数量，初始容量就是哈希表创建时的容量。加载因子是散列表在其容量自动增加之前被允许得到的比例。当桶中元素的数量超过桶容量*装载因子时，就会重新散列。散列后的桶容量是当前容量的两倍。
加载因子的默认值为0.75。JDK提供的折衷值考量了时间和空间的因素。较高的装载因子值可以减少空间的开销但是会增大hashmap的数据检索开销(包括get和put)。所以设置初始容量的时候，应该考虑到要填充的数据量与当前初始容量与负载因子的关系。尽量减少重新散列的机会。
与之对应的，如果准备向一个hashMap实例填充大量的元素，那么在创建hashMap实例的时候就设置较大的初始容量，会比默认容量然后不停重散列的性能好不少。如果有产生大量重复hashcode值的key的话，就会显著降低性能。
To ameliorate impact, when keys are Comparable, this class may use comparison order among keys to help break ties.
HashMap不是线程安全的类，要想保证线程安全，可以使用

Map m = Collections.synchronizedMap（new HashMap（...））;

另外，因为hashMap不是线程安全的，对应的其视图的迭代器也都包含了fail-fast机制。与collection接口一样，不要依赖于这个机制来编写在多线程环境下的代码。多个迭代器运行的时候，不是自己迭代器做出的修改被检测到并抛出ConcurrentModificationException。
2 代码 2.1 类成员

/* ---------------- Fields -------------- */// map中的用于保存node节点的链表数组，即hashMap中的“桶” transient Node[] table; /** * Holds cached entrySet(). Note that AbstractMap fields are used * for keySet() and values(). */ transient Set> entrySet; // map中key-value键值对的数量，其长度是有规律的，为2的指数倍 transient int size; // 用于实现fail-fast机制的统计字段，记录map发生的“结构性更改”的次数。发生多线程并发修改时，对外抛出并发修改异常(ConcurrentModificationException) transient int modCount; // 重散列临界值，计算方式为桶数目*装载因子 int threshold; // 装载因子 final float loadFactor;

前面叙述中提及到的loadFactor装载因子这里不赘述了。

table 散列桶数组，注意这个数组是单向链表结构。属于HashMap的一个内部类，每个node节点保存一组key-value键值对，一个next引用以及这个node节点的hash码。
entrySet
size 当前map的数据量
modCount 用于fail-fast机制的统计字段
threshold 重散列临界值

2.2 构造函数 HashMap有4个构造函数

// 构建一个指定桶初始容量和装载因子的map。这是最灵活的构造函数 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }// 指定初始化的桶容量，装载因子为默认的0.75 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }// 默认无参构造 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }/** * Constructs a new HashMap with the same mappings as the * specified Map.The HashMap is created with * default load factor (0.75) and an initial capacity sufficient to * hold the mappings in the specified Map. * * @paramm the map whose mappings are to be placed in this map * @throwsNullPointerException if the specified map is null */ public HashMap(Map m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

默认的无参构造会初始化装载因子为默认值0.75
入参为初始容量initialCapacity的构造函数会设置装载因子为默认值和初始化hashMap的容量
入参为初始容量initialCapacity和loadFactor的会同时设置指定的值
创建一个新的HashMap实例并将入参map的元素填入，这个方法后面会再次关注

2.3 部分方法 hashMap操作流程中的一系列难点都会体现在插入值的过程中，所以我们首先剖析一下put方法的完整流程：

文章图片
structure.jpg

// 将一组key-value键值对保存到map中，如果这个key在map中已经存在，那么新插入的value值将会覆盖已有的value值。其返回值存在如下状况：返回之前这个key对应的value值或者返回null，注意这个null既可能表示这个key之前没有保存过，也可能意味着这个key之前级亅保存的null值。 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }/** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //接收成员变量table里面的元素 Node[] tab; Node p; int n, i; //table赋值给tab并检查当前tab是否为空或者长度为0，如果是则执行一次扩容操作，此处的扩容方法用于初始化table或者是给table执行一次扩容，扩容为已有容量的两倍；初始化则是有一个默认值16。并将扩容后的size赋给n if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //扩容后的size值为n，哈希值与当前table的size取余得到就是当前key应该在哈希表中存放的位置，如果这个节点没有或者为null的话就新创建一个节点，将对应的hash值，key和value值放入其中并赋值给tab[i]，这里其实就完成了一次基础的put操作 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //如果检索到tab上已经有这个节点值(这里就是哈希碰撞)，检查当前位置node的哈希值与入参哈希值是否相等以及这个node节点的key是否与入参key一致。如果都一致，把这个节点的值赋给条件分支内的临时变量e Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) //类型检查当前的node是不是一个树节点，如果是的话就执行一个强转操作，方便后续操作 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { //因为存在碰撞的情况，就把新加入的node值放在已有链表的最后(尾插法)，如果链表长度已经超过8，就把链表转成平衡树并将数据放到平衡树中。最后将e赋回给p。这里e可能已经转成树了。 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } 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加一，这里这个字段是基于fail-fast机制设置的 ++modCount; //检查插入元素后的size是不是已经超过临界值了，如果超过了就执行一次扩容操作 if (++size> threshold) resize(); afterNodeInsertion(evict); return null; }

putVal方法四个入参

hash 哈希值，由入参key计算得到
key 入参key
value 入参value
onlyIfAbsent
evict

put时会判断当前hashMap的成员table是否是null或者size为0。执行resize方法
取余(%)操作中如果除数是2的幂次方，则等同于与其除数减一的与(&)操作这句话可以解释，在hashMap中大量出现的(n-1) & hash 这样的语句。意思就是哈希值与n的取余操作。
这里产生碰撞的key-value键值对都被保存了。取值的时候get方法的内容会解释，是如何在碰撞的键值对中找到正确的值的。

文章图片
put方法图解-此图出自引用文章流程解析

检查当前链表是否为null或者长度是否为空，如果是的话就执行一次扩容操作，为null的话设置长度为16，其扩容操作是将长度翻倍。
扩容后的size与key做位与操作，得到的值就是目标键值对在链表中的保存位置(位与操作实际就是取余)。如果得到的这个位置在链表中为null则创建一个新的节点保存键值对并将这个节点赋值给计算得到的位置。
如果这个计算得到的位置不是null，那么当前位置有值，首先判断是不是key重复了(此处是指key一致并且其hashCode也一致)，key完全一致则用新赋值的节点覆盖已有的节点。
不是key重复的话检查p节点是不是一个树形节点并在红黑树上插入这个节点。
3和4步骤都没有覆盖到，那么这是一个碰撞场景了，使用一个for循环单向遍历链表找到链表的结尾并插入一个新的节点(尾插法-即put方法的插入操作是链表的尾插)。注意在循环中一样要注意检查是否是key重复，如果在单向链表中也有key重复的场景就结束循环不执行插入操作
检查单向链表的长度是否超过了8，如果超过了则将其转换为树形结构。
再次检查新插入的节点，如果确实是已经存在的key了，将新的value值赋给这个节点并返回已经存在的oldValue。注意这里完成了一次替换。
modCount统计字段加1，并++size检查插入元素后是否需要扩容。

核心扩容方法

// 初始化或者执行一次扩容(每次扩容为原来size的两倍)。 final Node[] resize() { Node[] oldTab = table; //将table引用拷贝一份，作值oldTab int oldCap = (oldTab == null) ? 0 : oldTab.length; //获取链表长度,如果链表为null则长度值为0，其余情况都是原table的size值 int oldThr = threshold; //扩容判断的阀值 int newCap, newThr = 0; //预定义新的链表长度和新的扩容预判阀值,默认值均为0 if (oldCap > 0) {//当元链表的容量值有效(大于0)则检查这个容量值是否超过了桶容量上限(2的32次方)，是的话将扩容阀值调整为最大值(Integer.MAX)。并直接结束方法- if (oldCap >= MAXIMUM_CAPACITY) {//-这里首先判断链表是不是已经超出了扩容操作的上限。超过了就直接返回不再扩容。并且直接将阀值调整到最大，这样就不会在触碰到扩容阀值。 threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&//原链表长度没有超过上限，则将原链表长度翻倍(注意这里的翻倍操作是一个位运算，带符号右移)。并判断这个新得到的长度值是不是小于了上限MAX。 oldCap >= DEFAULT_INITIAL_CAPACITY)//同时检查原链表长度oldCap是不是大于初始化链表长度值(初始化值长度为1的4次方即16)。这两个条件满足则调整扩容阀值，策略也是翻倍(位运算) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold//如果扩容前的扩容阀值大于零即已经别初始化过了，就将原来的扩容阀值赋给新的(扩容后)的桶容量(newCap) newCap = oldThr; else {// zero initial threshold signifies using defaults//之前扩容阀值没有被初始化过，即这个map实例是第一次初始化，则将设定的默认值赋值。初始桶容量16，初始扩容阀值16*0.75=12 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); }if (newThr == 0) {//前面的逻辑会给newCap赋一个确定值，确定了桶数目后的下一步是确定扩容阀值newThr，如果前面都没有确定，那么这里确定下来新的扩容阀值。 float ft = (float)newCap * loadFactor; //检查新的桶容量是不是没有超过上限，检查新的计算得到的扩容阀值是不是没有超过了扩容阀值上限。如果检查安全的话就赋值了 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; //这里就将确定下来的新的扩容阀值赋给类的成员变量，至此完成了新的size值与threshold值的确定 @SuppressWarnings({"rawtypes","unchecked"}) Node[] newTab = (Node[])new Node[newCap]; //创建新的桶链表newTab，其长度为newCap table = newTab; //链表类成员得到新的一个实例引用，这里原有的tab仍然保存在oldTab中，在复制数据的时候还会用到 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) {//数据拷贝工作，这里的j是从0递增，也就是从链表的表头开始遍历 Node e; if ((e = oldTab[j]) != null) {//获得oldTab[j]并判断其是否非空，将其赋值给局部变量Node节点e oldTab[j] = null; //将oldTab[j]置空 if (e.next == null)//如果遍历到的节点e已经没有后继节点，创建一个新的节点? newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode)//如果树结构(红黑树节点)，执行一个split方法？ ((TreeNode)e).split(this, newTab, j, oldCap); else { // preserve order//多数情况下走到的逻辑代码段，preserve order-维持原有顺序 Node loHead = null, loTail = null; //创建两个node头结点，分别称为lo串和hi串。这两个串。lo串会在新的桶中保持原来的位置即index[i]。而hi串会在原来位置的基础上迁移为index[i+newCap] Node hiHead = null, hiTail = null; Node next; do {//一段do/wh1ile循环 next = e.next; //节点e赋值给局部变量next节点 if ((e.hash & oldCap) == 0) {//当前节点hash值与旧的桶容量做位运算，如果值为0。这里是一段让人费解的逻辑，也是JDK1.8中的扩容重散列优化部分的代码。1.7的扩容会倒置原链表中元素的位置。1.8不会这么做。 if (loTail == null)//判断lo串的尾节点是否为null，如果是的话则将e插入lo串的尾节点 loHead = e; else//如果lo串的尾节点不为null,则将e插入作为lo串尾节点的后继节点 loTail.next = e; loTail = e; //最后将e插入lo串，直接为lo串的尾节点，这里可能出现一个情况，即lo串的尾节点以及lo串尾节点的后继节点都是节点e } else {//当前节点hash值与旧的桶容量做位运算，如果值不为0 if (hiTail == null)//将节点e插入hi串，和lo串一样的插入逻辑 hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) {//将lo串和hi串保存到新的哈希桶中 loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

2.4 hashMap 高并发情况下的闭环链问题在 JDK1.7 的 HashMap 源码中，存在这个问题，其根源在于扩容时的 transfer 方法，用于在扩容时对表中的节点进行 rehash，并将元素在扩容后的 hashmap 中妥善放置。

/** * Transfers all entries from current table to newTable. */ void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; // 获取扩容后，新的 table 的桶数目 for (Entry e : table) { // 从旧表中依次遍历元素while(null != e) { Entry next = e.next; // 多线程环境下，某些插入线程挂起的位置，也是引起闭环现象的根源。 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } // while} }

注释内容中我有说到一个线程挂起位置的一行，在这个位置挂起了某些插入线程，就是产生闭环问题的起始点。当多个线程在扩容的过程中互相修改链表内引用的地址。
最后在其他线程的查找操作中，因为哈希桶内元素的 next 引用互相的指向对象，从而产生一个死循环。导致查询操作停滞。这部分的内容有不少的博客有很详细的解释内容，在此处就不详细叙述了。