Java常用类源码——HashMap源码解析(JDK1.8)

Java中存在几大非常有名的集合大佬，例如HashMap， HashTable，TreeMap等等，各大集合大佬们各有特色，那么他们的内部是怎么实现的呢?是不是非常好奇呢？当然本人也是非常好奇的，那么我们就慢慢的一步一步的了解他们吧，下面我们就先来了解HashMap这个集合。

HashMap的基本概述

首先，我们来看Java中对于HashMap的一个说明:

* Hash table based implementation of the <tt>Map</tt> interface.  This
 * implementation provides all of the optional map operations, and permits
 * <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
 * unsynchronized and permits nulls.)  This class makes no guarantees as to
 * the order of the map; in particular, it does not guarantee that the order
 * will remain constant over time.

上面的这一段说明是说:Hash表是实现了 Map 接口的，实现了里面可选择的集合操作，其中允许了键和值为null的情况，HashMap除了不是线程安全和允许键和值可以为null的特殊性外，其他的和HashTable是非常现似的。当向集合中添加元素的时候，是不能保证集合中的元素是有序的，特别的是，它不能保证顺序是恒久不变的。

那么它的实现是怎么样的呢？接着往下看

HashMap的主要数据结构

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

从上面的源码我们知道HashMap 实现了Map，序列化，可复制的接口，继承了抽象的AbstraMap。
但是你们看

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

这个是不是比较有趣呢？HashMap不是再实现Map不是多余吗？ 但是在Stack Overflow 上解释到：

在语法层面继承接口Map是多余的，这么做仅仅是为了让阅读代码的人明确知道HashMap是属于Map体系的，起到了文档的作用

那么元素是怎么在HashMap中储存的呢？
我们从源码中可以找到以下的数据结构:
Node节点和存储数组

  /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
     //哈希值，用来定位数组索引位置。
        final int 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;
            //链表的下一个node
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
         //根据key和value计算hash值
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
//判断两个node元素是否是相同的，先判断是不是同一个对象，然后你比较key和value的值。
        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;
        }
    }
    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
     //存储（位桶）的数组
    transient Node<K,V>[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

从源码中可以知道，HashMap中有一个非常重要的字段（或者叫做 域），那个就是transient Node<K,V>[] table, 该字段是用于存储元素类型为Node的数组.
红黑树

/**
 * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
 * extends Node) so can be used as extension of either regular or
 * linked node.
 */
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    /**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }

    /**
     * Ensures that the given root is the first node of its bin.
     */
    static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
        int n;
        if (root != null && tab != null && (n = tab.length) > 0) {
            int index = (n - 1) & root.hash;
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
            if (root != first) {
                Node<K,V> rn;
                tab[index] = root;
                TreeNode<K,V> rp = root.prev;
                if ((rn = root.next) != null)
                    ((TreeNode<K,V>)rn).prev = rp;
                if (rp != null)
                    rp.next = rn;
                if (first != null)
                    first.prev = root;
                root.next = first;
                root.prev = null;
            }
            assert checkInvariants(root);
        }
    }
    .....

JDK1.8版本对以前的HashMap进行了很大的修改，在JDK1.6中，HashMap采用桶+链表的实现，即：使用链表处理冲突，同时同一hash值的链表（Node）都存储在一个链表中，因此当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低，但是在JDK1.8中，HashMap采用桶+链表+红黑树实现，当链表长度超过阙值 8（为什么是8呢？后面会讲到HashMap中的重要属性）的时候，将转化为红黑树，而红黑树的查找和插入的效率都是非常高的，这样大大的减少了查找的时间。

看了上面的图了之后，记住哦！当链表的长度大于8的时候，将会将链表转换为红黑树。

