java集合——HashMap源码

java集合——HashMap源码 1、jdk1.7关键代码

public class HashMap
    extends AbstractMap
    implements Map, Cloneable, Serializable
{
    // 默认数组大小
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // 默认加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    static final Entry[] EMPTY_TABLE = {};

    transient Entry[] table = (Entry[]) EMPTY_TABLE;

    transient int size;

    int threshold;

    final float loadFactor;

    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }

    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++; // 修改次数
        addEntry(hash, key, value, i);
        return null;
    }

    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

    private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestoneBit((number - 1) << 1) : 1;
    }

    final boolean initHashSeedAsNeeded(int capacity) {
        boolean currentAltHashing = hashSeed != 0;
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean switching = currentAltHashing ^ useAltHashing;
        if (switching) {
            hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }

    private V putForNullKey(V value) {
        for (Entry e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

    final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

1.1、底层数据结构

上面是HashMap的关键代码，其中Entry[] table数组是实际存储数据的底层数组。下面来看看table数组的类型（Entry是HashMap中的静态内部类，是一个泛型类，并继承Map.Entry）。

static class Entry implements Map.Entry {
    final K key;     // 键对象
    V value;         // 值对象
    Entry next; // 下一个Entry对象引用
    int hash;

    ......

}

从上面的代码可以看出，HashMap底层实现数据结构（数组+链表）: Entry类型的table数组 + entry类型的链式结构。

1.2、关键方法put

如果底层数组table是空数组，则初始化table。

        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }

根据传入的threshold值计算刚好出比其大的2的N次方为table数组容量。

    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

判断可以是否为null，如果key==null，则保存到table[0]下。

        if (key == null)
            return putForNullKey(value);

    private V putForNullKey(V value) {
        for (Entry e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

从上面的代码可以看出，key为null的entry对象是放在table[0]对象所在的第一条链表中，保存新值并返回原来的值。

然后是计算key的hash值（hash方法后面在研究）：

int hash = hash(key);

根据等到的hash值，计算出table数组索引下标值：

        int i = indexFor(hash, table.length);

    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : 
        // "length must be a non-zero power of 2";
        return h & (length-1);
    }

遍历table[i]下的链表，如果key存在，则替换新值替换老值，并返回老值。

        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this); // hashMap中此方法为空方法
                return oldValue;
            }
        }

如果key不存在于table[i]下的链表中，则以key-value为键值对创建entry对象，并保存。

addEntry(hash, key, value, i);

1.3、关键方法addEntry：

    void addEntry(int hash, K key, V value, int bucketIndex) {
        // 1、判断是否需要扩容table数组
        // 条件：
        // 1)当前HashMap中有效entry个数 >= table数组容量 * loadFactor;
        // 2)当前table[bucketIndex]不为null（table[bucketIndex]存在元素）
        if ((size >= threshold) && (null != table[bucketIndex])) {
            // 扩容table数组
            resize(2 * table.length); 
            // 扩容后需要重新计算hash值和索引下标
            hash = (null != key) ? hash(key) : 0; 
            bucketIndex = indexFor(hash, table.length); 
        }
        // 2、创建entry并保存为table[i]的头结点
        createEntry(hash, key, value, bucketIndex); 
    }

