本次分析难度有点大了，我曾经以为还算是了解HashMap了，但是具体分析了源码和看了别人的文章，我才发现还是差太多了。本文估计会非常非常长，而且在JDK1.8以后HashMap增加了使用红黑树来储存，所以应该会用两篇文章来处理了HashMap

散列表

什么是散列表

官方定义：

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表，也有叫做字典的说法。

用通俗的话来说：

你可以理解为，你去菜市场买菜。你会发现菜市场的菜农们，好像都不用思考？基本上你只要问他，这个白菜多少钱，他都是秒答。你当然希望计算机也能这样，于是我们使用了一种方式来实现这个逻辑。使用散列函数+数组。我们知道访问数组，只要知道下标是很快的。那么我们只需要散列函数能对一个输入值输出某个特定数值，然后用这个数组当作索引在数组存放数据即可。

什么是散列函数

所以什么是散列函数呢？散列函数就是无论你给它一个值，都能返回一个数字。

• 它必须是一致的，假如你输入我，返回1。那么下次输入我，也要返回1
• 应该能将不同的数据返回成不同的数字，如果每次输入任何值都是返回1的话也没有任何意义。

散列表的优势

散列表的查询速度很快，最好的情况下，无论你查询多少数据量都是同样的查询时间也就是一个所谓的常量查询时间。插入速度也很快，我们直接根据索引存入数据。删除也是如此，我们直接根据改索引删除数据，不需要移动数组。所以勉强算是结合了数组和链表两方的优势。

冲突

上面说到是最好的情况下是如此，散列函数是能将不同的数据映射成不同的值，但事实上我们根本做不到这样的散列函数。假如我们使用首字母开头来匹配的散列函数（实际上不可能这么用），那么匹配吴和无都有可能会返回相同的序列号，给两个键分配的位置相同，这种情况称为冲突。

最简单的处理办法就是，如果两个键映射到了同一个位置，就在这个位置存储一个链表。

性能

但是如果采用这样的方法的话，问题就来了。假如吴和无都存储在同一位置，现在访问吴可能速度依然很快，但是访问无可能速度就会慢一些。不过如果一条链表上只有3-4个数据那么影响也不大。所以这里就要求我们需要使用优秀的散列函数（最理想的情况下，散列函数能将键均匀地映射到散列表地不同位置）

现在我们重新回顾查询，插入，删除的性能。假如我们采取了使用链表来处理冲突的方案，最优的情况下，一个位置只有一个键。那么我们无论插入，查询，删除的性能都最高，都很快。但是，假如在同一位置上的链表过于长，那么我们无论查询，插入，删除的性能都是最差的。这里的最差是和数组和链表做对比，数组是出了名的插入，删除慢，链表是查询数据慢

这里就要引入填装因子这个计算值：数列表/位置总数

举例：假如使用散列表存储数据，你总共需要存储5个数据，但是现在位置已经分配了2个。则散列表的填装因子为2/5，即0.4

填装因子越大，则发生冲突的概率就会增多，所以一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度。一个不错的经验规则就是：一旦填装因子大于0.7，就调整散列表的长度。

HashMap源码分析（链表部分）

总览

HashMap算是集合框架中比较难的一部分，因为它集成了数组，链表，红黑树等数据结构。实际上HashMap运行情况和上面的散列表的介绍差不多。计算该数据的Hash值来判断是否放在同一位置，假如Hash值相同则形成链表存放在同一位置处。JDK1.8采用了红黑树才进一步消除关于冲突的问题，当数组长度大于64，链表长度大于8就会采用红黑树来储存。

HashMap桶和查找位置算法

对于存放位置的数组，我们在HashMap称为桶。

HashMap则使用了拉链式的散列算法，并在 JDK 1.8 中引入了红黑树优化过长的链表。

那么具体是如何定义存放桶的位置呢？