/**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
     //阙值：当数组中的元素大于8的时候，将数组中结构转化为树的结构。
    static final int TREEIFY_THRESHOLD = 8;

从上面的三个数据结构可以知道，Node元素实现了Map.Entry,而Map.Entry(K,V)就是定义了Entry的接口，定义了getKey(), getValue(), setValue(), equals()等一些抽象方法。HashMap的内部类Node实现这个接口。从源码中可以看到Node是里面存储的是链表。
有了以上桶+链表+红黑树，那么大致就是HashMap的实现了，首先HaspMap内部是有一个数组(也可以说是一个桶,桶排序算法也用的是这样的桶)，里面的元素都是Node元素的链表。

构造函数

//构建一个带指定初始容量和加载因子的空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;
        this.threshold = tableSizeFor(initialCapacity);
    }
    
//构造一个带初始容量和加载因子默认的空HashMap
 public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
 /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    //构造一个具有初始容量(16)和默认加载因子(0.75)的空HashMap
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
 
 //构造一个映射关系与指定Map相同的新HashMap,容量于指定Map容量相同，加载因子默认为0.75
 public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
    /**
     * Returns a power of two size for the given target capacity.
     */
    //找出“大于Capacity”的最小的2的幂，使得HashMap表的容量保持为2的次方倍
    //算法思想：通过使用逻辑运算来替代取余，这里有一个规律，就是当N为2的次方(Power of  two 那么X%N==X&(N-1))。
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;// >>> 无符号右移，高位补0
        n |= n >>> 2;// a|=的意思是把a和b位按位或 然后赋值给a
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

主要的属性

HashMap中的主要属性是一定要认识一下的，因为HasMap的一些特点很多是与属性有关的。

private static final long serialVersionUID = 362498820763181265L;
//初始容量的大小， 必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//顾名思义：集合的最大容量，必须是2的幂且小于2的30次方，传入的值如果过大的话，将会被这个值替换
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充比
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
//当数组中的一个位置上的链表的长度达到8的时候，将会将链表转化为红黑树
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
/**
 * The number of key-value mappings contained in this map.
 */
 //集合中的元素个数
transient int size;
 /**
 * The number of times this HashMap has been structurally modified
 * Structural modifications are those that change the number of mappings in
 * the HashMap or otherwise modify its internal structure (e.g.,
 * rehash).  This field is used to make iterators on Collection-views of
 * the HashMap fail-fast.  (See ConcurrentModificationException).
 */
 //map结构被修改的次数
transient int modCount;

/**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial
 */
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
//临界值，当实际大小(容量*填充比)超过临界值时，会进行扩容。
int threshold;
/**
 * The load factor for the hash table.
 *
 * @serial
 */
 //填充比
final float loadFactor;

HashMap中的成员属性不得不说的得是填充比了， 它的默认值是0.75 ，如果实际元素所占容量占分配容量的75%时，就要扩容了，如果填充比很大，说明空间的利用率非常的大，但是此时的查找效率是会很低的，因为链表的长度很大，但是JDK1.8之后的使用了红黑树会效率会更高一些，HashMap本来是以空间换时间，所以填充比没有必要太大，但是填充比太小会导致空间的浪费，如果关注内存，那么填充比可以稍大，如果关注的是查找性能，填充比可以稍小。

元素的存放位置put/get方法

我们向HashMap中添加元素的时候是通过put(K，V)方法，取得元素的方法一般是get(),那么这两个方法是怎么实现的呢？

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) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //此处分两种情况:1.当tabel为null时，用默认容量16初始化tabel数组，2.当table非空的时候
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//初始化hashMap的长度为16
    //此处又分为两种情况，1.key的hashMap值对应的那个节点为空时，2.key的hash值对应的那个节点不为空。
    if ((p = tab[i = (n - 1) & hash]) == null)//此种情况是 该key的hash值对应的那个节点为空，即表示还没有元素被散列到这个位置
        //那么就创建一个新的Node元素
        tab[i] = newNode(hash, key, value, null);
    else {
    //该key的hash值对应的那个节点不为空，与链表上的第一个节点p比较
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            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;
            }
        }
        //如果key对应的value已经存在了，则用新的value取代旧的value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //如果加入该键值对后超过最大阙值，则进行resize操作。
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
// put()方法中，使用的hash方法进行对key计算哈希值，从这里可以知道，如果传入的key值为null的时候，哈希值是0， 否则的话是通过key值的hashCode()方法取得值，然后做一次16位位移异或混合进行位运算 
 static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。理论上散列值是一个int型，如果直接拿散列值作为下标访问HashMap主数组的话，考虑到2进制32位带符号的int表值范围从-2147483648到2147483648。前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。你想，HashMap扩容之前的数组初始大小才16。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组下标。源码中模运算是在这个indexFor( )函数里完成的。

