Java高级主题：深度解析jdk1.8的HashMap源代码关键逻辑（不含红黑树结构）

jdk1.8的HashMap应该JSR-166 Java专家组（HashMap主要还是Dung Lea做了大量贡献）设计的一个极其出色且优秀的数据结构，无论是算法设计和程序代码设计都显得非常高水平，个人深入分析后，获益匪浅！

一、HashMap底层结构图以及基本术语

​ 这张结构图清晰展示HashMap由一维数组+链表+红黑树构成，数组在源码命名为table，是一个Node[]泛型类型数组，table数组上的每个元素或者为null或者为单个node或者冲突链头节点或者为treeNode。桶位上可能形成冲突链表，红黑树tree bins是由node链表树化而来。

bins：多个key哈希碰撞在某个桶位上形成的冲突链，bins这个名词来源于源码的官方注释

tree bins：某个桶位冲突链在HashMap扩容阶段被树化后的红黑树结构，tree bins这个名词来源于源码的官方注释

从这张图即可提出以下几个经典问题：

1、put一个key后，HashMap是如何将这个key定位到数组对应的某个桶位（bucketIndex）？

2、put多个key后，若形成冲突链表，那么这个链表如何形成？

3、如果put的冲突key数量非常多，例如10万个，那么在数组中的某个位置将形成一个长度为10万的长链表，那么HashMap真的会在某个桶位形成这么长的冲突链吗？ 若不会，它是怎么设计的？

4、当数组个数超过扩容阈值时，它如何扩容？扩容后，数组的有些桶位上是一条冲链表，链表上节点会被rehash到新数组其他位置，这个过程如何实现？

5、为何数组长度要设计为2的N次方，关键作用在哪里？

6、为何数组某个位置元素是一个红黑树节点，有什么用？就不能使用链表替代吗？

7、jdk1.7（Java7）的HashMap没有红黑树结构，这与java8的有何区别?

8、很多文章说在多线程场景下，Java7版本下的HashMap因为使用了头插法，在扩容节点出现循环链表导致死循环出现，Java8则不存在，为何？

当然，还有其他更刁钻问题：loadfactor为何设计0.75而是0.55、0.65、0.85等

带上以上问题，通过解析java8的HashMap源码后，将可获得准确而易于理解的答案。

二、java8的HashMap源码分析思路

分析路径参考：

静态常量=>成员变量=>构造方法=>put方法（含putVal）=>resize操作=>get方法=>remove方法等其他方法，当然还有putTreeVal方法、treefyBin方法，这两个属于HashMap的红黑树章节知识，涉及的原理也相对复杂，会在另外一篇文章会给出。

为何要先看构造方法和put方法？因为大家最熟悉以下用法：

Map<String,Integer> map=new HashMap<>();
map.put("foo",10);
map.put("bar",20);

1、继承关系

在IDEA里面容易得出以下UML图

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;

• HashMap<K,V>：说明它是以key-value形式存储，K，V为泛型类型参数。
• extends AbstractMap<K,V>：继承了AbstractMap，通过该继承，实现复用。
• implements Map<K,V>：实现了Map接口，提供了所有可选的Map接口方法。
• implements Cloneable：表明其可以调用clone()方法来返回实例的field-for-field拷贝。
• implements Serializable：表明HashMap可以被序列化和反序列化。serialVersionUID用于验证反序列化后类版本是否一致。

2、静态常量

重点看大写的静态变量。

  // 上图中数组初始容量，长度必须为2的整数幂，默认大小为16，这里用了位运算符
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 /*
* 若创建HashMap时指定容量超过2^31，则上限只能取到1 << 30，能否1 << 31？
首先int占用4个字节，数值范围在-2^31~2^31-1之间，也即[-2147483648,2147483647]，考虑到数组的容量设定值必须为2的整数幂，如果使用1 << 31，那么得出数组的长度为：2147483648，显然大于int上界2147483647，产生了溢出。换句话说，最大值2147483647不是2的整数幂，而数组每次扩容只能选择2的整数幂，因此只能在0~2^31-1之间，选择一个恰好为2的整数幂的最大值，因此只能是：1<<30,也即1073741824,10亿长度！
* “关于HashMap数组容量的最大值只能右移30位，网上很多这种解释：因为第31位是符号位，0正，1为负，因此去掉符号位后只能选择30位长度作为最大值”，这种解释不够细致。
 */
  static final int MAXIMUM_CAPACITY = 1 << 30;

  //默认负载因子大小
  static final float DEFAULT_LOAD_FACTOR = 0.75f;

 // 直译为树化阈值（桶的树化阈值），这里是指当数组里面的冲突链表长度达到8时，且数组size达到64时（MIN_TREEIFY_CAPACITY=64），才会执行treeify操作（注意不是treeifyBin操作），则需将这条链表转为tree bins。
  static final int TREEIFY_THRESHOLD = 8;

// 红黑树tree bins转为bins冲突链表的阈值，当在扩容resize时，此时HashMap的node所在桶位置会重新计算，在重新计算桶位（存储位置或者数组索引号）后，当原有的红黑树内数量 < 6时，则将红黑树转换成链表（转换过程参考本人发布的红黑树部分的文章）
  static final int UNTREEIFY_THRESHOLD = 6;

// 直翻：触发最小树化操作的容量,换句话说：当数组size小于该值时，优先进行扩容，而不是树化
  static final int MIN_TREEIFY_CAPACITY = 64;

这里要解释下为何普通的冲突链表bins转为tree bins的阈值设为8，其实是考虑到统计情况，参考以下官方解释:

* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins.  In
* usages with well-distributed user hashCodes, tree bins are
* rarely used.  Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006
* more: less than 1 in ten million

​ 根据泊松分布计算的概率分布，在负载因子默认为0.75的时候，采用足够分布均匀的随机hashcode，在桶位上(hash槽)出现冲突链且元素个数达到8的概率为0.00000006，非常小，不到百万分之一。换句话说，设为0.75时，只有百万分之一概率桶位上节点出现8个元素，显然这能大概率减少触发树化操作，从而提升HashMap性能。

​ 因此在日常开发中，put进去的key即使冲突（假设自定义的key哈希处理逻辑足够离散），也是大概率构成普通bins冲突链表（节点个数小于8），因此将树化阈值设为8可以减少频繁的树化操作。

​ 或者我们可以逆向考察：假设树化阈值设为3，根据泊松分布算出的概率为0.0126，那么每put一个key，就有1.26%概率触发树化操作，这么频繁触发，势必影响HashMap的性能，但只要将树化阈值设为8时瞬间将普通概率事件变成小概率事件，显然合理，也有科学依据。

