HashMap源码分析

介绍

HashMap是基于Map接口的实现，位于java.util包下，HashMap类似于HashTable，
作用主要是存放键值对，和HashTable不同的是，
HashMap不是同步的，是线程不安全的，且允许空值。
HashMap不能保证它的节点的顺序随时间不变，也就是说Map里面的节点的顺序是不断变化的。
这里所使用JDK版本是8。
Map家族的整体结构：

Map下不同实现类的特点

HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。
LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。

HashMap的类图如下：

HashMap的类定义如下:

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

不着急，我们再看看AbstractMap的类定义：

public abstract class AbstractMap<K,V> implements Map<K,V>

为什么HashMap要声明implements Map？

在这里，细心的同学就发现了，HashMap继承了AbstractMap，而AbstractMap又实现了Map接口，
为什么HashMap还要声明implements Map呢？是不是多此一举，这样的地方不止一处，
我们可以在集合框架中观察到很多这样的现象，比如LinkedHashSet的定义：

public class LinkedHashSet<E> extends HashSet<E> 
implements Set<E>,Cloneable, java.io.Serializable

这个地方和HashMap的定义极其相似，我们最终在stackoverflow上找到了答案：

I’ve asked Josh Bloch, and he informs me that it was a mistake.He used to think, long ago, that there was some value in it, but he since “saw the light”. Clearly JDK maintainers haven’t considered this to be worth backing out later.

Josh Bloch是集合框架的创始人，集合相关的类上的作者声明基本都有他的名字，他认为这是一个失误，当初设计时认为在某些地方是有价值的，后来看到了光，但是这个呢不影响什么，所以JDK维护者也一直没有修改它。
原地址：
https://stackoverflow.com/questions/2165204/why-does-linkedhashsete-extend-hashsete-and-implement-sete

数据结构

Map接口的定义

由于HashMap实现了Map接口，我们先看Map接口的定义：

public interface Map<K,V> {
    int size();
    boolean isEmpty();
    V get(Object key);
    V put(K key, V value);
    V remove(Object key);
    void clear();
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
    // .... 省略了一些接口方法
    interface Entry<K,V> {
        K getKey();
        V getValue();
        V setValue(V value);
        boolean equals(Object o);
        int hashCode();
        // .... 省略了一些接口方法
    }
}

可以看出，Map接口内部还有一个接口Entry，这个Entry就是Map里面实际的节点，也就是键值对。
Entry接口定义了getKey，getValue等函数，Map则定义了keySet，values，entrySet等函数。

Node键值对

Map.Entry在HashMap中的实现是Node，看看源码:

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        // key值
        final K key;
        // value值
        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) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

可以看出Node是一种链表结构，存储了key和value的信息，用next指向它挨着的下一个节点。

HashMap的内部结构

HashMap内的静态变量

HashMap内的静态变量如下：

    // 默认初始化的容量，16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // 最大容量，2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认负载因子，0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 节点树化阈值，8
    static final int TREEIFY_THRESHOLD = 8;
    // 解除节点树化阈值，6
    static final int UNTREEIFY_THRESHOLD = 6;
    // 最小树化容量，64
    static final int MIN_TREEIFY_CAPACITY = 64;

HashMap内的成员字段

HashMap内的成员字段如下：

    // 表，长度始终是2的幂
    transient Node<K,V>[] table;
    // entrySet 缓存
    transient Set<Map.Entry<K,V>> entrySet;
    // 表中键值对的数量   
    transient int size;
    // 表结构修改次数，用于fail-fast机制
    transient int modCount;
    // 下次扩容的阈值，(容量 * 负载因子)
    int threshold;
    // 负载因子
    final float loadFactor;

Node数组就是HashMap的内部存储结构，每一个Node又是一个链表，
所以HashMap = 数组 + 链表。
不过我们注意到Node下面还有子类LinkedHashMap.Entry，LinkedHashMap.Entry的子类是HashMap.TreeNode，这个TreeNode就是树节点，根据里式替换原则，Node节点也是可以表示为这个TreeNode的，所以HashMap=数组 + 链表 / 树。