bucketIndex = indexFor(hash, table.length);

indexFor的代码也很简单，就是把散列值和数组长度做一个”与”操作.

static int indexFor(int h, int length){
    return h & (length-1);

顺便说一下，这也正好解释了为什么HashMap的数组长度要取2的整次幂。因为这样（数组长度-1）正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值,用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值

     10100101 11000100 00100101
&    00000000 00000000 00001111
---------------------------------
     00000000 00000000 00000101 //高位全部归0，只保留末四位

但这时候问题就来了，这样就算我的散列值分布再松散，要是只取最后几位的话,碰撞也会很严重。更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，恰好使最后几个低位呈现规律性重复，就无比蛋疼。这时候“扰动函数”的价值就体现出来了，说到这里大家应该猜出来了。看下面这个图，

位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性.而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
最后我们来看一下Peter Lawley的一篇专栏文章《An introduction to optimising a hashing strategy》里的一个实验:他随机选取了352个字符串，在他们散列值完全没有冲突的前提下，对它们做低位掩码，取数组下标。

结果显示，当HashMap数组长度为512的时候，也就是用掩码取低9位的时候，在没有扰动函数的情况下，发生103次碰撞，接近30%,而在使用了扰动函数之后只有92次碰撞。碰撞减少了将近10%，看来扰动函数确实是有功效的。

HashMap中查找元素方法的办法有多种，有get(Object key), containsKey(Object key), containsValue(Object value)这些查找键值对的方法:

//返回指定key所映射的value；如果对于该键来说，次映射不包含任何的映射，则返回null
 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
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // key的哈希值作为数组的下表
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {           
            //检查第一个节点
            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 {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
    //如果此映射包含对于指定将的映射关系，则返回true
     public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }
    
    //如果此映射将一个或多个键映射到指定值，则返回true
      public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
            //外层循环搜索数组
            for (int i = 0; i < tab.length; ++i) {
                //内层循环搜索链表
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }

HashMap的扩容机制

在HsahMap的四种构造函数中并没有对其中的成员变量Node< K,V > [] table 进行任何初始化的工作，从上面对hashMap中的主要的属性的分析知道，构造HashMap表的时候，如果不指定表的数组大小的情况下，默认大小是16,那么HashMap是如何构造一个默认的初始容量为16的空表的呢？如果Node数组中的元素达到 填充比*Node.length 的时候，HsahMap将会扩容。那么它是怎么扩容的呢？

我们直接上源码吧！

/**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
     // 功能1. 初始化hashMap里的容量大小。功能2.对hashMap中的容量进行扩容,翻倍
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;//旧的hashMap
        // 先根据数组对象是否进行了初始化,得到旧HashMap的初始的容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;//旧的HashMap的阙值
        int newCap, newThr = 0;//新的HashMap容量，与扩容临界值
        if (oldCap > 0) {
        //如果容量大小超过最大容量大小，则不在进行调整，只能改变阙值了。
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //新的容量大小为旧的2倍，最小的为16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //扩容阙值加倍
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // oldCap = 0, oldThr = 0 相当于使用默认填充比和初始容量来进行初始化
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            //创建一个新的数组长度为newCap大小，然后将原来的数组中的元素拷贝到新的数组中。
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        
        table = newTab;
    //如果旧的HashMap表非空，则按序将旧HashMap中的元素重定向到新HashMap表中
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;//e按序指向oldTab数组中的元素，及每个链表中的头结点
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    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
                    //对链表进行秩序的维护，因为对HashMap表是进行过两倍的扩容，所以每个桶里面的元素必须要么是待在原来的索引所对应该位置，要么是在新的桶中位置偏移两倍。
                    
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

通过阅读和解释上面的源码可以知道:
该初始化的诱发条件是在向HashMap中添加第一个元素时，通过put< K key, V value >——>putVal(hash(key), key, value, false, true)——> resize()方法，一步一步的将元素添加到hashMap中。HashMap中尤其重要的resize()方法主要实现的了两个功能：
1、在table为数组为null的时候，对其进行初始化，默认容量是16；
2、当table数组为非空，但是需要调整HashMap容量的时候，将HsahMap容量翻倍。
该方法的解释是: 这个方法可以用来初始化HashMap的大小，或者重新调整HashMap的大小，变为原来的2倍。 在从旧的数组中拷贝元素到新的数组中的时候，是一个一个的遍历数组，元素的同时遍历链表(或者红黑树)，所以这个过程是相当的耗时间的。

清空有删除

HashMap中提供了remove(Object key)方法来删除键值对，使用clear()清除所有的键值对的方法，这方法使用的时候需要比较小心。

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
   * @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
   */
   //该方法是remove()方法的内部实现方法。
  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数非空，键的hash值所指向的数组中的元素非空
      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指向最终的结果节点，e为链表中的遍历指针
          if (p.hash == hash &&
              ((k = p.key) == key || (key != null && key.equals(k))))//检查第一个节点，如果匹配成功
              node = p;
          //如果第一个节点匹配不成功，则向后遍历链表查找
          else if ((e = p.next) != null) {
              if (p instanceof TreeNode)
                  node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
              else {
                  do {
                      if (e.hash == hash &&
                          ((k = e.key) == key ||
                           (key != null && key.equals(k)))) {
                          node = e;
                          break;
                      }
                      p = e;
                  } while ((e = e.next) != null);
              }
          }
          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);
              else if (node == p)//删除node节点
                  tab[index] = node.next;
              else
                  p.next = node.next;
              ++modCount;
              --size;
              afterNodeRemoval(node);
              return node;
          }
      }
      return null;
  }

