一.HashMap介绍

1.哈希表（hash table）

• 在哈希表中进行添加，删除，查找等操作,时间复杂度为O(1)

• 存储位置 = f(关键字)

  其中，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣

  将key通过哈希算法计算出哈希值，把哈希值作为数组下标

  通过该方法建立的数组就叫做哈希表

  

• 哈希冲突

  当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。

  • 解决方案：

    • 开放定址法

      开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
      其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。

    • 再散列函数法

      当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。

    • 链地址法（拉链法）

      将所有关键字为同义词的记录存储在同一线性链表中

2.HashMap实现原理

2.1 Map

• HashMap是Map的主要实现类，线程不安全的，效率高；可以存储null的key和value
• Map就是用于存储键值对（<key,value>）的集合类，也可以说是一组键值对的映射（数学概念），在java中map是一个接口，是和collection接口同一等级的集合根接口。
• Map特点：
  • key键值不可以重复
  • 每个key只能对应一个value，多个key可以对应一个value
  • key,value 都可以是任何引用类型（包括 null）的数据（只能是引用类型）

2.2 HashMap

• HashMap是用数组 + 单链表 + 红黑树实现的map类。

• 

• HashMap 的实现不是同步的，这意味着它不是线程安全的。

• 扩容机制和哈希函数越合理，空间成本越小，哈希函数计算结果越分散均匀。越分散发生哈希冲突的几率就越小

3.红黑树

、、、、、、、、

二.源码部分

1.基本属性

AbstractMap<K, V> :AbstractMap 提供了 Map 的基本实现，使得我们以后要实现一个 Map 不用从头开始，只需要继承 AbstractMap, 然后按需求实现/重写对应方法即可。

Map是Java集合框架的根接口，另一个是Collection接口

Cloneable接口是一个标记接口,也就是没有任何内容

Serializable 接口之所以定义为空，是因为它只起到了一个标识的作用，告诉程序实现了它的对象是可以被序列化的，但真正序列化和反序列化的操作并不需要它来完成。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    private static final long serialVersionUID = 362498820763181265L;
/**
 * The default initial capacity - MUST be a power of two.
 * 默认的初始容量--必须是2的幂
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 * 哈希表的最大容量为2^30
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The load factor used when none specified in constructor.
 * 在构造函数中未指定时使用的负载系数,负载因子默认为0.75f
 * 当元素的总个数>当前数组的长度 * 负载因子。数组会进行扩容，扩容为原来的两倍
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 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;

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 * 当红黑树结点小于6时重新转化为链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * The smallest table capacity for which bins may be treeified.
 * 可以树形化容器的最小表容量。
 * (Otherwise the table is resized if too many nodes in a bin.)
 * 否则，如果容器中的节点太多，则会调整表的大小
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 * 当Table所有元素超过该值，才会进行树化（为了防止前期阶段频繁扩容和树化过程冲突）
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/* ---------------- Fields -------------- */

/**
 * 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.)
 * node数组
 */
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;

/**
 * The number of key-value mappings contained in this map.
 *键-值映射的数量
 */
transient int size;

/**
 * The number of times this HashMap has been structurally modified
 * 这个HashMap被结构修改的次数
 * Structural modifications are those that change the number of mappings in
 * the HashMap or otherwise modify its internal structure
 * 结构修改是HashMap中那些改变映射数量的修改或修改其内部结构
 * (e.g.,
 * rehash).  This field is used to make iterators on Collection-views of
 * the HashMap fail-fast.  (See ConcurrentModificationException).
 */
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;

2.结构

• 如2.2中的图，顶层为动态数组，每个元素为一个node
  而每个node又是一个链表的头节点
  node的next指向下个hash值相同的结点

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     * node内部类，node
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        //当前的hash值
        final int hash;
        //键值
        final K key;
        //数据值
        V value;
        //指向node
        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;
        }
        //返回node键值的get方法
        public final K getKey()        { return key; }
        //返回node数据的get方法
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        //value的set方法
        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;
        }
    }

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);
    }