下面是几个面试题，一个一个来：

table的长度为什么始终是2的幂？（hash & (n -1)）

这是因为，为了高效存取，
在存取元素时都需要根据元素的hash值计算下标，算法为：hash & (n -1)
hash是节点的hash值，n是hash表的大小，
它的目的是将key转换为数组下标，
hash值我们知道是一个int值，4个字节，32位，有可能很大
而hash表的大小n一般很小，一般在2的16次方以下吧，
为了hash的计算结果在0到n范围，不要溢出hash表的范围，一般对hash值采用取余算法
将hash / n的余数设置为数组下标，这样余数就是[0,n)，和hash表下标[0,n)一致，
即 hash % n作为下标，正好满足节点下标下落范围的要求。

而hash & (n -1)实际与 hash % n 的效果一致，但前提是n为2的幂次方，
那为什么会一致？
假设n是2的n次幂，比如2，4，8，16，二进制分别表示为10，100，1000，
通过观察发现都是开头一个1，后面n个0的格式，
然后我们观察下n-1的格式，比如1，3，7，15，二进制分别表示为1，11，111，1111
可以看到n-1这个值的二进制的表示永远是n个1的叠加。
&与运算我们都知道，两个同时为1，结果为1，否则为0,
用hash & (n -1)，比如 100100101 和 111 做&运算，那么结果是101，
就是说hash值前面的部分会被丢弃，
最后结果会是0到n-1的一个数字，和 hash % n 是异曲同工之妙。
而且&位运算操作做位运算比%效率更高，这个操作保证了下标落在0到n范围内，结果会在hash表的整个空间内随机下落，不会溢出也不会有存储不到的下标。
所以为2次幂的目的就是为了高效的存取，也为后面的下标算法埋下了伏笔，&运算比%运算会真的快很多。
这也解释了每次table扩容为什么要扩容大小是原来的2倍的原因也就在于此。

初始容量为什么要写成1 << 4，不直接写成16？

从字节码角度而言，1 << 4也会编译成16，所以和直接写16是一样的。
写成1 << 4是为了提醒你这个值始终是2的幂。
至于为什么是16，16作为一个经验值不会太大也不会太小。

最大容量为什么是1<<30而不是1<<31?

首先最大容量为一个int值，int占32位，可以表示2^32个数字。
但是int在java里作为一个有符号的数据类型，有正负之分，所以表示范围是-2^31 ~ 2^31-1。
这里最大值就是2^31-1，为什么减一不用多说了吧，因为0占了一位。
1<<30等同于2^30，而HashMap每次扩容是2倍*当前容量，当容量达到最大值2^30时，再扩容就是2^31了，这时会产生溢出，超过了int的最大值2^31-1，所以最大容量只能是2^30也就是1 << 30。

默认负载因子为什么是0.75？

这个简单，0.75是一个好数字啊，0.75是在时间和空间成本上的一种平衡，太小了将会导致频繁的rehash，而且空间浪费大，太大了hash冲突将会频繁产生，性能也不高。

树化阈值为什么是8？

这个答案在jdk注释里面就有

• 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
  
  The root of a tree bin is normally its first node. However,
  sometimes (currently only upon Iterator.remove), the root might
  be elsewhere, but can be recovered following parent links
  * (method TreeNode.root()).

大意：如果 hashCode的分布离散良好的话，那么红黑树是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，注释中给我们展示了1-8长度的具体命中概率，当长度为8的时候，概率概率仅为0.00000006，超过8是小于千万分之一的概率，这么小的概率，HashMap的红黑树转换几乎不会发生。
Hash碰撞超过8次概率小于千万分之一，希望没有人在HashMap里存一千万个数据。

解除树化阈值为什么是6？