1. 调用对象的hashcode()，获得hashcode
2. 根据hashcode计算出需要的hash值（需要生成的值在我们数组范围内），一个常用和简单地计算方法就是hash=hashcode%n(数组的长度)

你可能会在源码中疯狂看见一段代码(n - 1) & hash，不过后来改进了算法。首先数组长度是2的整数幂，而且就算扩容也是按照2倍来扩容，所以使用(n - 1) & hash的效果和hash=hashcode%n(数组的长度)是一样的。不过前者更快，因为是位运算。

HashMap类属性和实现接口

直接上代码，晕死丫的

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
     /**
     * 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的幂<= 1<<30。
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     * 在构造函数中未指定时使用的负载系数。负载因子
     */
    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.
     * 使用树而不是列表的容器计数阈值。当向至少有这么多节点的容器中添加元素时，容器被转换为树。
     * 该值必须大于2，并且应该至少为8，以与关于在收缩时转换回普通bins的树移除假设相匹配。
     * 简单来说就是界定了什么时候转变为树状结构
     */
    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.
     * 在调整大小操作期间取消树状(分裂)仓的堆数阈值。应小于TREEIFY_THRESHOLD，且最多为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.
     * 容器可以树形化的最小表容量。(否则，如果一个容器中有太多节点，则会调整表的大小。)应该至少为4 * TREEIFY_THRESHOLD，以避免调整大小和树形化阈值之间的冲突。
     * 用人话说就是当桶大于64就会变成红黑树（条件的一种）另一方面也说明了红黑树的桶最小是64
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    /**
     * 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.)
     * 表，第一次使用时初始化，并根据需要调整大小。当分配时，长度总是2的幂。(在某些操作中，我们也允许长度为零，以允许当前不需要的引导机制。)
     * 说人话，这就是所谓的桶了，分配时，总长度总是2的幂
     */
    transient Node<K,V>[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     * 保存缓存的entrySet()。注意，keySet()和values()使用了AbstractMap字段。
     * 迭代器所使用的数值
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * The number of key-value mappings contained in this map.
     * 此映射中包含的键-值映射的数量。不过这个size并不代表桶（数组）的长度
     */
    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).
     * 结构修改是指改变HashMap中的映射数量或修改其内部结构(例如，rehash)。该字段用于使HashMap的集合视图上的迭代器快速失败。(见ConcurrentModificationException)。
     * 和之前我在ArrayList文章里讲的一样，简单理解为程序计数器，在使用迭代器时，多线程修改数据会报错
     */
    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;

这里面的值有几个比较关键

• loadFactory加载因子：就如文章一开始所言，太大导致查找元素效率低，太小导致数组利用率低，所以默认值DEFAULT_LOAD_FACTOR=0.75这是官方给出的一个比较号的临界值。static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16默认容量为16，也就是说当数据量达到了16*0.75=12的时候会进行扩容。扩容是非常消耗性能的操作，因为扩容会改写所有数据的Hash值。我们使用时应尽量避免扩容
• threshold:当size>=threshold的时候就会触发扩容

下面是Node节点类，这里只分享链表的类，树的类换在下一节讲

/**
 * Basic hash bin node, used for most entries.  (See below for
 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 * 基本hash bin节点，用于大多数条目。(参见下面的TreeNode子类和LinkedHashMap的Entry子类。)
 */
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;
        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类应该很简单，阉割版的链表node，不过其中加了个属性hash

HashMap构造方法

直接先上代码！

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *
 *构造一个空的<tt>HashMap</tt>，具有指定的初始容量和负载因子。
 * @param  initialCapacity the initial 初始容量
 * @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) {
    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);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 *构造一个空的<tt>HashMap</tt>，具有指定的初始容量和默认的负载因子(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).
 *构造一个空的<tt>HashMap</tt>，默认初始容量(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>.
 **构造一个新的<tt>HashMap</tt>，其映射与指定的<tt>Map</tt>相同。创建<tt>HashMap</tt>时，默认负载因子(0.75)和初始容量足以容纳指定的<tt>Map</tt>中的映射。
 * @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次幂大小。这是一个算法，还是比较抽象的，可以不用理解那么深。
 * 必须要保证容量总是2的幂。这样寻找数据的算法才有效。
 */
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;
}