先来看createEntry方法：

    void createEntry(int hash, K key, V value, int bucketIndex) {
        // 获取table[bucketIndex]，即table[bucketIndex]为所在链表的头结点
        Entry e = table[bucketIndex];
        // 创建Entry，将之前的 头结点e 设置为新new节点的后置next节点
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

从createEntry方法可以看出，新创建的entry节点是作为头结点放在table数组指定下标的链表中。

下面我们重点看一下addEntry方法中出现的resize(2 * table.length)代码。

从传入resize方法的参数（2 * table.length）可以看出，在扩容的时候底层table数组实际变为原先长度的2倍。

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        // 1、如果当前table数组的长度已经是2的30次方，则不进行扩容
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        Entry[] newTable = new Entry[newCapacity];
        // 2、转移老table数组的元素到新table数组上（重要）
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

进入transfer方法，遍历老table数组和链表中的entry，重新计算hash值和新数组table索引下标，并将entry迁移到新table数组中:

    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry e : table) {
            while(null != e) {
                Entry next = e.next;
                // 是否需要重新计算hash值
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                // 重新计算table数组索引下标
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

以上就是hashMap的put方法的主要流程，在其中我们应该注意额外几点：

1）hashSeed的作用

    transient int hashSeed = 0;

2）roundUpToPowerOf2方法的作用

    private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestoneBit((number - 1) << 1) : 1;
    }

3）initHashSeedAsNeeded方法的作用

    final boolean initHashSeedAsNeeded(int capacity) {
        boolean currentAltHashing = hashSeed != 0;
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean switching = currentAltHashing ^ useAltHashing;
        if (switching) {
            hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }

4）hash方法的作用

    final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

2、jdk1.8关键代码

public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable {
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    // 底层table数组最大长度2的30次方
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // 默认加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 链表树化的元素个数
    static final int TREEIFY_THRESHOLD = 8;

    // 解除树化的元素个数
    static final int UNTREEIFY_THRESHOLD = 6;

    // 树化时底层table的最小长度
    static final int MIN_TREEIFY_CAPACITY = 64;

    // 底层数组table
    transient Node[] table;

    // 有效元素个数
    transient int size;

    // 实际加载因子
    final float loadFactor;
    
    // 默认构造器，只设置 加载因子，其他属性取默认值
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

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

    // 计算hash值
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    // 实际put值的方法
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        // 1、hash表 底层table数组为空则初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 2、如果计算的table数组下标的头结点为空，
        //    则将数据创建一个node，并设置为底层数组中table[i]链表的头结点
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            // 3、如果当前节点table[i]的hash值和需要新增的key的hash值相同，则替换
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 4、如果 table[i]节点 是TreeNode，则执行putTreeval方法
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            else {
                // 5、无限for循环 遍历table[i]链表或树
                for (int binCount = 0; ; ++binCount) {
                    // 1）遍历到尾节点，创建Node节点并跳出循环
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 执行树化
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 2）如果节点e的hash值和需要新增的key的hash值相同，跳出循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 循环
                    p = e;
                }
            }
            // 6、如果 e 不为null，则表示key存在，则替换oldValue并返回
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 7、如果hash表中的有效元素个数 > threshold，就重新挑战底层数组table的数组
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    
    // 创建Node节点
    Node newNode(int hash, K key, V value, Node next) {
        return new Node<>(hash, key, value, next);
    }

    // 树化方法
    final void treeifyBin(Node[] tab, int hash) {
        int n, index; Node e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode hd = null, tl = null;
            do {
                TreeNode p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

    // 树化后put方法
    final TreeNode putTreeval(HashMap map, Node[] tab,
                                   int h, K k, V v) {
        Class kc = null;
        boolean searched = false;
        TreeNode root = (parent != null) ? root() : this;
        for (TreeNode p = root;;) {
            int dir, ph; K pk;
            if ((ph = p.hash) > h)
                dir = -1;
            else if (ph < h)
                dir = 1;
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                return p;
            else if ((kc == null &&
                     (kc = comparableClassFor(k)) == null) ||
                     (dir = compareComparables(kc, k, pk)) == 0) {
                if (!searched) {
                    TreeNode q, ch;
                    searched = true;
                    if (((ch = p.left) != null &&
                        (q = ch.find(h, k, kc)) != null) ||
                        ((ch = p.right) != null &&
                        (q = ch.find(h, k, kc)) != null))
                        return q;
                }
                dir = tieBreakOrder(k, pk);
            }

            TreeNode xp = p;
            if ((p = (dir <= 0) ? p.left : p.right) == null) {
                Node xpn = xp.next;
                TreeNode x = map.newTreeNode(h, k, v, xpn);
                if (dir <= 0)
                    xp.left = x;
                else
                    xp.right = x;
                xp.next = x;
                x.parent = x.prev = xp;
                if (xpn != null)
                    ((TreeNode)xpn).prev = x;
                moveRootToFront(tab, balanceInsertion(root, x));
                return null;
            }
        }
    }

    // 扩容底层table数组
    final Node[] resize() {
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {// 如果 底层table数组长度 大于 0
            if (oldCap >= MAXIMUM_CAPACITY) {// 如果 底层table数组长度 大于等于2的30次方
                threshold = Integer.MAX_VALUE;
                return oldTab;
            } // 如果 底层table数组长度 在 2的4次方到2的29次方之间，则扩容为原来的2倍
            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 {    // 1、当底层数组table还是空时，给hashMap对象的元素容量和扩容阈值赋值
            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;
        // 2、按照 新容量（oldCap << 1，即原来容量的2倍） 来创建 新的底层数组table
        Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node 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;
    }

    ......

}

2.1、底层数据结构

从关键代码上看，底层数据结构依旧是table数组（transient Node[] table），元素的类型是Node（注意：在后续HashMap中的链表树化后，链表节点类型TreeNode extends linkedHashMap.Entry，然而 linkedHashMap.Entry extends HashMap.Node，所以实际上链表的数据节点类型依旧是Node）。

2.2、关键方法put

put方法执行的表象：put一个键值对k-v到hashMap中，如果k不存在于map中则添加进去返回null，如果k存在于map中则用新v替换老v并返回老v。

具体代码逻辑如下：

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

先调用hash方法计算hash值：

    // 计算hash值
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

然后将关键put的参数传入putVal方法：

    // 实际put值的方法
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        // 1、hash表 底层table数组为空则初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 2、如果计算的table[i]链表为空，
        //    则将数据创建一个node，并设置为底层数组中table[i]链表的头结点
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            // 3、如果当前节点table[i]的hash值和需要新增的key的hash值相同，则替换
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 4、如果 table[i]节点 是TreeNode，则执行putTreeval方法
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            else {
                // 5、无限for循环 遍历table[i]链表或树
                for (int binCount = 0; ; ++binCount) {
                    // 1）遍历到尾节点，创建Node节点并跳出循环
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 执行树化
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 2）如果节点e的hash值和需要新增的key的hash值相同，跳出循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 循环
                    p = e;
                }
            }
            // 6、如果 e 不为null，则表示key存在，则替换oldValue并返回
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 7、如果hash表中的有效元素个数 > threshold，就重新挑战底层数组table的数组
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

putVal方法需要详细介绍一下执行逻辑：

1）底层table数组（hash表）为空则初始化（默认底层table数组长度为16，扩容阈值为12）；

        // 1、hash表 底层table数组为空则初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

    // 扩容底层table数组
    final Node[] resize() {
        Node[] oldTab = table;
        // 底层table数组为空 容量和扩容阈值都为0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {// 如果 底层table数组长度 大于 0

            ...... 无关代码

        }
        else if (oldThr > 0) // initial capacity was placed in threshold

            ......无关代码

        else {    // 1、当底层数组table还是空时，给hashMap对象的元素容量和扩容阈值赋值
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }

        ...... 无关代码

        threshold = newThr;
        // 2、按照 新容量（oldCap << 1，即原来容量的2倍） 来创建 新的底层数组table
        Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        
        ...... 无关代码

        return newTab;
    }

2）如果当前定位的table[i]链表为空， 则将数据创建一个node，并设置为底层数组中table[i]链表的头结点；

        // 2、如果计算的table[i]链表为空，
        //    则将数据创建一个node，并设置为底层数组中table[i]链表的头结点
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

    Node newNode(int hash, K key, V value, Node next) {
        return new Node<>(hash, key, value, next);
    }

3）如果当前定位的table[i]链表不为空，则进行下面复杂逻辑；

        else {
            Node e; K k;
            // 3、如果当前table[i]链表的头结点的key和新增的key相等，则替换
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 4、如果 table[i]节点 是TreeNode，则执行putTreeval方法
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            else {
                // 5、无限for循环 遍历table[i]链表或树
                for (int binCount = 0; ; ++binCount) {
                    // 1）遍历到尾节点，创建Node节点并跳出循环
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 执行树化
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 2）如果节点e的hash值和需要新增的key的hash值相同，跳出循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 循环
                    p = e;
                }
            }
            // 6、如果 e 不为null，则表示key存在，则替换oldValue并返回
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }

我们先来关注其中无限for循环部分

// 5、无限for循环 遍历table[i]链表或树
for (int binCount = 0; ; ++binCount) {
    // 1）遍历到尾节点，创建Node节点并跳出循环
    if ((e = p.next) == null) {
        // 创建新node节点
        p.next = newNode(hash, key, value, null);
        // 执行树化
        if (binCount >= TREEIFY_THRESHOLD - 1) // bitCount >= 7
           treeifyBin(tab, hash);
        break;
    }
    // 2）如果节点e的key和新增的key相等，跳出循环
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
          break;
    // 3）循环
    p = e;
}

注意：bitCount是一个标识计数，当bitCount自增8次（即链表的长度为8就开始进行链表的树化），执行treeifyBin(tab, hash)方法逻辑。

            // 6、如果 e 不为null，则表示key存在，则替换oldValue并返回
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }

上面的代码显示，如果key已经存在于HashMap中，则用value替换oldValue，并返回oldValue。

4）修改计数+1，有效个数+，判断底层table数组是否需要扩容，如果需要则执行resize方法扩容。

        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;

    final Node[] resize() {
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {

            ...... 无关代码

            // 1、如果当前底层table数组的长度在2的4次方与2的29次方之间，则扩容2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) 
            ...... 无关代码
        else {               
            ...... 无关代码
        }
        if (newThr == 0) {
            ...... 无关代码
        }
        threshold = newThr;
        Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        // 2、如果底层table数组不为null，则遍历底层table数组和其下的链表，进行扩容相关 *** 作
        if (oldTab != null) { 
            // 遍历底层table数组
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                // 如果table[j]链表存在，则遍历链表
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 如果只有1个元素，则直接重新计算在新table数组的位置并保存
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e; 
                    // 如果已经是树节点
                    else if (e instanceof TreeNode)
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node 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;
    }

5）具体需要介绍一下treeifyBin方法：

    final void treeifyBin(Node[] tab, int hash) {
        int n, index; Node e;
        // 1、如果 底层table数组为null或者长度小于64，则不进行树化，直接进行扩容 *** 作
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        // 2、获取table[index]链表头结点，开始遍历替换节点类型为TreeNode，
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode hd = null, tl = null;
            do {
                TreeNode p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            // 3、将链表进行树化
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

    // 树化
	final void treeify(Node[] tab) {
		TreeNode root = null;
        // 遍历链表，其中this是链表的头结点
		for (TreeNode x = this, next; x != null; x = next) {
			next = (TreeNode)x.next;
			x.left = x.right = null;
            // 红黑树的根为空，则设置为根节点
			if (root == null) {
				x.parent = null;
				x.red = false;
				root = x;
			}
			else {
				K k = x.key;
				int h = x.hash;
				Class kc = null;
                // 遍历 红黑树
				for (TreeNode p = root;;) {
					int dir, ph;
					K pk = p.key;
					if ((ph = p.hash) > h)
						dir = -1;
					else if (ph < h)
						dir = 1;
					else if ((kc == null &&
							  (kc = comparableClassFor(k)) == null) ||
							 (dir = compareComparables(kc, k, pk)) == 0)
						dir = tieBreakOrder(k, pk);

					TreeNode xp = p;
					if ((p = (dir <= 0) ? p.left : p.right) == null) {
						x.parent = xp;
						if (dir <= 0)
							xp.left = x;
						else
							xp.right = x;
						root = balanceInsertion(root, x);
						break;
					}
				}
			}
		}
		moveRootToFront(tab, root);
	}