如果没有解除树化阈值，只用8来树化和解除，那么8将成为一个临界值，时而树化，时而退化。
这非常的影响影响性能，所以需要一个退化为链表的阈值。
如果是7的话，就差了1，仍然会相互转化，并不会好多少。
那么将7作为一个分水岭，大于7进化，小于7退化是一个不错的选择。
考虑到内存和为了避免相互转化，解除树化的阈值最大为6。

最小树化容量为什么是64？

这是因为容量低于64时，哈希碰撞的机率比较大，而这个时候出现长链表的可能性会稍微大一些，这种原因下产生的长链表，我们应该优先选择扩容而避免不必要的树化。

TreeNode

TreeNode的继承关系是HashMap.TreeNode -> LinkedHashMap.Entry -> HashMap.Node，
好家伙，子类的内部类继承了父类的内部类，父类的另一个内部类又继承了子类的内部类，搁这鸡生蛋蛋生鸡呢。
源代码如下：

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
    // 省略其他代码......
}
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable{
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;
        boolean red;
         // 省略其他代码......
    }
}

TreeNode为啥不直接继承Node？

细心的同学有个问题，TreeNode为啥不直接继承Node，而是要继承LinkedHashMap.Entry这个中间类呢？
而且LinkedHashMap.Entry的两个字段before, after也没有在HashMap里面用到。

答案来了：确实，LinkedHashMap.Entry确实对于HashMap没有一丢丢的作用，他的作用是为LinkedHashMap设计的。
回顾一下继承关系：HashMap.TreeNode -> LinkedHashMap.Entry -> HashMap.Node。
LinkedHashMap是一个节点有顺序的HashMap，LinkedHashMap.Entry作为它的键值对结构，同时他和HashMap的结构要求是一样的，也是数组 + 链表 / 树，只不过节点可以按顺序访问。他的键值对LinkedHashMap.Entry首先继承了HashMap.Node，直接就有了链表的功能，然后利用了HashMap.TreeNode继承LinkedHashMap.Entry，所以他的Entry节点也是可以表现为树的形式。
如果TreeNode继承于Node，Entry也继承Node，LinkedHashMap的树节点形式无法体现，为了复用HashMap的代码，所以TreeNode继承于Entry。
如果TreeNode继承于Node，Entry继承TreeNode呢？那确实可以这么做，但是有丢丢浪费，Entry是用不到parent，left，right，prev这种字段的。
所以呢这种代码复用对LinkedHashMap是很友好的，LinkedHashMap把HashMap复用到了极致，
对于HashMap而言呢，它的TreeNode节点浪费了before, after这两个字段，不过在hashcode方法实现均匀的情况下，HashMap极少会出现TreeNode节点。

构造过程

看一下HashMap的构造函数，选择这个参数最全的。

    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;
        // 根据initialCapacity计算初始的扩容阈值
        this.threshold = tableSizeFor(initialCapacity);
    }

需要注意的是这里计算的扩容阈值只是一个初始的赋值，没有乘以负载因子，因为table数组还没有进行初始化，当table数组进行初始化之后threshold才会乘上以负载因子。

tableSizeFor方法解析

计算初始的扩容阈值调用了tableSizeFor方法，以下是源码：

/**
* Returns a power of two size for the given target capacity.
*/
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;
    }

从注释我们看出，tableSizeFor方法是计算比目标数字的大的第一个2次幂，
比如传5，就返回8，传13就返回16，有一个问题是如果传的参数本身就是2次幂，那他会返回什么？
这个问题的答案是会返回它本身，比如传4就返回4，传8就返回8。
下面我们分析一下这几行代码。

1. int n = cap - 1；

好家伙，上来先减个1，这里为什么要减1呢，因为如果在参数本身就是2次幂的情况下，先进行减1，
然后再求大于这个数的第一个2次幂，这样不用做额外的判断，提高了效率。

1. n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16;

