我的jdk源码（十三）：HashMap一磕到底，追根溯源！

一、前言

    HashMap作为java重要的数据结构之一，是jdk源码阅读必看的内容，今天就带大家一起深入分析，探讨jdk1.7和jdk1.8下HashMap的结构有哪些区别变化，并且深入分析产生这些变化的原因，最后再结合近几年的面试题目进行分析探讨。那我们开始吧！

二、HashMap概述

    HashMap是基于哈希表的Map接口实现，此实现提供所有可选的映射操作，并允许使用null值和null键。HashMap与HashTable的作用大致相同，但是它不是线程安全的。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。遍历HashMap的时间复杂度与其的容量(capacity)和现有元素的个数（size）成正比。如果要保证遍历的高效性，初始容量（capacity)不能设置太高或者平衡因子（load factor）不能设置太低。大致介绍如下：

    1.HashMap是存储键值对（key，value）的一种数据结构。

    2.每一个元素都是一个key-value。

    3.HashMap最多只允许一个key为null，允许多个key的value值为null。

    4.HashMap是非线程安全的，只适用于单线程环境。

    5.HashMap实现了Serializable、Cloneable接口，因此它支持序列化和克隆。

三、HashMap在jdk1.7中的形态

    JDK1.7的HashMap是基于一个数组加多个单链表来实现的，hash值冲突时，就将对应节点以链表的形式存储。底层实现图如下：

    接下来从底层结构、put和get方法、hash数组索引、扩容机制等几个方面来分析HashMap的实现原理：

    (1) jdk1.7中的成员变量，源码如下：

/** 初始容量，默认16 */static final int DEFAULT_INITIAL_CAPACITY = 1 <<4; // aka 16 /** 最大初始容量，2^30 */static final int MAXIMUM_CAPACITY = 1 <<30; /** 负载因子，默认0.75，负载因子越小，hash冲突机率越低 */static final float DEFAULT_LOAD_FACTOR = 0.75f;/** 初始化一个Entry的空数组 */static final Entry[] EMPTY_TABLE = {};/** 将初始化好的空数组赋值给table，table数组是HashMap实际存储数据的地方，并不在EMPTY_TABLE数组中 */transient Entry[] table = (Entry[]) EMPTY_TABLE;/** HashMap实际存储的元素个数 */transient int size;/** 临界值（HashMap 实际能存储的大小）,公式为(threshold = capacity * loadFactor) */ int threshold;/** 负载因子 */ final float loadFactor;/** HashMap的结构被修改的次数，用于迭代器，用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时， 如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常 ConcurrentModificationException*/ transient int modCount;

        注意：

        * transient关键字将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会被序列化

        *  负载因子为什么是0.75，是由泊松分布得出，在时间和空间成本折衷选择

   (2) 构造函数源码如下：

//计算Hash值时的key transient int hashSeed = 0; //通过初始容量和状态因子构造HashMap 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;//通过tableSizeFor()方法计算容器容量this.threshold = tableSizeFor(initialCapacity);} //通过扩容因子构造HashMap,容量取默认值，即16public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //装载因子取0.75，容量取16，构造HashMappublic HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } //通过其他Map来初始化HashMap,容量通过其他Map的size来计算，装载因子取0.75public HashMap(Map m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); //初始化HashMap底层的数组结构inflateTable(threshold);//添加m中的元素putAllForCreate(m);}

    注意：

     a. 给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了，就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。因此通常建议能提前预估 HashMap 的大小最好，尽量的减少扩容带来的性能损耗。

     b. 根据成员变量源码可以看出，数据是被存放在Entry[] table数组里面。

(3) Node源码如下：