这里可以引出一个问题：

为何需要将普通链表树化为红黑树？

考察这种情况：若所put的key的哈希值离散性不合理，且需要put很多这样的key，则高频出现hash冲突，那么这些key将会出现以下情况：

​ 假设这些key被定为到index=3的桶位置上，如果需要put 10万个这样的key，那么将会在这桶位上形成一条超长包含10万个节点的bins链表，这会出现什么问题？ 当使用get查询对应key时，将会使得原本o(1)的时间复杂度退化为0(n)，对于最坏查找情况：将需要遍历10万次，这是无法接受的查询性能。

​ 加了树化阈值后，一旦bins链表超过阈值且数组容量达到64，那么一个包含10万个节点长链表将使用红黑树来组织，也能实现o(log(n))的查找效率。

3、成员变量

主要是Fields字段，这里重点是table数组和modCount真实含义及其改变时对应的操作

  /* ---------------- Fields -------------- */
  // HashMap的底层数组，在第一次put的时候才会被初始化，里面每个元素都是Node<K,V>类型
  transient Node<K,V>[] table;

//  键值对缓存集合
  transient Set<Map.Entry<K,V>> entrySet;

  //  key-value mappings 键值对的数量
  transient int size;

  //HashMap 结构发生改变的次数，对于key更新值不属于结构改变，引起结构改变的事件如：put、remove、clear、compute、merge，其实只要看源码里方法里面是否有出现++modCount或者modCount++
  transient int modCount;

  // The next size value at which to resize (capacity * load factor).\
// 下一次resize扩容阈值，当前table中的元素超过此值时，触发扩容,对于初始默认capacity=16，loadFactor=0.75，那么当table的元素个数达到12时，table进行resize
  int threshold;
  final float loadFactor;

4、构造方法

它有三个构造方法，这里只需解析HashMap(int initialCapacity, float loadFactor)：

public HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity)
public HashMap()

这个构造方法目的是保证数组的初始容量必须为2的n次方，以及相关数值合法性检查

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;
    /*这里很奇怪是吧？threshold就是触发扩容的阈值，在这里应该设定为capacity * load factor，对于默认容量16，则算出的threshold应该是12。但是这里threshold是tableSizeFor计算出，它返回是2的整数幂16。
    关于这里的解释：  
    (1) 如果使用类似new HashMap<>()构造方法，那么threshold初始化值为0,之后第一次put元素时，会被resize()创建table数组时，在resize方面里面threshold被重新赋值为：
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    threshold = newThr;//也即等于12
 		(2) 如果使用类似new HashMap<>(10)构造方法或者new HashMap<10,0.5>构造方法时：
 	那么threshold先被初始化值为16：
 	this.threshold = tableSizeFor(initialCapacity=10);// 16
 	之后第一次put元素时，会被resize()创建table数组时，threshold被重新赋值，过程如下：
 				int newThr=0
 				int oldThr=threshold; //16
 			  ....
	  else if (oldThr > 0) 
	  				{newCap = oldThr;}// 而且创建新数组的容量直接使用oldThr=16
	  
	  if (newThr == 0) {
            float ft = (float)newCap * loadFactor; 16*0.5=8
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);  8
    }
    threshold = newThr; 8
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 前面newCap为16
    table = newTab;
    return newTab; 所以最终返回的是16个null元素的数组，其扩容阈值为threshold = newThr=8，而不是10*0.5
	
 关于(2)的分析方法：
 Map<String,Integer> map=new HashMap<String,Integer>(10,0.5F);
 map.put("foo",10);//使用IDEA，在这里断点debug，然后观察在resize的执行过程即可
 使用条件断点：new HashMap<>()->put->putVal->resize->观察threshold在不同构造方法下的赋值
 */
    this.threshold = tableSizeFor(initialCapacity);
}

​ 关于this.threshold，在resize小节也会被再次提到。

​ 这里tableSizeFor是重点解析方法，它会返回一个大于或等于设定值最小2的n次方数字，例如new HashMap(12)，那么经过tableSizeFor后，table的长度也会被设为16，而不是12，这里cap给定为12作为计算过程示例

    // n=12-1=11，11对应二进制位0000 0000 0000 0000 0000 0000 0000 1011（32位），为了方便演示计算，这里去掉前面28位高位0，取1011
    int n = cap - 1; // 为何将设定的容量值先减1？
    /*右移：最左补0，最右位删掉
    * 1011右移一位再和1011取或
    */
    n |= n >>> 1; //1011 | 0101 = 1111 
    n |= n >>> 2; //1111 | 0011 = 1111
    n |= n >>> 4; //1111 | 0000 = 1111
    n |= n >>> 8; //1111 | 0000 = 1111
    n |= n >>> 16;//1111 | 0000 = 1111
    // 1111也即15，因此返回的是n+1，也即15+1=16，16显然满足大于等于12的最小2的n次方数字
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 
}

对于12这个数字，到了 n >>> 4之后就不需要再计算了。

这里有个trick：1+2+4+8+16=31，显然，只要右移动累计够31位，对于int四个字节无论再大的数，都可找到与n对应的二进制数且全部位都为1。那么在在它基础上加个1，即可算出大于等于这个数的最小2^n次幂整数（最大数为2^31次方），当然如果找到最大的数为2^31，它已经大于MAXIMUM_CAPACITY=2^30，因此即使给定数例如2^30+111,经过tableSizeFor后，也只能返回MAXIMUM_CAPACITY