假设n为二进制0b01XXXXXX(6个X)，右移1位n >>> 1为0b001XXXXX(5个X)，再进行或运算为0b011XXXXX(5个X)，这时候表达式的开头变成了两个1，那么下次再右移2位进行或运算，11后面的两位也会变成1，n |= n >>> 2就会变为0b01111XXX，如果假设二进制表达式低位没有了0，全都是1，那么后面进行右移再或运算也不会改变结果。如果低位依然有0，那么继续这个操作，直到int的32位都进行了或运算。
那么最后的结果是，这个二进制表达式中低位的0全部被替换成了1，就是这个二进制目前的位数能够表达的最大值，比如15是二进制4位能表达的最大值，表达式是0b1111，它如果再+1，将会发生进位并产生连锁反应，后面所有的1都会变成0，0b1111 + 1 = 0b10000（16）。
我们知道二进制第一位是1后面全是0这种形式，它就是2的幂。

1. return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

如果结果小于0的话就返回1，大于0的话先判断是否超过最大容量，如果超过了就返回最大容量，不超过返回n + 1,n + 1是因为第二步返回了二进制当前位数的最大值，用n + 1进行进位操作，返回的值就是大于这个数字最接近的2次幂。

添加元素的过程（put函数）

下面是添加一个元素的过程：

public V put(K key, V value) {
    // 根据key计算hash值传入，key ，value，不改变现有值，创建模式
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 如果table未初始化，先进行初始化，初始化也是调用扩容函数
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果hash位置节点p为null， 直接创建节点
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 新建一个Node节点
            tab[i] = newNode(hash, key, value, null);
        else {
            // p不为null的情况，有三种情况：要找的节点为首节点p，p是树节点，p是链表节点。
            Node<K,V> e; K k;
            // 1.要找的节点和p的hash值相等且key值相同，把节点p赋值给e
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 2. 如果p是树节点，用红黑树的方法进行put
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 3.如果p是链表节点
            else {
                for (int binCount = 0; ; ++binCount) {
                    // 把下一个节点赋值给e，如果下一个节点为空，说明已经遍历到了末尾
                    if ((e = p.next) == null) {
                        // 如果没有找到元素的话，是在末尾进行添加。
                        p.next = newNode(hash, key, value, null);
                        // 如果binCount > 8 转换成红黑树，< 64 resize的操作在treeifyBin里面进行
                        // TREEIFY_THRESHOLD -1 是因为binCount从0开始遍历，
                        // 再加上当前新添加的节点, 最终判断是binCount > TREEIFY_THRESHOLD
                        // 也就是链表已有8个节点，当前put第9个节点时进行树化
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 树化或者扩容
                            treeifyBin(tab, hash);
                        // 已经遍历到尾部了，跳出循环
                        break;
                    }
                    // 如果节点hash值相等且key值相同,跳出循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 没有找到元素，继续遍历，p = p.next
                    p = e;
                }
            }
            // 找到了对应的元素，进行添加
            if (e != null) { // existing mapping for key
                // 取旧的值
                V oldValue = e.value;
                // onlyIfAbsent为false或者值本身不存在才进行赋值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 回调函数，用于linkedhashmap
                afterNodeAccess(e);
                // 返回旧值
                return oldValue;
            }
        }
        // 修改次数+1
        ++modCount;
        // 容量+1，判断是否超过容量阈值，进行resize扩容操作
        if (++size > threshold)
            resize();
        // 回调函数，用于linkedhashmap
        afterNodeInsertion(evict);
        return null;
    }
//    将key的hashCode重新计算一个hash值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}
// Create a tree bin node
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
    return new TreeNode<>(hash, key, value, next);
}

保证hash的散列随机性