3.构造函数

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *构造一个手动设置初始容量和负载因子的空hashmap
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public HashMap(int initialCapacity, float loadFactor) {
    //如果设置的初始容量小于0，抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //如果手动设置的初始容量大于最大容量，则设置为最大容量，即2^30 = 1,073,741,824
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //如若设置的负载因子<=0 或者
    //NaN全称是Not a Number，意思是“不是一个数字”，代表一种不合法，即float值和double值不合法。
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    //将负载因子赋值
    this.loadFactor = loadFactor;
    //将初始容量的2次幂值赋给边界值
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *使用指定的初始容量构造一个空的HashMap
 * 负载因子为默认的0.75
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
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
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
 * Constructs a new <tt>HashMap</tt> with the same mappings as the
 * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
 * default load factor (0.75) and an initial capacity sufficient to
 * hold the mappings in the specified <tt>Map</tt>.
 *根据传入的map，使用相同的映射构造一个新的HashMap
 * 负载因子为0.75
 * @param   m the map whose mappings are to be placed in this map
 * @throws  NullPointerException if the specified map is null
 */
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.
 * 返回给定目标容量的2次幂大小
 * 由于HashMap的capacity都是2的幂，因此这个方法用于找到大于等于initialCapacity的最小的2的幂（initialCapacity如果就是2的幂，则返回的还是这个数）。
 */
static final int tableSizeFor(int cap) {
    //cap-1是当进入的数本身为二次幂数而进行转换
    //让最高位的1后面的位全变为1,最后加1，就得到了2次幂大小
    //当32为都为1的时候，容量为MAXIMUM_CAPACITY
    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;
}

4.hashcode

• Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，这个数值称作为散列值。

• 由于和（length-1）运算，length 绝大多数情况小于2的16次方。所以始终是hashcode 的低16位（甚至更低）参与运算。要是高16位也参与运算，会让得到的下标更加散列。

•   static final int hash(Object key) {
        int h;
        //h >>> 16是用来取出h的高16，(>>>是无符号右移)
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
  

5.get方法

public V get(Object key) {
    Node<K,V> e;
    //找不到键映射的值，返回null，否则返回value
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
 * Implements Map.get and related methods
 *get操作是通过调用getNode方法
 * @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;
    //在table不为空的情况下
    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;
        //以下为first node不是目标结点的情况
        if ((e = first.next) != null) {
            //判断是否为红黑树对象
            //instanceof是Java中的二元运算符，左边是对象，右边是类；当对象是右边类或子类所创建对象时，返回true；否则，返回false。
            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);
        }
    }
    //没找到，返回null
    return null;
}

instanceof是Java中的二元运算符，左边是对象，右边是类；当对象是右边类或子类所创建对象时，返回true；否则，返回false。

6.put方法

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 * 将键/值对添加到 hashMap 中
 * 如果先前的映射包含一个键的映射，则旧的value被替换。
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V put(K key, V value) {
    //false: onlyIfAbsent,表示改变现有值
    //true： 不处于创建模式
    return putVal(hash(key), key, value, false, true);
}

/**
 * Implements Map.put and related methods
 *实现了地图Map.put及相关方法
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 *        如果为true，则不更改现有值
 * @param evict if false, the table is in creation mode.
 *        如果为false，则表示表处于创建模式
 * @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;
    //如果table为空，则进行扩容操作
    if ((tab = table) == null || (n = tab.length) == 0)
        //n 为扩容后的长度
        n = (tab = resize()).length;
    //如果 tab[i]为空，则新建结点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //n = (tab = resize()).length
        //p目前指向tab[i = (n - 1) & hash]，也就是数组的最后一个元素
        //如果p的hash有相同的，且key ！= null，说明键值已经存在了
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //把p存储在e中
            e = p;
        //如果p结点为红黑树结点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //遍历链表
            for (int binCount = 0; ; ++binCount) {
                //如果p结点没有后继结点，则新建链表节点
                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 = p.next;
                p = e;
            }
        }
        //如果e不为空说明hashmap本来就存储了键值
        if (e != null) { // existing mapping for key
            //把原来的vlue保存起来
            V oldValue = e.value;
            //当相同可以修改的时候，进行重新赋值操作
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //继承HashMap的LinkedHashMap类服务的
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //在进行一次扩容判断
    if (++size > threshold)
        resize();
    //继承HashMap的LinkedHashMap类服务的
    afterNodeInsertion(evict);
    return null;
}

7.resize()方法

/**
 * 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
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    //旧容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //旧阈值
    int oldThr = threshold;
    int newCap, newThr = 0;
    //如果旧的容量大于0，则以2的幂次加倍table的容量
    if (oldCap > 0) {
        //如果容量已经为最大值时，将边界值也赋值成最大值，返回原来的table
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //newCap * 2 小于最大容量，且oldCap大于等于默认容量（已经初始化过的table），阈值 * 2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //oldCap <= 0,但是oldThr > 0，说明构造hashtable对象时，手动设置了容量
    else if (oldThr > 0) // initial capacity was placed in threshold 初始容量设置为threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults 零初始阈值表示使用默认值，16
        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"})
            //扩容后，新建数组保存旧数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //如果原数组不为空，则需要将新的数组都逐个拷贝到新的数组中
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //如果 j 结点不为空，则将其先保存在e中，并将原结点设置为null
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //如果该结点没有后继结点（树，链表），直接把这个结点放在新的数组中
                //根据当前节点的hash值与新数组容量减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 {
                        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) {
                        //再将最后的结点赋值为null
                        loTail.next = null;
                        //再将数组头节点赋给数组
                        newTab[j] = loHead;
                    }
                    //高位同样操作
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    //返回新的数组
    return newTab;
}

8.遍历方法

• 先遍历key，再取出value

  /**
   * Returns a {@link Set} view of the keys contained in this map.
   * The set is backed by the map, so changes to the map are
   * reflected in the set, and vice-versa.  If the map is modified
   * while an iteration over the set is in progress (except through
   * the iterator's own <tt>remove</tt> operation), the results of
   * the iteration are undefined.  The set supports element removal,
   * which removes the corresponding mapping from the map, via the
   * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
   * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
   * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
   * operations.
   *     返回 hashMap 中所有 key 组成的集合视图
   * @return a set view of the keys contained in this map
   */
  public Set<K> keySet() {
      Set<K> ks = keySet;
      if (ks == null) {
          ks = new KeySet();
          keySet = ks;
      }
      return ks;
  }
  

  然后通过get方法都得到value