/**
 * Implements Map.putAll and Map constructor.
 * 实现了putAll和Map构造函数。
 *
 * @param m the map
 * @param evict false when initially constructing this map, else
 * true (relayed to method afterNodeInsertion).
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    //首先判断输入进来的map是否有容量，得有容量才能进行操作
    if (s > 0) {
        //判断该HashMap是否已经初始化过了
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            //判断ft是否大于最大值，取得这个map的容量
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                //调用上面的方法，返回给定目标容量的2次幂大小
                threshold = tableSizeFor(t);
        }
        //已初始化，并且m的size大于临界值就需要扩容
        else if (s > threshold)
            resize();
        //循环遍历添加到HashMap中
        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);
        }
    }
}

你别看构造方法挺多的样子，实际上就是把一些值赋给类里的属性。

存入数据

主要是put方法的介绍，其他都大差不差。这个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.
 * *将map中的指定值与指定键关联。如果之前的映射包含键的映射，则旧值将被替换。
 * @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) {
    return putVal(hash(key), key, value, false, true);
}

/**
 * Implements Map.put and related methods.
 * 这个翻译没啥意思，就是实现了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 onlyIfAbsent如果为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) {
    //初始化1个空的节点数组（用于承接本类中的桶），初始化1个空节点（用于承接该key位置的节点），两个int值（承接容量）
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果桶是空的，也就意味着第一次插入数据
    if ((tab = table) == null || (n = tab.length) == 0)
        //如果是第一次插入，则进行第一次扩容
        n = (tab = resize()).length;
    //(n - 1) & hash是确定元素放入哪个桶中，如果桶是空的，则新生成节点放进去就行了
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //如果桶里面有数据
        //定义一个节点用于插入数据
        Node<K,V> e; K k;
        //比较桶里面的第一个元素，如果刚好是这个key，则直接替换
        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);
                    //如果插入以后结点数量达到阈值（8），则触发方法
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //该方法会判断是否真的转为红黑树
                        treeifyBin(tab, hash);
                    //跳出循环
                    break;
                }
                //判断链表中的结点key是否与插入元素的key相同，如果相同则插入
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //用于遍历链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        //如果e不是空，说明已经找到了与之匹配的节点
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //这里根据方法最上面的配置来决定是否替换数据
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //该方法在HashMap中是空方法
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //判断是否需要扩容
    if (++size > threshold)
        resize();
    //该方法在HashMap中是空方法
    afterNodeInsertion(evict);
    return null;
}

总的来说put方法的逻辑是：

1. 先判断table是否为空，如果长度是0的话要进行第一次扩容
2. 先找到对应的桶，如果这个桶中没有数据则直接插入
3. 如果桶里面已经有元素了，那么就遍历这个桶中的链表，找到这个key
4. 如果找不到就插入到这个链表的结尾。
5. 修改结构，增加程序计数器和map的size

获取节点

主要看get方法

/**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 * 返回指定键映射到的值，如果此映射不包含键的映射，则返回 {@code null}。
 * 
 * <p>More formally, if this map contains a mapping from a key
 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 * key.equals(k))}, then this method returns {@code v}; otherwise
 * it returns {@code null}.  (There can be at most one such mapping.)
 * 更正式地说，如果此映射包含从键 k 到值 v 的映射，使得 {(key==null ? k==null : key.equals(k ))}，则此方法返回 {@code v}; 否则返回 {@code null}。 （最多可以有一个这样的映射。）
 *
 * <p>A return value of {@code null} does not <i>necessarily</i>
 * indicate that the map contains no mapping for the key; it's also
 * possible that the map explicitly maps the key to {@code null}.
 * The {@link #containsKey containsKey} operation may be used to
 * distinguish these two cases.
 *
 * {@code null} 的返回值并不<i>必然</i>表示映射不包含键的映射； 地图也有可能将键显式映射到 {@code null}。 {@link #containsKey containsKey} 操作可用于区分这两种情况。
 * @see #put(Object, Object)
 * 说了这么多是什么意思呢？其实就是get方法返回null的情况有两种，一种是根本不存在这个键，另一种情况是这个键本身存储的数据就是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的数组用于临时保存桶，定义一个节点用来指向桶中的首个节点，定义int来代表桶的长度，定义一个K来定义键
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //如果桶不是空的，且桶中有数据（也就是桶中有第一个节点不为空）
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //总是先检查第一个节点，判断键和hash是否相同，如果相同则返回
        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;
}

get方法的话就不多说了，如果能把put方法都理顺的话。

扩容

扩容是HashMap中比较重要的节点，同时也是比较消耗性能的方法，因为需要重新整理所有Hash值。还有不要因为这段代码过于长就害怕！一定要支棱起来！

/**
 * 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.
 *
 * 初始化或加倍表大小。 如果为空，则分配符合初始容量目标保持在现场阈值。
 * 否则，因为我们使用的是二次幂扩展，所以每个 bin 中的元素必须保持相同的索引，或者移动在新表中具有 2 次方偏移。
 * @return the table
 */