hash & (n -1)保证了最终计算的下标下落在table下标0到n-1范围内，
那么还有一个问题，就是怎么保证他的散列随机性？
虽然你是在0到n-1范围内，但是如果你每次都结果一样，那样都hash冲突了，会退化成链表。
所以呢这个就要求我们的计算hashCode呢这个算法要随机。
除此之外呢，还有一个点，因为hash表大小通常在2的16次方内，对应下标0到65535，16位
而我们的hashCode呢是int值，4个字节，32位。
那么我们进行hash & (n -1)时，假设你n的大小基本只有16位以下的话，
那么这个&操作大部分计算时都是丢弃了高位的16位，保留了低的16位，
为了把高位的16位也一起用上，hashCode转换为hash值的代码如下：

    static final int hash(Object key) {
        int h;
        // 保留高16位，高16位和低16位进行异或的结果作为低16位，增加散列均匀性
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

保留高16位，低16位变成高16位和低16位的异或结果，增加了随机性。

根据key查找value的过程（get函数）

public V get(Object key) {
    Node<K,V> e;
    // 元素为null返回null，不为null返回value
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // table不为null，且hash的节点不为null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 检查查找的节点是不是首节点，需要hash值相等且key值也相同
        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<K,V>)first).getTreeNode(hash, key);
            do {
                // 是链表，进行循环比对key值，需要hash值相等且key值也相同
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

移除元素的过程 （remove函数）

下面是HashMap移除一个元素的过程：

public V remove(Object key) {
    Node<K,V> e;
    // 返回移除元素的value，元素不存在时返回null
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
/**
*
* @param hash hash for 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
* @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) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 判断table不是null且容量大于0
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // hash值目标位置不为null，赋值给Node p
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 判断首节点p是否跟要查找的hash值相等且key相同
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 把首节点p赋值给node
            node = p;
        // 有子节点存在，结构可能是树或者链表
        else if ((e = p.next) != null) {
            // 首节点是树节点，调用getTreeNode获取Node，之后赋值给node
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 循环查找链表
                do {
                    // 判断e和p节点hash值相等且key相同，e赋值给node
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    // 遍历e的同时，把e赋值给p,如果node最后存在，p最终为node的上一个节点
                    // 如果node不存在，p为链表的末尾节点
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 最终查找到的节点node不为null，并且matchValue为false，或者value值相等
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 是树节点，可能会移动节点的位置
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // node = p的情况，node是首节点，将首节点tab[index]指向node.next
            else if (node == p)
                tab[index] = node.next;
            // 在链表中的子节点，p是node的上一个节点，将p.next指向node.next，跳过了node节点
            else
                p.next = node.next;
            // 修改次数+1
            ++modCount;
            // 大小-1
            --size;
            // 钩子函数，为linkedhashmap打造
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

扩容的过程（resize函数）

扩容是HashMap里面重要的机制，下面是扩容的源码：

/**
 * 扩容为表大小的两倍，如果表没有初始化，则扩容为初始容量，
 * 另外，使用的是二次幂扩容，扩容后bin的索引和原来相同，或者偏移2次幂。
 *
*/
final Node<K,V>[] resize() {
    // 把旧表table赋值给oldTab
    Node<K,V>[] oldTab = table;
    // 获取oldTab的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 获取旧的扩容阈值threshold赋值给oldThr
    int oldThr = threshold;
    // 初始化新的容量和阈值为0
    int newCap, newThr = 0;
    // 如果旧表容量>0
    if (oldCap > 0) 
       {
        // 旧表大于等于容量2^30，这里应该只会走到等于，不可能超过
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 把阈值改为int的最大值，2^31-1
            // 这时阈值超过了最大容量2^30，后面table将永远不会进行resize
            threshold = Integer.MAX_VALUE;
            // 不能再扩容了，直接返回旧表
            return oldTab;
        }
        // 新容量赋值为旧容量的2倍并且小于最大容量 且 旧容量 >= 16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 默认新的阈值是旧阈值的2倍
            // 如果newCap刚好等于MAXIMUM_CAPACITY，
            // 那么新阈值不是原来的2倍，而是Integer.MAX_VALUE
            // 如果oldCap小于16，新阈值是newCap * loadFactor
            newThr = oldThr << 1; // double threshold
    }
    // 注意这里是else if, 旧表容量 = 0 且旧表阈值 > 0, 新表容量设置为旧表阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 表未初始化，容量设置为初始的阈值
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 这里说明旧表阈值为0，容量也是0，设置新表容量默认值16
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 设置默认容量的阈值
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 新表阈值还没赋值，说明上面的判断都没走进去
    // 当旧表容量 < 16；或者容量刚好是最大值的一半时；
    // 或者旧表容量 = 0 且旧表阈值大于0，也就是初始化的时候
    if (newThr == 0) {
        // 根据容量和负载因子计算阈值
        float ft = (float)newCap * loadFactor;
        // 容量和阈值都小于最大容量时才赋值为ft，否则直接为Integer.MAX_VALUE
        // 如果是newCap刚好为MAXIMUM_CAPACITY，那么阈值是Integer.MAX_VALUE
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 把新的阈值设置到当前table
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 根据新的容量创建新的table
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 把newTab赋值给当前table
    table = newTab;
    // 旧table不为空，进行元素转移
    if (oldTab != null) {
        // for遍历旧表
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 索引位置不为null，同时将该Node赋值给e
            if ((e = oldTab[j]) != null) {
                // 将索引位置为null
                oldTab[j] = null;
                // 如果e没有后继节点，直接重新根据hash&n-1得到新下标
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 有后继节点且是树节点
                else if (e instanceof TreeNode)
                    // 是红黑树，调用红黑树的拆解方法
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 新的位置有两种可能：原位置，原位置+老数组长度 
                    // 把原链表拆成两个链表，然后再分别插入到新数组的两个位置上
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        // 遍历老链表，判断新增判定位是不是0进行分类
                        next = e.next;
                        // (e.hash & oldCap) == 0，新位置不变,记为低位区链表 lo开头-low
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // (e.hash & oldCap) != 0，新位置为原来位置+数组长度，
                        // 记为高位区链表 hi开头-high
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 两个链表分别赋值给新的table
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // 返回新的table
    return newTab;
}

这里我们看到旧链表的节点会根据(e.hash & oldCap) == 0 进行分类，
(e.hash & oldCap) == 0时，新下标与原下标相同。
(e.hash & oldCap) != 0时，新下标 = 原下标 + 旧表长度。
下面详细分析一下这个表达式。

e.hash & oldCap==0时，新下标 = 旧下标

设旧的下标为x，新的下标为y。证明当e.hash & oldCap == 0时，x = y。

在旧table中，计算下标的公式为 e.hash & (oldCap - 1) = x ，由于 oldCap = 2^n，可知 oldCap - 1 的二进制形式为 n 个 1。
e.hash & (oldCap - 1) 相当于取 e.hash 的低 n 位的值，该值为 x。

在新table中，容量上升为原来的2倍，所以他的公式为 e.hash & (2oldCap - 1) = y，由于 oldCap = 2^n，可知 2oldCap - 1 的二进制形式为 n + 1 个 1。
e.hash & (2oldCap - 1) 相当于取 e.hash 的低 n + 1 位的值，该值为 y。

2^n表示形式为第n + 1位是1，后面全0，当 e.hash & oldCap = e.hash & 2^n = 0 时，表示e.hash 的第 n + 1 位为 0，所以低 n 位的值与低 n +1 位的值是一样的，即 x = y。
例: 0 & 111 与 0 & 1111相等

e.hash & oldCap != 0 时，新下标 = 旧下标 + 旧数组长度

设旧的下标为x，新的下标为y。证明当e.hash & oldCap != 0时，y = x + oldCap。

e.hash & (oldCap - 1) = x ，oldCap = 2^n，x等于取e.hash低n位的值。
e.hash & (2oldCap - 1) = y ，oldCap = 2^n，y等于取e.hash低n+1位的值。
oldCap = 2^n，第 n + 1 位为 1，低 n 位全为 0。

当 e.hash & oldCap != 0 时，由于 oldCap = 2^n，说明 e.hash 的第 n + 1 位不是 0 ，而是 1。

当 e.hash 的第 n + 1 位为 1，且e.hash的低 n + 1 位的值为 y，低 n 位的值为 x，此时 y = x + oldCap。
例：1 = 1000 +

总结

1. 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
2. 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
3. HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。
4. JDK1.8引入红黑树大程度优化了HashMap的性能。