/**
   * Removes all of the mappings from this map.
   * The map will be empty after this call returns.
   */
   //从映射中移出所有映射关系
  public void clear() {
      Node<K,V>[] tab;
      modCount++;
      if ((tab = table) != null && size > 0) {
          size = 0;
          for (int i = 0; i < tab.length; ++i)
              tab[i] = null;//直接将数组中的值赋值为null
      }
  }

其他方法:size(),isEmpty(),clone()

//返回HasMap中的大小 
public int size() {
     return size;
 }

 //判断hashMap是否为空
 public boolean isEmpty() {
     return size == 0;
 }
 
   /**
  * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
  * values themselves are not cloned.
  *
  * @return a shallow copy of this map
  */
  //HashMap复制。
 @SuppressWarnings("unchecked")
 @Override
 public Object clone() {
     HashMap<K,V> result;
     try {
         result = (HashMap<K,V>)super.clone();//调用父类的clone方法
     } catch (CloneNotSupportedException e) {
         // this shouldn't happen, since we are Cloneable
         throw new InternalError(e);
     }
     result.reinitialize();
     //将HashMap 元素放入到result中。
     result.putMapEntries(this, false);
     return result;
 }

HashMap序列化

保存Node的table数组为transient的，也就是说在进行序列化时，并不会包含该成员，这是为什么呢？

transient Node<K,V>[] table;

为了解答这个问题，我们需要明确下面事实：