final Node<K,V>[] resize() {
    //老样子，把现在的桶赋值给oldTab以做备用
    Node<K,V>[] oldTab = table;
    //假如是空，则之前桶的大小为0
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //把现在的临界值赋值给oldThr
    int oldThr = threshold;
    //初始化新的桶容量和临界值
    int newCap, newThr = 0;
    //如果之前桶容量大于0，也就是桶不为空的
    if (oldCap > 0) {
        //判断桶容量是否已经超过最大上线，如果超了就不扩容了，直接返回之前桶的容量
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //判断新的容量扩容2倍是否会大于最大容量，这里使用了位运算，实际上就是扩容2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //这里会出现这种情况的可能是调用其他构造器生成时，将使用 threshold 变量暂时保存 initialCapacity 参数的值
    else if (oldThr > 0) // initial capacity was placed in threshold
        //这里的目的是扩容到initialCapacity的这个值
        newCap = oldThr;
    //如果都不满足说明调用得是无参构造器，直接赋值默认值
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //如果newThr为0，说明没有赋值了默认值，现在就要计算它的值
    if (newThr == 0) {
	//这是计算他们值的过程，新的桶容量乘以负载因子
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //更新HashMap的临界值
    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;
            //如果这个桶中有数据
            if ((e = oldTab[j]) != null) {
                //清空这个数据
                oldTab[j] = null;
                //如果next为空，代表该节点是尾节点
                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) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

扩容方法其实很复杂。其中涉及到了某些算法，这里要深究的话可以深究为什么要使用这个算法，时候之后会怎样。

但是假如不深究上述内容，总的大体流程为：

1. 创建所需要的默认值
2. 判断是否超过最大容量，没有超过则扩大容量为原理的2倍，判断是否是第一次扩容，如果是则直接赋值默认值
3. 重新计算新的临界值
4. 遍历之前桶数组中的所有数据，假如这个桶不为空
5. 给之前的数据重新分组
6. 重新映射到新的桶中

其他方法

其他删除的方法就比较简单了，就不一一举例了。

这篇文章完全是站在巨人的肩膀上进行的，我也是根据源码根据别人的博客一步一步摸索产生的。以下贴两个我觉得写的最好的关于HashMap的文章链接。

HashMap 源码详细分析(JDK1.8)-coolblog

源码+底层数据结构分析

关于散列表的知识我主要借鉴了《算法图解》和《大话数据结构》