此外`n = cap - 1，这里有个对设置值进行减1操作，设计原因如下:假定给定new HashMap(16)

    int n = cap  // 考察不减1的情况,这里cap=16，对应10000。
    n |= n >>> 1; //10000 | 01000 = 11000 
    n |= n >>> 2; //11000 | 00110 = 11110
    n |= n >>> 4; //11110 | 00000 = 11111
    n |= n >>> 8; //11111 | 00000 = 11111
    n |= n >>> 16;//11111 | 00000 = 11111
    // 11111对应31,这里返回的是n+1,也是31+1=32
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 

既然new HashMap(16)给定的16设定值恰好满足2^4次方条件，可直接return，但因为采用int n = cap方式，导致返回的容量是32，显然浪费了一倍空间，因此int n = cap-1保证返回的值一定是大于等于cap的2^n次数。

5、Node节点定义

由于本次文章不包含HashMap里面的红黑树结构，因此只给出普通Node节点说明，定义相对简单：节点必须实现hashCode和equals方法

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // 用于存放该节点的hash值，避免重复计算
    final K key;
    V value;
    Node<K,V> next; // 用于指向下一个节点

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

  
    // 节点与节点之间的判等
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {  // 如果Object类型的o对象时Map.Entry类型，则先将o对象强制类型转换为 Map.Entry<?,?>类型，以便两个节点使用可以相同方法进行equals判等
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

Node内部静态类相对简单，这里不再累赘。

5、理解hash扰动函数

如何将一个Node节点put到数组对应的位置（桶位）？

​ 设计较为简单：由该节点的key的hashcode经过一个扰动函数之后再与table的长度进行与运算得出index，这个index对应桶位就是新增Node节点要插入的位置，当然需要调用put方法才能实现放入一个新增元素，计算公式为：

int n=capacity; // 数组容量，2的整数幂
int hash=hash(key) // 扰动哈希函数hash对给定的key计算出对应的哈希值
int i =  hash & (n - 1);  // 使用位与运算，算出桶位所在的数组的索引号
Node<K,V> p=table[i];  

接下来看看i = hash & (n - 1)工作原理：假设目前数组为默认初始容量16，put四个key到HashMap里面

虽然四个key的hash值都不相同，但四个key都定位到同一个桶位上，为何会这样？观察一下计算过程：

    // 注意这里不是使用hashCode方法计算，而是hash扰动方法，该方法见后面解释
System.out.println(hash("foo00")); // 97614999
    System.out.println(hash("foo11")); // 97615031
    System.out.println(hash("foo22")); // 97614935
    System.out.println(hash("foo33")); // 97614967

​ 以上四个hash值对应的二进制和(16-1)进行与运算后算出的桶位索引号都是7，桶位冲突，显然这四个key对应的节点将在table[7]形成一条冲突链表。此外，从计算过程可以观察出数组长度-1对应的二进制1111恰好形成一个对高位的掩码，“与”操作后，key的高位全部置为零，只保留低4位，这个值就就是给定key的桶位索引号7。

这样设计有什么好处？

不管给定的key多大，例如key是一个整数1073741821，通过以上与运算，在计算过程中，永远只有key的低n位参与到位运算（这里n就是数组长度2^n里面的n次幂数字。例如上面的foo00例子，若数组长度16，n就是4），这这方式屏蔽了高位，能非常快速计算出index，利用底层cpu的位运算能力来加速得到桶位索引号，这个设计确实很巧妙，这也是为何数组长度要设计2的整数幂原因之一。

但这里是不是有个担心的地方？

即使给定的key有多大或者可以分布均匀，按照上面的算法，运算后仅有低n位的值，这不就加大了桶位冲突吗？原本想让均布分别的key能够均匀分别到数组大部分桶位上，结果反而更加冲突了？ 

对于这个问题，好在HashMap已经想到这一点，不是直接使用i = hashCode & (n - 1)，更好的处理方法：

i = hash & (n - 1)，这里hash就是扰动函数

既然如果直接用key的hashCode和table.length-1进行与运算后，key高位信息就会被置0，导致key无法合理离散分布。那么可以再这样设计，让key右移16位，和原key的hashCode进行异或运算，使得key的高位信息特征能够“融入”到低位中，经过这种“扰动”处理，在进行`i =  hash & (n - 1)`后，能进一步降低哈希冲突。

如何使得key的高位信息特征能够“融入”到低位中？以下就是hash(key)内部实现为：

static final int hash(Object key) {
    int h;
    /*假设现在有个一key对应的hashCode如下
    * 0100 1010 0000 0000 0101 0000 1011 1101，h
    * 0000 0000 0000 0000 0100 1010 0000 0000 ，h>>16，
    * 0100 1010 0000 0000 0001 1010 1011 1101，h^h>>16 ,异或运算：同为0，异为1
    */
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

(h = key.hashCode()) ^ (h >>> 16)能够把key的高16位信息“融入”到低16位中，当进行桶位bucketIndex计算时，被16位全为1的table长度&运行后，后得到低16位是包含高16key高位信息，以期减少哈希冲突。

6、如何快速制造桶位冲突的键

假设让所加的key都定位到数组索引号10，数组初始容量为16，生成过程如下

public class Demo {
    static class Util {
          /**
         * @param collidedIndex  指定桶位冲突的位置，也即定位元素碰撞的数组索引号
         * @param tableSize  指定数组容量
         * @param num  指定生成冲突key的个数
         * @return 
         */
        public static List<Integer> makeKeyCollision(int collidedIndex, int tableSize, int num) {
            int target = hash(collidedIndex) & tableSize - 1;
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < Integer.MAX_VALUE; i++) {
                if (list.size() == num) break;
                int bucket_index = hash(i) & tableSize - 1;
                if (bucket_index == target) {
                    list.add(i);
                }
            }
            return list.subList(0, num);
        }

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


    public static void main(String[] args) throws InterruptedException {
        Map<Integer, String> map = new HashMap<>();
        // 要求在桶位10上生成10个hash冲突节点
        List<Integer> list = Util.makeKeyCollision(10, 16, 10);
        // [10, 26, 42, 58, 74, 90, 106, 122, 138, 154]
        for(int key:list){
            map.put(key,"foo"+key);
        }
      
}

其实这个冲突的key很好找，如果给定一个key为10，那么其他key生成方式为nextKey=10+tableSize*n，n=0,1,2,3,4…，因此生成冲突key另外一种方法：

public static List<Integer> KeyCollision(int collidedIndex, int tableSize, int N) {
       int i;
       List<Integer> list= new ArrayList<>();
       for(i=0;i<N;i++){
           list.add(collidedIndex+tableSize*i);
       }
       return list;
   }

6、put（putVal）方法

在前面第5点已经知道如何将一个新增节点定位到数组里面对应的桶位，那么找到桶位后，如何放置呢？

putVal的分析要结合HashMap是由数组、链表和红黑树构成的原理进行理解，以下源码是针对类似这样的操作map.put("foo",10)：key为”foo”,value为10。

以下代码总体思路：

以下为源码对应的实现

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        /* 
         tab表示当前HashMap的table，临时变量
         p表示table的桶位节点（或者称为桶位头节点、桶位首节点），临时变量
         n表示table哈希表（数组）的长度，临时变量
         i表示key定位到的桶位下标位置（简称桶位位置），临时变量
        */
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        /* 只有第一次put时才会触发初始化逻辑，这时HashMap的talbe才会被resize()方法在内存创建出来,换句话说在new HashMap()时，table不会被创建到内存。这种叫惰性创建。
         if ((tab = table) == null || (n = tab.length) == 0)  // 将这句代码分开写：
				 tab=table;
				 n=tab.length; 
				 if((tab==null)|| n==0) // 显然如果table为null或者table数组长度为0，说明是第一次put
        */
        if ((tab = table) == null || (n = tab.length) == 0)
         /*tab = resize() //调用resize初次创建table
         * n=tab.length; //初次创建tabel,数组长度显然为n=16
         */
            n = (tab = resize()).length;
  			
 			/* 对应第2条思路:如果定位到数组的桶位上的元素table[i]恰好为null,直接将该新节点放入该桶位，而且next指向null
  		* Node<K,V> p = tab[i = (n - 1) & hash];
  		  if(p==null){
  		   		tab[i] = newNode(hash, key, value, null); 
  		  }
  		*/
  		// p指向的是桶位的头节点，若该头节点为null，则说明桶位是空，则放入新节点即可完成put操作
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // p指向的是桶位的头节点，若该头节点不为空null，则说明桶位上可能是红黑树节点或者冲突链表
        else {
            
            //  Node<K,V> e节点临时变量，如果给定的key不为null，且当前桶位的节点key与给定的key一致，将将当前桶位节点p赋给临时变量e，k表示一个key临时变量，用于后续k=p.key赋值操作
           /*
           K k=p.key;
           Node<K,V> p = tab[i = (n - 1) & hash];
           if (p.hash== hash && ((k==key) || (key != null && key.equals(k))) ) 
           // p.hash == hash && ((k==key) 用于判断新增节点key为null或者key为基本类型的情况
    			 // p.hash == hash && (key.equals(k)) 用于判断新增节点key是不为null的引用类型情况,这样才能保证key.equals(k)不会出现NullPointerException
           */
            
            Node<K,V> e; K k;
            if (p.hash == hash &&
                 // 新节点Node与p刚好哈希碰撞,且两者的key相等。
                ((k = p.key) == key || (key != null && key.equals(k)))) // 这句能够证明java8的HashMap支持key为null插入。
                e = p;
           // 对应第3思路的的2)方向：
          // 如果新节点Node与p刚好哈希碰撞，但两者的key不等，当p为TreeNode，那么只需将新增节点Node放入到这课以p为根节点的红黑树。
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 对应第3思路的的3)方向：说明定位到该桶位的第一个节点：
                // Node<K,V> p = tab[i = (n - 1) & hash]是链表上的节点,使用链表遍历，将新节点插入到合适位置。
                // binCount用于计算出该桶位上链表的长度
                for (int binCount = 0; ; ++binCount) {
                    // 若遍历到链表尾，直接p.next指向newNode完成新增节点
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);  //也即所谓的尾插法
                        // 判断新增节点后，链表长度（桶节点个数）是否大于树化该桶链表的阈值8-1
                        //因为binCount从0开始，因此binCount等于7时，说明该桶位上链表长度为8，触发树化操作
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break; // 完成以上操作后，退出链表遍历。
                    }
     // 若遍历链表还未到尾部，例如在链表中间恰好找到一个链表上的节点e，它与给定key有哈希碰撞，且两者key相同，那么将退出该桶位上的链表遍历。
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e; // 用于链表下一轮遍历
                }
            }
          
            /* 以下操作是针对找到与给定key相同的节点三种情况进行更新值操作
            1) 当前桶位table[i]的p节点恰好与给定的key相同
            Node<K,V> p = tab[i = (n - 1) & hash]
            e=p;
            2) 当前桶位table[i]的p为treeNode，在红黑树里面找到一个与给定key相同的e节点
            TreeNode<K,V> p = tab[i = (n - 1) & hash]
            以p为根节点的红黑树在遍历过程中找到一个与给定key相同的e节点：
            e=p;
            
            3) 当前桶位table[i]的p为链表，在该链表中找到一个与给定key相同的e节点
            Node<K,V> p = tab[i = (n - 1) & hash]
            以p为根节点的链表在遍历过程中找到一个与给定key相同的e节点：
            e=p;
            */
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value; // 更新valu
                afterNodeAccess(e); // 在新增节点操作之后，需要对遍历过程的临时节点e做什么操作，源码未实现任何操作。
                return oldValue; // 显然更新值putVal就直接return了，不会执行后面++modCount这一句。这里证明更新值不会对HashMap结构产生变化。
            }
        }
  			/*
  			若程序能运行到++modCount这一句，说明一定是以下三种情况之一：
  			1、在tab[i]为null时为其新增一个节点
  			2、在treeNode增加一个节点
  			3、在冲突链表上新增节点后
  			*/
        ++modCount;
        if (++size > threshold) // 对于思路4：数组size长度加1，并判断是否大于threshold，大于则扩容
            resize();
        afterNodeInsertion(evict);
        return null; // 若新增节点被成功插入，则put方法的返回值为null
    }

7、resize()

原理与图解分析

(注意：本节内容重点放在HashMap数组、数组上的非treeNode节点、桶位上的链表，所作图也不包括tree bins 红黑树，所有关于红黑树的内容在另外一篇文章给出）

首先需明白为何要resize扩容？

先从逆向思维进行思考：若不对数组进行resize扩容，那么Node<K,V>[] table数组长度将固定在16。

考察一种情况：

不断往这个HashMap put元素后，例如随机put10万个元素到这个map，由于其底层table长度固定为16，根据抽屉原理也可以推出：至少99984个元素会在找桶位时发生哈希冲突，不妨假设会出现这种情况：数组的15个桶位位置形成15条bin链表（长度为7），总共可放置7*15个元素，剩下一个桶位将有(100000-7*15)个元素构成一课庞大的红黑树

（1）在查找一个key时，若该给定的key位于15个桶位位置形成15条bin链表的某种链表，时间复杂度最差也是只是查询7次，还可接受。

（2）在查找一个key时，若该给定的key位于这颗大的红黑树里面，那么查询时间复杂度最差为O(2logn)次，也即23次。

​ 目前固定table的长度看起来“查询需求”的效率还可接受，但仍然无法达到0(1)效率，还不如使用TreeMap

若采用扩容，虽然数组的容量变得更大，数组占用内存多，但带来额外的收益：

考察一种情况：假设还是put入10万个，对应的扩容数组容量为131072,也即2^17，若10万个元素都能平均分布在每个桶位上，也即这个HashMap底层的table数组每个元素就是节点，那么完全可以达到o(1)性能，且几乎无哈希冲突。

当然：table长度扩容到2^17，占用不少内存空间，这是典型的用空间换时间的例子。

实际情况不会出现10万个元素完全分布在不同的桶位上，更多常见的是：一部分的元素位于桶位第一个位置上，一部分元素在链表上，一部分元素在tree bin红黑树上。

扩容后，桶位上元素的索引在原表和新表上区别：the elements from each bin must either stay at same index, or move with a power of two offset in the new table.意思是说，扩容后，桶位上元素的索引号要么跟之前相同，要么就是元素所在的新表位置在索引号+oldTable.length

以下源码解析部分：

在前面的putVal方法，出现resize调用的场合：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;  // 第一次put时，用resize初始化了一个长度为16的空table

它是如何初始化？

这里需要可通过IDEA里面debug相关过程即可知道resize的设计过程：

• 1) 第一种情况：针对第一次put key时，在putVal方法里面：n = (tab = resize()).length;

Map<Integer, String> map = new HashMap<>();
map.put(5,"foo"+5); // 对其设置断点

通过debug观察resize的初始化流程Force Step Into先进入内建方法，再使用Step out 返回，直到出现resize的调用后，使用Force Step Into进去方法内部，接着即可单步debug也即Step Into。

当然也可以使用condition条件设置debug直接跳到这里的条件成立： if ((tab = table) == null || (n = tab.length) == 0)

resize内部参与执行的语句，不满足执行条件的代码被忽略

    Node<K,V>[] oldTab = table; // null
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // oldCap=0
    int oldThr = threshold; // oldThr=threshold=0
    int newCap, newThr = 0; 
....
   else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY; // newCap使用默认容量16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // newThr=16*0.75=12
    }
......
threshold = newThr;// threshold = newThr=12
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 空Node数组，容量16
    table = newTab;// table=Node[16]
......
    return newTab;

可以看出，如果第1次往map里面put key，对应resize的执行流程相对简单

• 2) 第2种情况，也是第一次put key，只是使用的构造方法不同

Map<Integer, String> map = new HashMap<>(10,0.5F); //自行定义了初始数组容量和负载因子
map.put(5,"foo"+5); // 对其设置断点

resize内部参与执行的语句，不满足执行条件的代码被忽略

    Node<K,V>[] oldTab = table; // null 
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // // oldCap=0
    int oldThr = threshold; // 这里threshold=16，因为 new HashMap<>(10,0.5F)里面调用了this.threshold = tableSizeFor(10)
    int newCap, newThr = 0;
......
    else if (oldThr > 0) // 前面已知oldThr=threshold=16
        newCap = oldThr; // 新数组容量newCap被置为16
......
     
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor; // 16*0.5=8.0
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE); // 新扩容阈值为8
    }
    threshold = newThr; // threshold = newThr=8
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 正式初始化table数组 Node[16]
    table = newTab; // table=Node[16]
.......
    return newTab; 

使用new HashMap<>(10)构造方法同上。可以看出这两种构造方法目的也是为了确认根据给定容量和负载因子值（得到原数组容量0和原扩容阈值16），来计算出新数组容量和新扩容阈值。

3) 第3三种需要resize的情况最复杂：

根据putVal源码可知，若table数组本身已有元素，当新插入一个节点后HashMap的元素数量超过容量时，需进行扩容，参考以下put的逻辑：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length; // 对应前面1）2）的resize情况
        ...... 
        if (++size > threshold) // map的里面的元素个数超过扩容阈值
            resize(); // 对应本次resize情况
        afterNodeInsertion(evict);
        return null;

先给出扩容过程原理图，假设现在给map 放入以下的key:

第一组key：0，1

第二组key：5，21，37，133，309，3189

    Map<Integer, String> map = new HashMap<>();       
map.put(0,"foo0");
    map.put(1,"foo1");

    map.put(5,"foo5");
    map.put(21,"foo21");
    map.put(37,"foo37");
    map.put(133,"foo133");
    map.put(309,"foo309");
    map.put(3189,"foo3189");

根据putVal的桶位(定位到数组的index位置)计算方法:

public static int getIndex(int key,int n){
    return hash(key)&(n-1);
}


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

第一组key：0，1，对应的桶位为0，1

第二组key：5，21，37，133，309，3189，对应的桶位都是5

初始化

因此以上的key在HashMap的分布如下图所示（注意，为方便作图，已忽略节点里面的hash、value、next以及tree bins 红黑树）：

第一次扩容至32

假设该HashMap元素个数已达12个，触发扩容（阈值threshold=16*0.75=12），进行扩容后，HashMap内部结构图如下：

对比前后图可以发现：新数组长度为32，key：21、309、3189对应的节点去到新数组的第21个桶位上，且形成链表。

第二次扩容至64

又再假设假设该HashMap元素个数已达个24个，再次触发扩容（阈值threshold=32*0.75=24），进行扩容后，HashMap内部结构图如下：

对比前后图可以发现：新数组长度为64，

key为5的节点原位置5，在新数组也是5，位置没变

key为133的节点原位置5，在新数组也是5，位置没变

key为21的节点原位置21，在新数组也是21，位置没变

key为37的节点原位置5，扩容后脱离了原链表，落在新数组第37桶位上

key为309、3189的节点原位置21，扩容后脱离了原链表，落在新数组第53桶位上

以上节点在扩容后，如何确定哪些节点应该落到新数组的哪个位置呢？在以下关于数组扩容（resize又称rehash）知识点，可以再次说明数组容量设为2的整数幂是有多方便。

扩容前后，节点迁移过程

根据桶位计算方法：hash(key)&(table.size-1)，对所有key：0，1，5，21，37，133，309，3189使用二进制方式计算

从HashMap内置的hash方法可以得出，对数值key采用hash方法计算后还是这个数值key本身，因此相当于所有key的值，与15进行与运算

对于0，1这两个key，很简单:

对于5，21，37，133，309，3189这5个key，你会发现这些key的低4位都是0101，如下图红色标记所示，和(16-1)与后，高位直接置0，仅留低4位，因此5个key的桶位索引号都为5，换句话说这些key在桶位为5的位置发生冲突，放入HashMap后，就形成一条长链表如前面图示。

• 数组被扩容后，容量为32的节点分布计算

此时hash(key)&(table.size-1)里面的table.size-1的值为32-1，也即31，对应二进制位11111,

对于0，1这两个key，很简单:

对于5，21，37，133，309，3189这5个key，对比数组容量16的情况，和(32-1)与后，高位直接置0，仅留低5位。key的低4位还是0101，对于key第5位要么0要么1，因此和11111与运算后，高位（第5位）有1的key，落在21号桶位上，高位（第5位）有0的key还是落在5号桶位上，因此5、37、133最终保持在index=5位置上，而21、309、3189落在index=21位置上，如下图所示：

以上得出重要的扩容节点位置定位逻辑，如下图所示：该图能可视化解释了resize源码里面关于低位节点和高位节点如何挪动的设计，图的左边是扩容前容量16的HashMap结构，图的右边是扩容后容量32的新HashMap结构

• 数组被扩容后，容量为64的节点分布计算

  这里不再给出，逻辑跟上面一致。

理解高节点hiNode和低节点loNode

有两种方式可以定义，这里以高节点hiNode看看它具备什么特征：

方式1（从新数组容量的角度出发）：假设新数组容量-1对应的二进制位数为n，key哈希值的二进制位从左往右数的第n位为1的话，那么key所属节点即为高节点，例如数组32-1，对应二进制11111位数为5，对于key为21，其hash值也为21，二进制为10101，第5位为1，那么这个21所属节点则称为“高节点”（或高位节点）

同理：假设新数组容量-1对应的二进制值位数为n，key哈希值的二进制位从左往右数的第n位为0的话，那么这key所属节点则称为“低节点”（或低位节点），例如对于对于数组32-1，对应二进制11111位数为5，对于key为5，其hash值也为5，二进制为00101，第5位为0，所以key为5的节点则称为“低节点”（或低位节点）

方式2（从旧数组容量的角度出发）：旧表容量对应的二进制和key哈希值&后的值，该值最高位为1，那么key所属节点即为高节点

(这里要小心了，方式2说的是旧数组容量，不是方式1所提的新数组容量，新数组容量=旧数组容量<<1)

实例说明：旧数组容量16的二进制10000，key为21的哈希值二进制为10101，两者&后，10000，最高位为1，所以这个21所属节点就是高节点。

同理：假设旧容量对应的二进制和key哈希值&后的结果（注意这个结果会是0），该值最高位为0，那么key所属节点即为低节点

实例说明：旧数组容量16的二进制10000，key为133的哈希值二进制为100 0101，两者&后，值为000 0000，当然最高位为0，所以这个133所属节点就是低节点。

16 & 133 => 001 0000 &100 0101，结果为0

HashMap哪些位置上节点才是高节点和低节点对应的特征呢？

经过前面的原理分析，HashMap的结构无非就是数组+冲突链表(bins)+红黑树(tree bins)，所以高节点和低节点的分布如下：

1）数组桶位上的节点：要么是高位节点，要么是低位节点

2）若桶位上已形成冲突链表，那么链表上节点类型可能有三种情况：A、全部节点都是低节点 （低位节点）B、全部节点都是高节点（高位节点）C、低节点和高节点都有

3) 桶位上是一个tree bins红黑树，树上节点类似跟2）情况类似：A、全部树节点都是低节点 （低位节点）B、全部树节点都是高节点（高位节点）C、树所有节点既有含低节点又有高节点

以上三点内容，结合节点扩容迁移图可知：

1）数组桶位、冲突链、红黑树上的高节点，扩容后，在新数组的位置index发生改变，index=原index+原数组容量

2）数组桶位、冲突链、红黑树上的低节点，在新数组的位置index和原数组的位置一样，没有改变，即index=原index

费这么大劲去理解所谓“高节点和低节点”有何用？因为它就是resize内部最核心的设计，理解了它，resize工作原理才能真正理解，也能真正理解为何数组容量要设计为2的整数幂。

resize()核心内容

有了前面原理性分析的铺垫，针对旧数组已有节点的情况下的resize的源码分析将“易如反掌”，resize就是把所有的Node节点重新Hash挪（迁移）到新数组new table上，挪动节点的位置需要按一定规则去挪。

 final Node<K,V>[] resize() {
   			// 临时变量oldTab：表示旧数组，
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
 				// ....省略部分
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // newTab容量一定是2倍旧数组容量
        table = newTab;
   
        if (oldTab != null) {  // 旧数组有节点的情况下才进行扩容
            for (int j = 0; j < oldCap; ++j) {  // 遍历数组每个元素（或者说遍历每一个桶位（槽位））
                Node<K,V> e; // 临时变量，oldTab[j]表示key定位到的桶位头节点，赋给这个临时变量e
                 /* 
                 e = oldTab[j];
                 if (e != null){ 如果旧数组桶位j节点不为空
                 		oldTab[j] = null; //  则先该桶位指向null，用于GC回收
                 }
                 */ 
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                  	 //1、桶位单个节点迁移
                    if (e.next == null) // oldTab[j].next为空，说明这是个单个头节点，不是一条链表，先计算其在新数组的位置i=e.hash & (newCap - 1)，然后newTab[i]=e，完成了这个单个头节点挪到新数组上。注意新数组的位置不是使用该计算方式：e.hash & oldCap
                        newTab[e.hash & (newCap - 1)] = e;
                    //2、红黑树节点迁移
                    else if (e instanceof TreeNode) // 如果oldTab[j]是一个TreeNode，那么进行红黑树的扩容处理，本章暂不给出相关分析，在另外一篇文章给出。
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                   //3、冲突链节点迁移
                    else { // 到了这里oldTab[j]上有一条冲突链，需要将高节点和低节点分别取出，放到新数组对应位置。
                      
                        // preserve order,这是源码注释：1.8的HashMap扩容后还可以链表上节点前后指向不变。乍一看好像没啥，其实以下代码说表达就是面试过程最核心的一个问题： 头插法和尾插法、为何什么java 7的头插法在扩容阶段容易因此死循环？ 

                     
// 低节点构成新链表的头、尾节点临时变量：loHead->node->node-...->loTail->null, 存放旧数组oldTab[j]冲突链上的低节点
                        Node<K,V> loHead = null, loTail = null;
// 高节点构成新链表的头、尾节点临时变量：hiHead->node->node-...->hiTail->null, 存放旧数组oldTab[j]冲突链上的高节点
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next; // 临时变量，存放遍历原冲突链表的下一个节点,和e搭配，形成循环
                        /*
                        do{
                        		next=e.next;
                        		//低高链表处理
                        		e=next;
                        } while(e != null)
                         */
                        do {
                            next = e.next;
                            // 从前面低节点特征定义可知，冲突链表的低节点和旧数组容量&后为0，例如
                            // *** 0 0101 & 10000 = 0 0000 =>0
                            if ((e.hash & oldCap) == 0) {
                              if (loTail == null) // 如果loTail为空，说明还没创建低节点链表
                                    loHead = e; // 因此将当前遍历的e节点作为低节点链表的头节点
                                else
                                   // 说明已存在低节点链表，只需将当前遍历的e节点作为该链的尾节点即可。
                                    loTail.next = e;
                                loTail = e; // 用于后面：if (loTail != null) loTail.next = null;
                            }
                            else {
                             //从前面低节点特征定义可知，冲突链表的高节点和旧数组容量&后为1 
                                if (hiTail == null) // 如果hiTail为空，说明还没创建高节点链表
                                    hiHead = e; // 因此将当前遍历的e节点作为高节点链表的头节点
                                else
                                  // 说明已存在高节点链表，只需将当前遍历的e节点作为该链的尾节点即可。
                                    hiTail.next = e;
                                hiTail = e; // 用于高节点链表遍历
                            }
                        } while ((e = next) != null);
                        if (loTail != null) { // loTail不空，说明从旧桶位j的冲突链表上“分离出”低位节点链表
                            loTail.next = null; // 这里表明java8的HashMap扩容阶段的冲突链上采用尾插法
                            newTab[j] = loHead; // 低节点链表放在新数组的（原index）对应的位置
                        }
                        if (hiTail != null) { // hiTail不为空，明从旧桶位j的冲突链表上“分离出”高位节点链表
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead; // 高节点链表放在新数组的（原index+原数组容量）对应的位置
                        }
                    }
                }
            }
        }
        return newTab; // 返回扩容后的新数组引用
    }

这里的难点在 ：loHead、loTail 以及hiHead、hiTail的工作原理：

旧数组桶位号index=5上的冲突链：

5->21->37->133->309->3189->null，节点迁移到新数组，被if (e.hash & oldCap) == 0)分成以下两条链

新数组桶位号index=5上的低节点链：

loHead(5)->node(37)->loTail(133)->null

新数组桶位号index=5+旧数组capacity上的高节点链：

hiHead(21)->node(309)->hiTail(3189)->null

可以看出，在old table已经有元素的情况下，resize的过程会触发较多操作（创建新数组、红黑树spit、原冲突链分开为高低节点链等），换句话说，若频繁触发resize，会拖慢HashMap实际使用性能，因此在使用过程中，可以预估好容量再new HashMap

8、get方法

有了前面putVal和resize的深度解析，关于get、remove、replace方法都很容易理解，从注释可以看出HashMap的get方法是实现了Map接口的get方法，从源码可以知，getNode才是内部实现。

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
 * Implements Map.get and related methods.
 */
final Node<K,V> getNode(int hash, Object key) {
   /*
   tab:当前HashMap里面数组table的引用
   first：桶位中的头节点
   n：table的长度
   e：临时Node节点
   k：key的临时变量
   */
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    /*
      hash=hash(key);
    	tab=table;
  		n=tab.length;
  		first = tab[(n - 1) & hash;
  		if(tab != null && n>0 && first !=null) 如果table不为空 且长度>0且所定位到的桶位节点不为空
  	*/	
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
      	
      // 先判断桶位上的first节点key是否与给定key一致，若一致则返回该桶位头节点first
        if (first.hash == hash && 
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
      // 给定key所定位到的桶位节点的next指针不为空，说明该桶位上要么有一条冲突链，要么有一棵红黑树
        if ((e = first.next) != null) {
            // 1、针对当前桶位是一个红黑树节点的情况
            if (first instanceof TreeNode) // 如果first是TreeNode类型，那么使用getTreeNode继续去查找key
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
             // 2、针对当前桶位是一条冲突链的情况。
               // 否则在冲突链表上进行遍历，若当前遍历节点e的hash与给定key的hash一致且值相等，说明已找到，返回该e即可。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

getNode逻辑比较简单（红黑树的getTreeNode逻辑会更复杂）。

9、remove方法

内部逻辑由removeNode实现。

整体思想：先根据key数组去找到node（node可能位于数组索引位置上（桶位）头节点，或者冲突链上，或者红黑树上），然后再使用内部的removeNode方法删除该node

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

/**
 * Implements Map.remove and related methods.
 *
 * @param hash hash for key，给定key的哈希值
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @param matchValue if true only remove if value is equal，要求key和value相同时才删除该节点
 * @param movable if false do not move other nodes while removing，是否可删除节点，
 * @return the node, or null if none
 */
			
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
   /*
   tab:当前HashMap数组table的引用
   p：桶位中的头节点,p=tab[index = (n - 1) & hash]
   n：table的长度,n = tab.length
   index：数组元素索引号(key定位到的桶位置)，index = (n - 1) & hash
   */        
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    /*
      hash=hash(key);
    	tab=table;
  		n=tab.length;
  		index = (n - 1) & hash;
  		p = tab[index];
  		if(tab != null && n>0 && first !=null) 如果table不为空 且长度>0且所定位到的桶位节点p不为空
  	*/	      
  
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
         /*
         Node<K,V> node = null,临时节点，用于放置找到与给定key相同的节点
         Node<K,V> e,遍历冲突链时的临时节点
         */
         
        if (p.hash == hash &&
            // 当前桶位上的节点p与给定的key相同，说明p就是要删除的节点。
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 若key不同，则桶位上p节点要么是tree bin红黑树根结点，要么是冲突链bins的根节点
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
              // 若p节点是TeeNode类型，则在红黑树找出与key相同的节点
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
              // 否则在冲突链上找到与给定key相同的节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e; 
                        break; // 在冲突链上找到要删除的节点，则结束链表遍历
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 上面根据给定key找到这个节点若不为空，且不需要value匹配
  /* 以下两句表达式一个是判断给定key与当前定位的节点key是否相等
      一个是判断给定value与当前定位的节点的value是否相等
  (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k))))
  (v = node.value) == value || (value != null && value.equals(v))
  */
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
          	// 如果找到的node节点是红黑树类型节点，则对应执行红黑树节点删除方法
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 如果找到的node节点就是桶位上的头节点p，则node下一个节点放到桶位上即可
            else if (node == p)
                tab[index] = node.next;
            // 如果找到的node节点是冲突链上节点，将node下一个节点放到p的next，完成node节点本身的删除
            else
                p.next = node.next;
            ++modCount; // 因为前面已经删除了一个节点，所以HashMap结构发生了一次变化，需要记录
            --size;
            afterNodeRemoval(node);// 删除一个节点后回调方法，默认为空操作。
            return node;
        }
    }
    return null;
}

对于三种类型节点的删除逻辑代码设计如下图所示：

10、putAll

将一个HashMap放入到另外一个HashMap里面

Map<Integer, Object> map = new HashMap<>();
Map<Integer,String> map1=new HashMap<>();
map.put(0,"foo0");
map.put(1,"foo1");
map.put(5,10);

map1.put(21,"foo21");
map1.put(37,"foo37");
map.putAll(map1);
System.out.println(map); // {0=foo0, 1=foo1, 5=10, 21=foo21, 37=foo37}

源码实现放在putMapEntries方法里面：

(总体设计：将新map里面元素放入到旧map里面，例如Map可以容纳Map类型、入Map类型)

  // 注意Map的key和value是上界通配符，注意类型兼容情况
public void putAll(Map<? extends K, ? extends V> m) {
      putMapEntries(m, true);
  }
  
  final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
      int s = m.size(); // 新map的元素个数
      if (s > 0) { // 
          if (table == null) { // 新map的数组容量有无超过旧map设定的扩容阈值，其实需带入相关默认值即可了解下面两句代码的意义，例如旧map使用new HashMap<>(),那么默认容量为16，loadFactor=0.75，threshold=12
            //若新map目前有3个元素，则s=3,因此ft=3.0F/0.75F+1.0F=5.0F
            //t= 5,显然t小于旧map的扩容阈值，因此无需进行tableSizeFor
            // 简单说，旧map容量为16，新map才3个元素，当然可以直接放入，无需扩容等操作。
              float ft = ((float)s / loadFactor) + 1.0F;
              int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                       (int)ft : MAXIMUM_CAPACITY);
              if (t > threshold)
                  threshold = tableSizeFor(t);
          }
          else if (s > threshold) // 新map的元素个数超过旧map的扩容阈值，则直接先对旧map进行扩容操作
              resize();
          // 当旧map的容量足够容纳新map的元素个数，则遍历新map元素，复用putVal方法，将其放入到旧map里面
          for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
              K key = e.getKey();
              V value = e.getValue();
              putVal(hash(key), key, value, false, evict);
          }
      } // 若新map的元素个数为空，则不做任何操作
  }

三、小结

关于java8的HashMap的其他方法如：clear()、’containsKey’、’containsValue’、’replace’等方法不再讲解，这些方法实现相对简单，关于HashMap红黑树部分的核心方法将在下一篇文章给出。

四、部分经典问题讨论

1、在桶位计算里面，hash方法为何采用异或运算而不是“或”“或非”等逻辑运算？

这个概念非常巧妙和重要：

• 找出两个数有差异的位，a^b得到的结果中，1表示在该位两数存在差别，0表示无差别，回看hash的计算方法

  h = key.hashCode() ^ (h >>> 16)

  这种方式能找出key1有差异的位，同理也可以找出key2有差异的位，那么这种方式计算出来key1的哈希值和key2的哈希值将不同，从而把key1和key2的hash值“尽量分散”。

  （1）异或运算的作用能够识别出key的hash高16位只要有一位不同，最终使得不同key对应不同的hash值

  （2）hash计算采用异或运算能够让两个hash整数运算后，不会出现溢出：不进位有什么好处，例如有个key的hash值为2^31-1，它和(2^31-2) 异或后，还是31位，且能找出有差异的位

  异或其实就是是不带进位的加法器（又称半加法器）
  0+0=0
  0+1=1
  1+0=1
  1+1=0（不进位） 

2、HashMap的构造方法里面为何要将初始容量设为16，而不是2、4、8或者32或者其他奇数值？

1）首先数组容量长度设计为2的整数幂有两个收益

第一个收益：扩容阶段，能快速计算节点在新数组的桶位

第二个收益：扩容阶段，能快速将原数组的冲突链上的高位节点和低位节点“分离出来”，然后方便放到新数组相应桶位上

2）如果设为2、4、8或者32的情况：

对于数组容量设为2，4，8当然可以，但也导致了put的前期节点更加频繁扩容，而初始容量为32，对于又会有点点浪费内存，所以16算是一个相对平衡的值，这也是一个trade-off，空间和时间的权衡

3、HashMap的构造方法里面为何要将load factor设为0.75？而不是0.73、0.5、0.65、0.85？等，以下有三种解释：

1）第一种是本人对其解释：0.75化为分数形式为3/4，那么基于数组容量会被tableSizeFor设为2的整数幂，分母的4，那么扩容阈值threshold=2的整数幂*3/4算出的值也是整数。按这种说法设为0.5也可以吗，当然可以，但是0.5降低扩容阈值，会让HashMap更早（更高概率）触发resize操作，影响HashMap性能。 对于0.65、0.85写成分数分别为13/20、17/20，显然对于数组容量为2^n来说，无法整除分母，计算threshold得出非整数，这种方式若放在JDK源码里面，显得很不严谨，也不合理（因为人类喜欢看到类似整数的东西，若出现小数即显得“繁琐”又不好”记忆”）

2）基于泊松分布概率

如果key的hash算法离散性好，那么不同key定位到某个桶位的这一事件将变成随机事件，恰好能用泊松分布来观察key的分布情况，而且当load factor设为0.75时，由于采用足够分布均匀的随机hashcode算法，那么在桶位上(hash槽)出现冲突链且元素个数达到8的概率为0.00000006，非常小，不到百万分之一。

换句话说，设为0.75时，只有百万分之一概率桶位上节点出现8个元素，显然这能大概率减少触发树化操作，从而提升HashMap性能。

3）官方说明

首先是 Oracle官方的Java docs

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor.

…..

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put).

As a general rule 也即根据经验（软件工程实践），0.75可以在时间成本和空间成本上取得最佳平衡，高于0.75，map填得越满，碰撞概率越高（想想抽屉原理或者结合上面的知识点即可理解）

其次来自wiki的一个中文解释，还不错，链接

对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放定址法的hash库，例如Java的系统库限制了荷载因子为0.75。

4、java开发手册中为何建议将(int) ((float) expectedSize / 0.75F + 1.0F)

先看个简单计算：例如new HashMap(6)，在内部因为有tableSizeFor方法，会将数组给定容量从6变为8，那么下次扩容阈值就变成8*0.75=6，也即数组元素个数到达6时就触发resize，这个操作我们知道它让HashMap有性能损耗。

如果采用 expectedSize / 0.75F + 1.0计算出给定的初始容量，那么对于上面的6来说，initialCapacity=6/0.75+1.0=9，

也即使用new HashMap(9)做初始化，这样tableSizeFor方法会将其table容量设为16，于是扩容阈值变为12，也即数组元素个数到达12时再触发resize，显然比前面new HashMap(6)情况，已经降低一半的扩容概率。

当然代价就是牺牲了空间，原来占用8，现在占用16，占用空间增加一倍，但扩容概率降低一倍，典型的trade-off。