• Object.hashCode方法对于一个类的两个实例返回的是不同的哈希值

我们可以试着想下一下下面的场景

我们在机器A上算出对象A的哈希值与索引，然后把它插入到HashMap中，然后把该HashMap序列化后，在机器B上重新算对象的哈希值与索引，这与机器A上算出的是不一样的，所以我们在机器B上get对象A时，会得到错误的结果。
所以说，当序列化一个HashMap对象时，保存Entry的table是不需要序列化进来的，因为它在另一台机器上是错误的。

因为这个原因，HashMap重现了writeObject与readObject 方法

  /**
     * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
     * serialize it).
     *
     * @serialData The <i>capacity</i> of the HashMap (the length of the
     *             bucket array) is emitted (int), followed by the
     *             <i>size</i> (an int, the number of key-value
     *             mappings), followed by the key (Object) and value (Object)
     *             for each key-value mapping.  The key-value mappings are
     *             emitted in no particular order.
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws IOException {
        int buckets = capacity();
        // Write out the threshold, loadfactor, and any hidden stuff
        s.defaultWriteObject();
        s.writeInt(buckets);
        s.writeInt(size);
        internalWriteEntries(s);
    }

private void readObject(java.io.ObjectInputStream s)
        throws IOException, ClassNotFoundException {
        // Read in the threshold (ignored), loadfactor, and any hidden stuff
        s.defaultReadObject();
        reinitialize();
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        s.readInt();                // Read and ignore number of buckets
        int mappings = s.readInt(); // Read number of mappings (size)
        if (mappings < 0)
            throw new InvalidObjectException("Illegal mappings count: " +
                                             mappings);
        else if (mappings > 0) { // (if zero, use defaults)
            // Size the table using given load factor only if within
            // range of 0.25...4.0
            float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
            float fc = (float)mappings / lf + 1.0f;
            int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
                       DEFAULT_INITIAL_CAPACITY :
                       (fc >= MAXIMUM_CAPACITY) ?
                       MAXIMUM_CAPACITY :
                       tableSizeFor((int)fc));
            float ft = (float)cap * lf;
            threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
                         (int)ft : Integer.MAX_VALUE);
            @SuppressWarnings({"rawtypes","unchecked"})
                Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
            table = tab;

            // Read the keys and values, and put the mappings in the HashMap
            for (int i = 0; i < mappings; i++) {
                @SuppressWarnings("unchecked")
                    K key = (K) s.readObject();
                @SuppressWarnings("unchecked")
                    V value = (V) s.readObject();
                putVal(hash(key), key, value, false, false);
            }
        }
    }

简单来说，在序列化时，针对Entry的key与value分别单独序列化，当反序列化时，再单独处理即可。

小结

HashMap的一些特点

• 线程非安全，并且允许key与value都为null值，HashTable与之相反，为线程安全，key与value都不允许null值。

• 不保证其内部元素的顺序，而且随着时间的推移，同一元素的位置也可能改变（resize的情况）

• put、get操作的时间复杂度为O(1)。

• 遍历其集合视角的时间复杂度与其容量（capacity，槽的个数）和现有元素的大小（entry的个数）成正比，所以如果遍历的性能要求很高，不要把capactiy设置的过高或把平衡因子（load factor，当entry数大于capacity*loadFactor时，会进行resize，reside会导致key进行rehash）设置的过低。

• 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。

• 由于HashMap是线程非安全的，这也就是意味着如果多个线程同时对一hashmap的集合试图做迭代时有结构的上改变（添加、删除entry，只改变entry的value的值不算结构改变），那么会报ConcurrentModificationException，专业术语叫fail-fast，尽早报错对于多线程程序来说是很有必要的。

• Map m = Collections.synchronizedMap(new HashMap(…)); 通过这种方式可以得到一个线程安全的map。

• 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。

• JDK1.8引入红黑树大程度优化了HashMap的性能。