// 静态内部类static class Node implements Map.Entry {//key 就是写入时的键。final K key;//value 自然就是值V value;//开始的时候就提到 HashMap 是由数组和链表组成，所以这个 next 就是用于实现链表结构。用于指向下一个entry节点Entry next;//hash 存放的是当前 key 的 hashcode。int hash;/*** 构造函数，每次都用新的节点指向链表的头结点。新节点作为链表新的头结点*/Entry(int h, K k, V v, Entry n) {value = v;next = n; // !!!key = k;hash = h;}public final K getKey() {return key;}public final V getValue() {return value;}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}public final boolean equals(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry e = (Map.Entry)o;Object k1 = getKey();Object k2 = e.getKey();if (k1 == k2 || (k1 != null && k1.equals(k2))) {Object v1 = getValue();Object v2 = e.getValue();if (v1 == v2 || (v1 != null && v1.equals(v2)))return true;}return false;}public final int hashCode() {return (key==null ? 0 : key.hashCode()) ^(value==null ? 0 : value.hashCode());}public final String toString() {return getKey() + "=" + getValue();}//每当Entry中的值被已在HashMap中的键k的put(k,v)调用覆盖时，都会调用此方法。void recordAccess(HashMap m) {}//每当从表中删除Entry时，都会调用此方法。void recordRemoval(HashMap m) {}}

    以上就是基本的结构内容了，接下来深入学习put方法。

   (4)put方法源码如下：