• 直接遍历value

  /**
   * Returns a {@link Collection} view of the values contained in this map.
   * The collection is backed by the map, so changes to the map are
   * reflected in the collection, and vice-versa.  If the map is
   * modified while an iteration over the collection is in progress
   * (except through the iterator's own <tt>remove</tt> operation),
   * the results of the iteration are undefined.  The collection
   * supports element removal, which removes the corresponding
   * mapping from the map, via the <tt>Iterator.remove</tt>,
   * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
   * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
   * support the <tt>add</tt> or <tt>addAll</tt> operations.
   * 返回 hashMap 中存在的所有 value 值。
   * @return a view of the values contained in this map
   */
  public Collection<V> values() {
      Collection<V> vs = values;
      if (vs == null) {
          vs = new Values();
          values = vs;
      }
      return vs;
  }
  

• 通过遍历entry来取key和value

  /**
   * Returns a {@link Set} view of the mappings contained in this map.
   * The set is backed by the map, so changes to the map are
   * reflected in the set, and vice-versa.  If the map is modified
   * while an iteration over the set is in progress (except through
   * the iterator's own <tt>remove</tt> operation, or through the
   * <tt>setValue</tt> operation on a map entry returned by the
   * iterator) the results of the iteration are undefined.  The set
   * supports element removal, which removes the corresponding
   * mapping from the map, via the <tt>Iterator.remove</tt>,
   * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
   * <tt>clear</tt> operations.  It does not support the
   * <tt>add</tt> or <tt>addAll</tt> operations.
   * 返回键值对
   * @return a set view of the mappings contained in this map
   */
  public Set<Map.Entry<K,V>> entrySet() {
      Set<Map.Entry<K,V>> es;
      return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
  }
  

• 通过foreach方法直接遍历key和value

  //对 hashMap 中的每个映射执行指定的操作。
      @Override
      // BiConsumer是一个功能接口。 它接受两个参数，但不返回任何内容
      public void forEach(BiConsumer<? super K, ? super V> action) {
          Node<K,V>[] tab;
          //如果action为0，则抛出异常
          if (action == null)
              throw new NullPointerException();
          //如果size大于0， 并且将table 赋给tab
          if (size > 0 && (tab = table) != null) {
              int mc = modCount;
              //遍历哈希表
              for (int i = 0; i < tab.length; ++i) {
                  //遍历表上的链表节点或者树节点
                  for (Node<K,V> e = tab[i]; e != null; e = e.next)
                      action.accept(e.key, e.value);
              }
              if (modCount != mc)
                  throw new ConcurrentModificationException();
          }
      }
  

9.remove方法

/**
 * Removes the mapping for the specified key from this map if present.
 * 删除 hashMap 中指定键 key 的映射关系
 * @param  key key whose mapping is to be removed from the map
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V remove(Object key) {
    Node<K,V> e;
    //调用removeNode方法，若无则返回null，否则返回value
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

/**
 * Implements Map.remove and related methods
 * 实现了MAP移除及相关方法
 * @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
 *                   如果为true，只在value相等时移除
 * @param movable if false do not move other nodes while removing
 *                如果为false，则在移除时不要移动其他节点
 * @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;
    //同样的在复制的同时，做一个合法性检查
    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;
        //如果头节点就是目标结点，就将这个节点保存起来
        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 {
                    //判断key值相等，则为目标节点
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                    //直到结点遍历完
                } while ((e = e.next) != 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为头节点，则将其next变成头节点
            else if (node == p)
                tab[index] = node.next;
            else
                //这时p为e的前驱结点，就将node删除
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            //返回结点
            return node;
        }
    }
    return null;
}

三.总结

1. HashMap的初始长度为什么是16？每次自动扩展或是手动初始化时，长度为什么是2的幂？

   • HashMap的默认长度为16,15的二进制为1111，做与运算的时候，降低了hash碰撞的几率
   • 容量为2的整数幂是为了让（2^n）-1的二进制是全1 的，符合hash均匀分布的原则

2. 为什么要引入红黑树？

   为了提高查询效率，故在JDK１.8中引入了改进方法红黑树。此数据结构的平均查询效率为Ｏ(log n) 。

3. 什么是加载因子、负载因子、边界值？

   • 加载因子：用于表示哈希表中元素填满的程度。

     • 加载因子越大,填满的元素越多,好处是,空间利用率高了,但，冲突的机会加大了.反之,亦同。

     • 冲突的机会越大,则查找的成本越高.反之,查找的成本越小.因而,查找时间就越小.

     • 默认的加载因子： static final float DEFAULT_LOAD_FACTOR = 0.75f;

   • 负载因子：等同于加载因子，也叫扩容因子

   • 边界值： threshold

     • threshold = capacity * loadFactory

4. 怎么计算key值的存储位置？

   hash & (cap - 1)

   扩容时：e.hash & oldCap

5.