public V put(K key, V value) {//如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(=16)。if (table == EMPTY_TABLE) {inflateTable(threshold);}//若“key为null”，则将该键值对添加到table[0]处，遍历该链表，如果有存在key为null的entry，则将value替换。没有就创建新Entry对象放在链表表头，所以table[0]的位置上，永远最多存储1个Entry对象，形成不了链表。key为null的Entry存在这里。if (key == null)return putForNullKey(value);//若key不为null，则计算该key的hash值，然后将其添加到该哈希值对应的数组索引处的链表中。int hash = hash(key);//根据hash值计算桶号。int i = indexFor(hash, table.length);//遍历该桶中的链表。for (Entry e = table[i]; e != null; e = e.next) {Object k;//如果其hash值相等且键也相等，将新值替换旧值，并返回旧值。if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}//保证并发访问时，若HashMap内部结构发生变化，快速响应失败。即修改次数+1modCount++;//如果桶是空的，说明当前位置没有数据存入；新增一个 Entry 对象写入当前位置。addEntry(hash, key, value, i);return null;}

   (5) 数组空间分配的方法 inflateTable(threshold)，源码如下：

private void inflateTable(int toSize) {//capacity一定是2的次幂int capacity = roundUpToPowerOf2(toSize);//此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1。threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//分配空间。table = new Entry[capacity];//选择合适的Hash因子。initHashSeedAsNeeded(capacity);}

    inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16；to_size=16，capacity=16；to_size=17,capacity=32。

   (6) roundUpToPowerOf2(toSize)源码如下：

private static int roundUpToPowerOf2(int number) {// assert number >= 0 : "number must be non-negative";return number >= MAXIMUM_CAPACITY? MAXIMUM_CAPACITY: (number > 1) ? Integer.highestOneBit((number - 1) <<1) : 1;}

    roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂，Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值。

   (7) 我们再来看put方法中的hash方法的计算，源码如下：

//判断k的数据类型选择不同的hash计算方式。用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀。final int hash(Object k) { //随机种子,用来降低冲突发生的几率int h = hashSeed;//这里针对String优化了Hash函数。if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}//对键值计算的hashcode再进行一系列运算h ^= k.hashCode();//这个函数确保哈希码在每个位的倍数不变的情况下只会发生有限数量的碰撞(默认负载系数大约为8)。h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}

    从上面的操作看以看出，影响HashMap元素的存储位置的只有key的值，与value值无关。通过高低位之间进行异或用来加大低位的随机性，以减少冲突的几率。通过hash函数得到散列值后，再通过indexFor进一步处理来获取实际的存储位置.

   (8) put方法中的indexFor方法的源码如下：

//返回数组下标static int indexFor(int h, int length) {//把hash值和数组的长度进行“与”操作。return h & (length-1);}

        该方法用于确定元素存放于数组的位置，但是参数h是一个由hash方法计算而来的int类型数据，如果直接拿h作为下标访问HashMap主数组的话，考虑到2进制32位带符号的int值范围从-2147483648到2147483648，该值可能会很大，所以这个值不能直接使用，要用它对数组的长度进行取模运算，得到的余数才能用来当做数组的下标，这就是indexFor方法做的事情。（因为length总是为2的N次方，所以h & (length-1)操作等价于hash % length操作， 但&操作性能更优，性能更优的原因是将代码反编译后可以看到，取模运算至少需要26个CPU周期，而与运算只需要5个CPU周期）。

        该方法也是HashMap的数组长度为什么总是2的N次方的原因。2的N次方 - 1的二进制码是一个“低位掩码”，“与”操作后会把hash值的高位置零，只保留低位的值，使用这种方法使值缩小。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。这样，就算差距很大的两个数，只要低位相同，那么就会产生冲突，会对性能造成很大的影响，于是，hash方法的作用就体现出来了。具体计算如下图所示：

   (9) put方法中的addEntry方法的源码如下：

void addEntry(int hash, K key, V value, int bucketIndex) {//当调用 addEntry 写入 Entry 时需要判断是否需要扩容if ((size >= threshold) && (null != table[bucketIndex])) {//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容，新容量为旧容量的2倍resize(2 * table.length);//扩容后，重新计算哈希值hash = (null != key) ? hash(key) : 0;//扩容后重新计算插入的位置下标，即重新计算桶号bucketIndex = indexFor(hash, table.length);}//createEntry中会将当前位置的桶传入到新建的桶中，如果当前桶有值就会在位置形成链表createEntry(hash, key, value, bucketIndex);}void createEntry(int hash, K key, V value, int bucketIndex) {//获取待插入位置元素Entry e = table[bucketIndex];//这里执行链接操作，使得新插入的元素指向原有元素。这保证了新插入的元素总是在链表的头table[bucketIndex] = new Entry<>(hash, key, value, e);//元素个数加1size++;}

        发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。   

   (10)  接下来让我们看看resize（2 * table.length）的扩容方法，源码如下：

//按新的容量扩容Hash表 void resize(int newCapacity) {//先获取老的数据 Entry[] oldTable = table;//获取老的容量值 int oldCapacity = oldTable.length;//如果老的容量值已经到了最大容量值，则修改扩容阙值 if (oldCapacity == MAXIMUM_CAPACITY) {//修改扩容阀值threshold = Integer.MAX_VALUE; return; } //创建新的结构Entry[] newTable = new Entry[newCapacity];boolean oldAltHashing = useAltHashing; //(6)计算是否需要对键重新进行哈希码的计算useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);boolean rehash = oldAltHashing ^ useAltHashing;//将老的表中的数据拷贝到新的结构中。将原有所有的桶迁移至新的桶数组中 ，在迁移时，桶在桶数组中的绝对位置可能会发生变化 *，这就是为什么HashMap不能保证存储条目的顺序不能恒久不变的原因 transfer(newTable, rehash);//修改HashMap的底层数组 table = newTable;//修改阀值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}

   (11) 接下来让我们进入到tranfer方法中，看看是如何进行桶迁移至新的桶数组中的，源码如下：

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;//遍历当前的table，将里面的元素添加到新的newTable中for (Entry e : table) {while(null != e) {Entry next = e.next;//如果是重新Hashif (rehash) {//重新计算hash值e.hash = null == e.key ? 0 : hash(e.key);}//计算桶号int i = indexFor(e.hash, newCapacity);//元素连接到桶中,这里相当于单链表的插入，总是插入在最前面e.next = newTable[i];//存放在数组下标i中,所以扩容后链表的顺序与原来相反newTable[i] = e;//继续下一个元素e = next;}}}

   (12) get方法源码如下：

//获取key值为key的元素值public V get(Object key) {//如果Key值为空，则获取对应的值，这里也可以看到，HashMap允许null的key，其内部针对null的key有特殊的逻辑if (key == null)return getForNullKey();//如果建不为null，获取Entry实体Entry entry = getEntry(key);//判断是否为空，不为空，则获取对应的值return null == entry ? null : entry.getValue();}final Entry getEntry(Object key) {//元素个数为 0 ，直接返回nullif (size == 0) {return null;}//计算key的hash值int hash = (key == null) ? 0 : hash(key);//根据key和表的长度，定位到Hash桶for (Entry e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;//遍历直到 key 及 hashcode 相等时候就返回值if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;}//啥也没取到,返回nullreturn null;}

   (13) 针对键值为null的的特殊逻辑，源代码如下：

//获取key为null的实体 private V getForNullKey() { if (size == 0) {//如果元素个数为0，则直接返回null return null; } //key为null的元素存储在table的第0个位置 for (Entry e = table[0]; e != null; e = e.next) { if (e.key == null)//判断是否为null return e.value;//返回其值 } return null; }

   (14) 接着让我们看最后一个remove方法，源码如下：

final Entry removeEntryForKey(Object key) {//计算键的hash值int hash = (key == null) ? 0 : hash(key);//计算桶号int i = indexFor(hash, table.length);//记录待删除节点的上一个节点Entry prev = table[i];//待删除节点Entry e = prev;while (e != null) {Entry next = e.next;Object k;//是否是将要删除的节点if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {modCount++;size--;//将要删除的节点是否为链表的头部if (prev == e)//链表的头部指向下一节点table[i] = next;else//上一节点的NEXT为将要删除节点的下一节点prev.next = next;e.recordRemoval(this);return e;}prev = e;e = next;}return e;}

四、HashMap在jdk1.8中的变化

    正如开篇提到的当 Hash 冲突严重时，在桶上形成的链表会变的越来越长，这样在查询时的效率就会越来越低，时间复杂度为O(N)。因此JDK1.8中中采用的是位桶+链表/红黑树的结构实现，而在JDK1.8中的时候链表长度达到一个阙值(通常节点数量  > 8 )的时候就会转换成红黑树结构，至于红黑树，自己去了解后再来看此篇文章，众所周知红黑树的时间复杂度为 log n ，这无疑是对性能的一次大提升。相对于JDK1.7的位桶+链表的实现方式来说，性能谁优谁劣，可想而知。底层实现图如下：

   (1) jdk1.8中HashMap的成员变量，源码如下：

//默认的初始容量是16static final int DEFAULT_INITIAL_CAPACITY = 1 <<4; //桶最大容量static final int MAXIMUM_CAPACITY = 1 <<30; //默认的负载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;//当桶(bucket)上的结点数大于这个值时会转成红黑树static final int TREEIFY_THRESHOLD = 8; //当桶(bucket)上的结点数小于这个值时树转链表static final int UNTREEIFY_THRESHOLD = 6;//桶中结构转化为红黑树对应的table的最小大小static final int MIN_TREEIFY_CAPACITY = 64;//存储元素的数组，总是2的幂次倍transient Node[] table; //存放具体元素的集transient Set> entrySet;//存放元素的个数，注意这个不等于数组的长度。transient int size;//每次扩容和更改map结构的计数器transient int modCount; //临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容int threshold;//负载因子final float loadFactor;

        可以看出，多出了3个成员变量：

        * TREEIFY_THRESHOLD： 链表转为红黑树的临界值。

        * UNTREEIFY_THRESHOLD：红黑树转为链表的临界值。

        * MIN_TREEIFY_CAPACITY ：当有链表转为红黑树时，需要判断数组桶的长度是否小于这个值，如果小于，就拓展这个桶，每次拓展为原长度的2倍

   (2) 构造函数源码如下：

public HashMap(int initialCapacity, float loadFactor) {// 桶初始容量不能小于0，否则报错if (initialCapacity <0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);// 桶初始容量不能大于最大值，否则为最大值if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;//校验负载因子 负载因子不能小于或等于0，不能为非数字if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);// 初始化负载因子 this.loadFactor = loadFactor;// 初始化threshold大小this.threshold = tableSizeFor(initialCapacity);
}public HashMap(int initialCapacity) {// 调用HashMap(int, float)型构造函数,通过扩容因子构造HashMap,容量取默认值，即16 。this(initialCapacity, DEFAULT_LOAD_FACTOR);
}public HashMap() {// 初始化负载因子，装载因子取0.75，容量取16，构造HashMap this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//通过其他Map来初始化HashMap,容量通过其他Map的size来计算，装载因子取0.75
public HashMap(Map m) {// 初始化负载因子this.loadFactor = DEFAULT_LOAD_FACTOR;// 将m中的所有元素添加至HashMap中putMapEntries(m, false);
}

        与jdk1.7相比，有以下不同之处：

        a. 初始化threshold大小

            jdk1.8中设置临界值this.threshold = tableSizeFor(initialCapacity)，tableSizeFor(initialCapacity)返回大于等于initialCapacity的最小的二次幂数值，源码如下：

static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n <0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

        为什么要在前面减1， n = n - 1; 是为了防止输入已经是2的幂次的数还扩大了。 然后在后面为什么加回来呢？当输入为0的时候就会发现，方法的输出为1，HashMap的容量只有大于0时才有意义。

        b. 通过其他Map来初始化HashMap，putMapEntries(Map m, boolean evict)函数将m的所有元素存入本HashMap实例中。源码如下：

final void putMapEntries(Map m, boolean evict) {int s = m.size();if (s > 0) {// 判断table是否已经初始化if (table == null) { // pre-size// 未初始化，s为m的实际元素个数float ft = ((float)s / loadFactor) + 1.0F;int t = ((ft <(float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);// 计算得到的t大于阈值，则初始化阈值if (t > threshold)threshold = tableSizeFor(t);}// 已初始化，并且m元素个数大于阈值，进行扩容处理else if (s > threshold)resize();// 将m中的所有元素添加至HashMap中for (Map.Entry e : m.entrySet()) {K key = e.getKey();V value = e.getValue();putVal(hash(key), key, value, false, evict);}}
}

   (3) 接下来我们再看JDK1.8中的Hash算法，源码如下：

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

        首先获取对象的hashCode()值，然后将hashCode值右移16位，然后将右移后的值与原来的hashCode做异或运算，返回结果。其中h>>>16，在JDK1.8中，优化了高位运算的算法，使用了零扩展，无论正数还是负数，都在高位插入0。

   (4) 接着再看jdk1.8中的put方法，源码如下：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node[] tab; Node p; int n, i;// 判断当前桶是否为空，空的就需要初始化（resize 中会判断是否进行初始化）。if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 桶中已经存在元素else {Node e; K k;// 如果当前桶有值（ Hash 冲突），那么就要比较当前桶中的key、key 的 hashcode与写入的 key 是否相等，相等就赋值给e,在第下面会统一进行赋值及返回。if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// 将第一个元素赋值给e，用e来记录e = p;// 如果当前桶为红黑树，那就要按照红黑树的方式写入数据。else if (p instanceof TreeNode)// 放入树中e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);// 该链为链表 // 为链表结点else {//如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面（形成链表）。for (int binCount = 0; ; ++binCount) {// 到达链表的尾部if ((e = p.next) == null) {// 在尾部插入新结点p.next = newNode(hash, key, value, null);// 接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);// 跳出循环break;}// 判断链表中结点的key值与插入的元素的key值是否相等if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 相等，跳出循环break;// 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表p = e;}}// 接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。if (e != null) { // 记录e的valueV oldValue = e.value;// onlyIfAbsent为false或者旧值为nullif (!onlyIfAbsent || oldValue == null)//用新值替换旧值e.value = value;// 访问后回调afterNodeAccess(e);// 返回旧值return oldValue;}}// 结构性修改++modCount;// 最后判断是否需要进行扩容。超过最大容量就扩容，实际大小大于阈值则扩容。if (++size > threshold)resize();// 插入后回调afterNodeInsertion(evict);return null;
}

        HashMap的数据存储实现原理：

        *  根据key计算得到key.hash = (h = k.hashCode()) ^ (h >>>16)；

        *  根据key.hash计算得到桶数组的索引index = key.hash & (table.length -1)，这样就找到该key的存放位置了，具体判断如下：

            ① 如果该位置没有数据，用该数据新生成一个节点保存新数据，返回null；

            ② 如果该位置有数据是一个红黑树，那么执行相应的插入 / 更新操作；

            ③ 如果该位置有数据是一个链表，分两种情况一是该链表没有这个节点，另一个是该链表上有这个节点，注意这里判断的依据是key.hash是否一样：

        如果该链表没有这个节点，那么采用尾插法新增节点保存新数据，返回null；如果该链表已经有这个节点了，那么找到该节点并更新新数据，返回老数据。

   (5) 接着我们进入到红黑树插入数据的putTreeVal(this, tab, hash, key, value)方法源码中：

/*** Tree version of putVal.* 红黑树插入会同时维护原来的链表属性, 即原来的next属性*/
final TreeNode putTreeVal(HashMap map, Node[] tab,int h, K k, V v) {Class kc = null;boolean searched = false;// 查找根节点, 索引位置的头节点并不一定为红黑树的根结点TreeNode root = (parent != null) ? root() : this; for (TreeNode p = root;;) { // 将根节点赋值给p, 开始遍历int dir, ph; K pk;if ((ph = p.hash) > h) // 如果传入的hash值小于p节点的hash值 dir = -1; // 则将dir赋值为-1, 代表向p的左边查找树else if (ph q, ch;searched = true;// 从p节点的左节点和右节点分别调用find方法进行查找, 如果查找到目标节点则返回if (((ch = p.left) != null &&(q = ch.find(h, k, kc)) != null) ||((ch = p.right) != null &&(q = ch.find(h, k, kc)) != null)) return q;}// 否则使用定义的一套规则来比较k和p节点的key的大小, 用来决定向左还是向右查找dir = tieBreakOrder(k, pk); // dir<0则代表k

xp = p; // xp赋值为x的父节点,中间变量,用于下面给x的父节点赋值// dir<=0则向p左边查找,否则向p右边查找,如果为null,则代表该位置即为x的目标位置if ((p = (dir <= 0) ? p.left : p.right) == null) { // 走进来代表已经找到x的位置，只需将x放到该位置即可Node xpn = xp.next; // xp的next节点 // 创建新的节点, 其中x的next节点为xpn, 即将x节点插入xp与xpn之间TreeNode x = map.newTreeNode(h, k, v, xpn); if (dir <= 0) // 如果时dir <= 0, 则代表x节点为xp的左节点xp.left = x;else // 如果时dir> 0, 则代表x节点为xp的右节点xp.right = x;xp.next = x; // 将xp的next节点设置为xx.parent = x.prev = xp; // 将x的parent和prev节点设置为xp// 如果xpn不为空,则将xpn的prev节点设置为x节点,与上文的x节点的next节点对应if (xpn != null) ((TreeNode)xpn).prev = x;moveRootToFront(tab, balanceInsertion(root, x)); // 进行红黑树的插入平衡调整return null;}}
}

   (6) 我们再来看链表是如何转红黑树的，treeifyBin(tab, hash)，源码如下：

final void treeifyBin(Node[] tab, int hash) {int n, index; Node e;// table为空或者table的长度小于64, 进行扩容if (tab == null || (n = tab.length) hd = null, tl = null;do {//调用replacementTreeNode方法（该方法就一行代码，直接返回一个新建的TreeNode）将链表节点转为红黑树节点，将头结点赋值给hd节点，每次遍历结束将p节点赋值给tl，用于在下一次循环中作为上一个节点进行一些链表的关联操作（p.prev = tl 和 tl.next = p）。TreeNode p = replacementTreeNode(e, null);if (tl == null) // tl为空代表为第一次循环hd = p; // 头结点else {p.prev = tl; // 当前节点的prev属性设为上一个节点tl.next = p; // 上一个节点的next属性设置为当前节点}tl = p; // tl赋值为p, 在下一次循环中作为上一个节点} while ((e = e.next) != null); // e指向下一个节点// 将table该索引位置赋值为新转的TreeNode的头节点if ((tab[index] = hd) != null) hd.treeify(tab); // 以头结点为根结点, 构建红黑树}

   (7) 我们继续看如何构建红黑树，treeify(Node[] tab)源码如下：

final void treeify(Node[] tab) { // 构建红黑树TreeNode root = null;for (TreeNode x = this, next; x != null; x = next) {// this即为调用此方法的TreeNodenext = (TreeNode)x.next; // next赋值为x的下个节点x.left = x.right = null; // 将x的左右节点设置为空if (root == null) { // 如果还没有根结点, 则将x设置为根结点x.parent = null; // 根结点没有父节点x.red = false; // 根结点必须为黑色root = x; // 将x设置为根结点}else {K k = x.key; // k赋值为x的keyint h = x.hash; // h赋值为x的hash值Class kc = null;// 如果当前节点x不是根结点, 则从根节点开始查找属于该节点的位置for (TreeNode p = root;;) { int dir, ph;K pk = p.key; if ((ph = p.hash) > h) // 如果x节点的hash值小于p节点的hash值dir = -1; // 则将dir赋值为-1, 代表向p的左边查找else if (ph xp = p; // xp赋值为x的父节点,中间变量用于下面给x的父节点赋值// dir<=0则向p左边查找,否则向p右边查找,如果为null,则代表该位置即为x的目标位置if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; // x的父节点即为最后一次遍历的p节点if (dir <= 0) // 如果时dir <= 0, 则代表x节点为父节点的左节点xp.left = x;else // 如果时dir > 0, 则代表x节点为父节点的右节点xp.right = x;// 进行红黑树的插入平衡(通过左旋、右旋和改变节点颜色来保证当前树符合红黑树的要求)root = balanceInsertion(root, x); break;}}}}moveRootToFront(tab, root); // 如果root节点不在table索引位置的头结点, 则将其调整为头结点
}

   (8) 我们来仔细看下节点调节的moveRootToFront()方法，源码如下：

/*** 如果当前索引位置的头节点不是root节点, 则将root的上一个节点和下一个节点进行关联, * 将root放到头节点的位置, 原头节点放在root的next节点上*/
static void moveRootToFront(Node[] tab, TreeNode root) {int n;if (root != null && tab != null && (n = tab.length) > 0) {int index = (n - 1) & root.hash;TreeNode first = (TreeNode)tab[index];if (root != first) { // 如果root节点不是该索引位置的头节点Node rn;tab[index] = root; // 将该索引位置的头节点赋值为root节点TreeNode rp = root.prev; // root节点的上一个节点// 如果root节点的下一个节点不为空, // 则将root节点的下一个节点的prev属性设置为root节点的上一个节点if ((rn = root.next) != null) ((TreeNode)rn).prev = rp; // 如果root节点的上一个节点不为空, // 则将root节点的上一个节点的next属性设置为root节点的下一个节点if (rp != null) rp.next = rn;if (first != null) // 如果原头节点不为空, 则将原头节点的prev属性设置为root节点first.prev = root;root.next = first; // 将root节点的next属性设置为原头节点root.prev = null;}assert checkInvariants(root); // 检查树是否正常}

         * assert 关键字本意是对环境中，在正常使用的情况下，不会出现问题的条件判断。这些代码常常出现在基类、框架类、工具类等核心代码中。而在这些代码的正常运行中，是不会出现参数异常的场景的。可是一旦通过反射，动态代理等方式使某些关键值发生了改变，就会导致出现大量的异常场景。而如果我们为了保护这些场景而加入大量的基本不会生效的if判断中，那么这些基本不会起作用的if判断，不但会严重的影响代码的可读性和简洁，还使读者觉得这些异常场景是会经常发生的，同时对系统的性能也有一定的影响。

   (9) 再来看jdk1.8中的get方法，源码如下：

public V get(Object key) {Node e;//首先将 key hash 之后取得所定位的桶。return (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node getNode(int hash, Object key) {Node[] tab; Node first, e; int n; K k;//如果桶为空则直接返回 null 。if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key，是就直接返回 value。if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;//如果第一个不匹配，则判断它的下一个是红黑树还是链表。if ((e = first.next) != null) {//红黑树就按照树的查找方式返回值。if (first instanceof TreeNode)// 在红黑树中查找return ((TreeNode)first).getTreeNode(hash, key);//不然就按照链表的方式遍历匹配返回值。do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}

   (10) 最后再来看看jdk1.8中的resize（）扩容方法，源码如下：

final Node[] resize() {Node[] oldTab = table;//oldTab指向hash桶数组int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {//如果oldCap不为空的话，就是hash桶数组不为空if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了，就赋值为整数最大的阀值threshold = Integer.MAX_VALUE;return oldTab;//返回}//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16else if ((newCap = oldCap <<1) = DEFAULT_INITIAL_CAPACITY)newThr = oldThr <<1; // double threshold 双倍扩容阀值threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap [] newTab = (Node[])new Node[newCap];//新建hash桶数组table = newTab;//将新数组的值复制给旧的hash桶数组if (oldTab != null) {//进行扩容操作，复制Node对象值到新的hash桶数组，注意这个地方，这里并发可能会造成数据丢失for (int j = 0; j e;if ((e = oldTab[j]) != null) {//如果旧的hash桶数组在j结点处不为空，复制给eoldTab[j] = null;//将旧的hash桶数组在j结点处设置为空，方便gcif (e.next == null)//如果e后面没有Node结点newTab[e.hash & (newCap - 1)] = e;//直接对e的hash值对新的数组长度求模获得存储位置else if (e instanceof TreeNode)//如果e是红黑树的类型，那么添加到红黑树中((TreeNode)e).split(this, newTab, j, oldCap);else { // preserve orderNode loHead = null, loTail = null;Node hiHead = null, hiTail = null;Node next;do {next = e.next;//将Node结点的next赋值给nextif ((e.hash & oldCap) == 0) {//如果结点e的hash值与原hash桶数组的长度作与运算为0if (loTail == null)//如果loTail为nullloHead = e;//将e结点赋值给loHeadelseloTail.next = e;//否则将e赋值给loTail.nextloTail = e;//然后将e复制给loTail}else {//如果结点e的hash值与原hash桶数组的长度作与运算不为0if (hiTail == null)//如果hiTail为nullhiHead = e;//将e赋值给hiHeadelsehiTail.next = e;//如果hiTail不为空，将e复制给hiTail.nexthiTail = e;//将e复制个hiTail}} while ((e = next) != null);//直到e为空if (loTail != null) {//如果loTail不为空loTail.next = null;//将loTail.next设置为空newTab[j] = loHead;//将loHead赋值给新的hash桶数组[j]处}if (hiTail != null) {//如果hiTail不为空hiTail.next = null;//将hiTail.next赋值为空newTab[j + oldCap] = hiHead;//将hiHead赋值给新的hash桶数组[j+旧hash桶数组长度]}}}}}return newTab;
}

五、总结

     从这两个核心方法（get/put）可以看出 1.8 中对大链表做了优化，修改为红黑树之后查询效率直接提高到了O(logn)，但是依旧存在一些问题。比如在并发场景下使用时容易出现死循环（JDK1.8中不会出现死循环了，但是并发可能会出现数据丢失，主要因为扩容的时候复制Node对象值到新的hash桶数组会可能出现数据丢失）。JDK1.7中导致死循环的主要原因是扩容后，节点的顺序会反掉，形成环形链接。

     更多精彩内容，敬请扫描下方二维码，关注我的微信公众号【Java觉浅】，获取第一时间更新哦！