Java 集合类系列（一）——HashMap源码分析

一、HashMap 概述

HashMap 在 java 里用于存储 Key-Value 结构的数据，它允许 key 和 value 为 null，是一种无序并且线程不安全的集合对象。HashMap 基于 hashing 的原理，内部使用的是数组加链表的结构，在 JDK 1.8 上对查询性能进行优化，链表长度大于一定值过后链表将重构为红黑树。本文对 HashMap 源码进行分析，了解其实现原理。

1.1 结构设计

HashMap 采用数组+链表或数组+红黑树的方式存储一条数据，数据结构如下图：

核心思想： 使用 hashCode 方法获取对象的 hash 散列值，通过散列值和数组长度进行与操作计算出数组下标，将对象均匀的存储在数组上，如果出现 hash 冲突则采用链表的方式存储冲突的值，如果冲突的数据过多，将链表转为红黑树以优化查询性能。

通过数组存储数据，使用链表和红黑树是为了应对冲突不得已的选择。

1. 数组容量和扩容的设计

HashMap 将数组长度设计为2幂，每次扩容为原先容量的2倍，要理解需要一点位运算的知识，这么做可以提高性能，降低扩容的复杂性。

每次进行数据操作时，都需要进行通过 hashCode 计算对应数组下标的操作，一般情况下只能通过取模的方式计算 hash 对应的数组下标。将数组长度设计为2的幂，数组最大下标的二进制低位数全部为 1，就可以通过 & 的方式计算下标，相比于取模的方式具有更高的性能。

进行数组扩容时，数组上的链表或红黑树需要进行拆分分配到新的数组上，数组下标为2的幂时，扩容为原先的两倍，从二进制上看只是低位增加了一个位，原先的链表可以被分为固定的两个下标，并且可以确保新的下标没有数据，降低了扩容的复杂性，提升了扩容的性能。

1.2 属性分析

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


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;


static final int MIN_TREEIFY_CAPACITY = 64;


transient Node[] table;

transient Set> entrySet;

transient int size;

transient int modCount;

int threshold;

final float loadFactor;

二、put 插入实现

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

2.1 hash 处理

hash 方法将 hashCode 的高 16 位和低 16 位进行异或操作，原先的高 16 位不变。

在计算 hashCode 对应的数组下标时，采用数组容量 - 1 和 hashCode 进行与操作进行计算，在数组容量比较小的时候，hashCode 的高位并不会参与到数组下标的计算。此处高位和低位进行异或的目的是为了在散列时能够尽量的考虑高位的影响，使散列更加的均匀，减少冲突。

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

2.2 putVal 插入数据

putVal 是实际进行数据插入的方法，首先判断了数组是否已经初始化，未初始化则进行数组初始化。数据插入时，先判断 hash 对应的数组下标是否已经存在数据，如果未存在则直接插入。数组下标已被占用则遍历占用数据的节点，红黑树和链表两种结构有不同的遍历方式，红黑树使用 putTreeval 方法遍历插入，链表从前往后遍历，未找到相同的 key 则插入到链表尾部，如果插入后链表长度大于 8 时链表将转化为红黑树。如果找到 key 相同的节点则根据 onlyIfAbsent 判断，如果是 true 就进行值替换，未找到节点则在链表尾部新建节点插入，如果插入后链表长度大于 8 时链表将转化为红黑树。

// onlyIfAbsent: 如果key已存在，是否替换值
// evict: 是否处于创建模式，在HashMap中未使用到
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        // 当前node列表未初始化，进行列表初始化
        n = (tab = resize()).length;
    // 通过与运算判断指定下标是否已经被占用
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 未被占用，创建并放入节点
        tab[i] = newNode(hash, key, value, null);
    else {
        Node e; K k;
        // hash相同，且key为同一个对象或equals比较相同，表示为同一个key
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 取出p
            e = p;
        // 红黑树实现
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
        // 链表实现
        else {
            // binCount = 0，而对应的e却是第二个节点
            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;
                }
                // hash相同，且key为同一个对象或equals比较相同，表示为同一个key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // e不为null表示不是插入节点，而是找到了key相同的数据
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent为false或者原先value为null
            if (!onlyIfAbsent || oldValue == null)
                // 替换value的值
                e.value = value;
            // 后置处理，未使用
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 修改次数+1
    ++modCount;
    //数组长度达到扩容阀值
    if (++size > threshold)
        // 扩容
        resize();
    // 后置处理，未使用
    afterNodeInsertion(evict);
    return null;
}

2.3 resize 数组扩容

数组已经初始化时： 如果数组已经达到最大值则修改扩容阀值为 Integer.MAX_VALUE，否则将数组增加为原先的2倍，并对数组上的链表和红黑树进行重新分配。如果扩容后的数组容量已经达到最大值则将扩容阀值设置为 Integer.MAX_VALUE 不再进行扩容，如果扩容前的数组容量小于默认数组容量，将对阀值进行重新计算，因为原先的容量太小，计算的阀值有比较大的误差。

数组未初始化时： 数组未初始化时 threshold 可能存储着构造方法设置的初始数组容量，如果 threshold 不为 0，则将初始化容量为 threshold 的数组，并根据该容量计算 threshold 扩容阀值，如果 threshold 为 0 则使用默认值创建创建数组并计算扩容阀值。

final Node[] resize() {
    // 取得原数组
    Node[] oldTab = table;
    // 取得原数组长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 取得原扩容阀值
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 数组已经初始化
    if (oldCap > 0) {
        // 原数组长度已经大于等于最大值了
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 阀值设置为int的最大值
            threshold = Integer.MAX_VALUE;
            // 直接返回
            return oldTab;
        }
        // 计算新容量，新容量小于最大容量且原容量大于等于默认容量
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 新阀值等于原阀值的2倍
            newThr = oldThr << 1; // double threshold
    }
    // 数组未初始化但是阀值大于0，这是构造方法指定initialCapacity的场景
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 将阀值设置为数组的初始化容量
        newCap = oldThr;
    else { // 零初始阈值表示使用默认值
        // 使用默认值初始化数组容量和阀值
        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[] 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;
                        // 容量扩容两倍，hash中多一个位参与下标计算，但是
                        // 这个位是0，所以下标不变
                        if ((e.hash & oldCap) == 0) {
                            // 设置原下标链表的首个节点
                            if (loTail == null)
                                loHead = e;
                            else
                                // 设置链表的next
                                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;
}

以上代码可以看到，扩容时采用的是尾部插入的方法，在 JDK 1.8 中采用的是头部插入的方法

因为头部插入将导致插入链表顺序倒置，多个线程进行插入时可能造成循环链表的问题

三、get 取值实现

先计算出key 的 hash，然后使用 getNode 方法取得对应的 Node 对象。

public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

3.1 getNode 取值

首先确定数组已经初始化，hash 对应的下标存在节点。判断首个节点 key 是否相等，如果相等则直接返回，否则将遍历后继节点，红黑树和链表遍历的方式不同。

final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    // 数组已经初始化，而且hash对应下标的位置不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 首个节点key相同，直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 首个节点后面存在后继节点
        if ((e = first.next) != null) {
            // 当前是红黑树结构
            if (first instanceof TreeNode)
                // 使用红黑树方式寻找节点
                return ((TreeNode)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;
}

四、remove 删除实现

remove 包含带 value 和不带 value 两个重载方法，当传入 value 时，需要 key 和 value 都比较通过才会删除数据。

public V remove(Object key) {
    Node e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}

4.1 removeNode 删除节点

// matchValue为true时比较value相等才进行删除
// movable在红黑树结构中使用，为false在删除时不移动其他节点
final Node removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node[] tab; Node p; int n, index;
    // 数组已经初始化，而且hash对应下标的位置不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node node = null, e; K k; V v;
        // 首个节点的key相等
        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)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    // 暂存e到p，将会是node的前一个节点
                    p = e;
                // 从前往后循环遍历节点
                } while ((e = e.next) != null);
            }
        }
        // 找到了node，matchValue为false，或者value的值与指定的值相等
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 红黑树的结构
            if (node instanceof TreeNode)
                //删除node节点
                ((TreeNode)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // key为链表的第一个节点，修改数组的引用
                tab[index] = node.next;
            else
                // key不是第一个节点，修改前一个节点的引用
                p.next = node.next;
            // 操作次数+1
            ++modCount;
            // 容量-1
            --size;
            // 后置处理，未实现
            afterNodeRemoval(node);
            // 返回被删除的节点
            return node;
        }
    }
    return null;
}

五、遍历的实现 5.1 HashIterator 实现

HashIterator 是一个抽象的迭代器，从数组下标小到大，链表或红黑树的 next 引用向后遍历所有数据，取出的是 Node，供 EntryIterator 、KeyIterator 和 ValueIterator 继承，进一步取出想要的数据。

abstract class HashIterator {
    // 下一个要返回的node
    Node next;        // next entry to return
    // 当前node
    Node current;     // current entry
    // 当前HashMap的修改次数
    int expectedModCount;  // for fast-fail
    // 当前遍历到数组的位置
    int index;             // current slot
    HashIterator() {
        expectedModCount = modCount;
        Node[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
            // 遍历找到第一个next节点
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }
    // 下一个要遍历的next不为0
    public final boolean hasNext() {
        return next != null;
    }
    // 取得下一个节点
    final Node nextNode() {
        Node[] t;
        Node e = next;
        // 确定map未被修改过
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        // 下一个next为空
        if (e == null)
            throw new NoSuchElementException();
        // node的next引用为空，增大数组下标寻找下一个节点
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }
    // 删除当前节点
    public final void remove() {
        Node p = current;
        if (p == null)
            throw new IllegalStateException();
        // map修改次数变化，抛出异常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        // 当前node设置为空
        current = null;
        K key = p.key;
        // 删除node
        removeNode(hash(key), key, null, false, false);
        // 更新修改次数
        expectedModCount = modCount;
    }
}

removeNode 方法的 movable 参数指定删除数据时红黑树是否移动节点，如果移动节点将导致 next 引用更新，可能会出现部分节点被遗漏遍历，这也是 HashMap 遍历时不允许删除数据的原因。

但是 HashIterator 迭代器设置的 movable 参数为 false，此时不会更新红黑树的结构，正因为如此，HashMap 仅允许在迭代器中删除数据。

KeyIterator 继承了 HashIterator 从中取出 key。

final class KeyIterator extends HashIterator
    implements Iterator {
    // 从HashIterator取出key
    public final K next() { return nextNode().key; }
}

ValueIterator 继承了 HashIterator 从中取出 value。

final class ValueIterator extends HashIterator
    implements Iterator {
    public final V next() { return nextNode().value; }
}

EntryIterator 继承了 HashIterator 直接取出并返回 Node，Node 继承了 Map.Entry，以基类作为类型返回给外部。

final class EntryIterator extends HashIterator
    implements Iterator> {
    public final Map.Entry next() { return nextNode(); }
}

每一个迭代器的 next 都是通过 nextNode 取值的，nextNode 中进行了数据修改次数的校验，所以在迭代时 Map 的内容是不允许改变的。

5.2 HashMapSpliterator 实现

HashMapSpliterator 是一个抽象类，供 KeySpliterator、ValueSpliterator、EntrySpliterator 继承，使用 getFence 方法进行参数初始化，current 用于存储在当前下标中 node 具体的位置，如果 current 不为空时不允许 trySplit 切分。

static class HashMapSpliterator {
    // 需要遍历的map
    final HashMap map;
    // 当前节点
    Node current;
    // 当前的数组下标
    int index;
    // map的数组结束位置,-1表示未初始化
    int fence;
    // map的总数据量
    int est;
    // map被修改次数
    int expectedModCount;
    HashMapSpliterator(HashMap m, int origin,
                       int fence, int est,
                       int expectedModCount) {
        this.map = m;
        this.index = origin;
        this.fence = fence;
        this.est = est;
        this.expectedModCount = expectedModCount;
    }
    // 初始化参数
    final int getFence() {
        int hi;
        // fence小于0
        if ((hi = fence) < 0) {
            HashMap m = map;
            // 取得map数据量
            est = m.size;
            // 取得map被修改的次数
            expectedModCount = m.modCount;
            Node[] tab = m.table;
            // 取得 table数组的长度
            hi = fence = (tab == null) ? 0 : tab.length;
        }
        // 返回数组长度
        return hi;
    }
    // 预估数据量大小
    public final long estimateSize() {
        // 初始化
        getFence(); // force init
        return (long) est;
    }
}

5.2.1 KeySpliterator 实现

KeySpliterator 继承了 HashMapSpliterator 抽象类，实现了 Spliterator 接口，通过 table 数组下标对迭代器进行平均切分，每次切分之后预估的数据量缩小为原来的二分之一。

static final class KeySpliterator
    extends HashMapSpliterator
    implements Spliterator {
    KeySpliterator(HashMap m, int origin, int fence, int est,
                   int expectedModCount) {
        super(m, origin, fence, est, expectedModCount);
    }
    public KeySpliterator trySplit() {
        // hi=map的数组结束位置,lo=当前数组下标，mid=lo+hi的平均值
        int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
        // 如果当前数组下标大于等于平均值，或者current不为空返回null
        // 否则返回一个新的Spliterator，新迭代器从原迭代器index开始，到平均值结
        // 束，并预估数据量为原迭代器的一半，当前迭代器的index则更新为从平均值开始
        return (lo >= mid || current != null) ? null :
            new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
                                    expectedModCount);
    }
    public void forEachRemaining(Consumer action) {
        int i, hi, mc;
        if (action == null)
            throw new NullPointerException();
        HashMap m = map;
        Node[] tab = m.table;
        // fence小于0
        if ((hi = fence) < 0) {
            // 更新map修改次数
            mc = expectedModCount = m.modCount;
            // 读取数组长度到fence
            hi = fence = (tab == null) ? 0 : tab.length;
        }
        else
            // 取得预期的修改次数
            mc = expectedModCount;
        // map已经初始化，index>=0，fence大于index或当前node不为null
        if (tab != null && tab.length >= hi &&
            (i = index) >= 0 && (i < (index = hi) || current != null)) {
            Node p = current;
            current = null;
            do {
                // 当前node为null，数组下标+1
                if (p == null)
                    p = tab[i++];
                else {
                    // 执行，并next引用
                    action.accept(p.key);
                    p = p.next;
                }
            // 当前节点不为空，或者数组下标未达到最大值
            } while (p != null || i < hi);
            // 版本改变
            if (m.modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
    public boolean tryAdvance(Consumer action) {
        int hi;
        if (action == null)
            throw new NullPointerException();
        Node[] tab = map.table;
        // 确定map初始化和参数
        if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
            // 当前node不为null
            while (current != null || index < hi) {
                // 增大数组下标取值
                if (current == null)
                    current = tab[index++];
                else {
                    K k = current.key;
                    // 更新当前node位置
                    current = current.next;
                    action.accept(k);
                    // 版本变化
                    if (map.modCount != expectedModCount)
                        throw new ConcurrentModificationException();
                    return true;
                }
            }
        }
        return false;
    }
    public int characteristics() {
        // 如果est等于数组长度，表示是第一个迭代器，SIZED表示数组长度可以确定
        return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
            // DISTINCT，key肯定是互相不同的
            Spliterator.DISTINCT;
    }
}

5.2.2 ValueSpliterator 实现

static final class ValueSpliterator
    extends HashMapSpliterator
    implements Spliterator {
    ValueSpliterator(HashMap m, int origin, int fence, int est,
                     int expectedModCount) {
        super(m, origin, fence, est, expectedModCount);
    }
    public ValueSpliterator trySplit() {
        // hi=map的数组结束位置,lo=当前数组下标，mid=lo+hi的平均值
        int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
        // 如果当前数组下标大于等于平均值，或者current不为空返回null
        // 否则返回一个新的Spliterator，新迭代器从原迭代器index开始，到平均值结
        // 束，并预估数据量为原迭代器的一半，当前迭代器的index则更新为从平均值开始
        return (lo >= mid || current != null) ? null :
            new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
                                      expectedModCount);
    }
    public void forEachRemaining(Consumer action) {
        int i, hi, mc;
        if (action == null)
            throw new NullPointerException();
        HashMap m = map;
        Node[] tab = m.table;
        // fence小于0
        if ((hi = fence) < 0) {
            // 更新map修改次数
            mc = expectedModCount = m.modCount;
            // 读取数组长度到fence
            hi = fence = (tab == null) ? 0 : tab.length;
        }
        else
            // 取得预期的修改次数
            mc = expectedModCount;
        // map已经初始化，index>=0，fence大于index或当前node不为null
        if (tab != null && tab.length >= hi &&
            (i = index) >= 0 && (i < (index = hi) || current != null)) {
            Node p = current;
            current = null;
            do {
                if (p == null)
                    p = tab[i++];
                else {
                    // 执行，并next引用
                    action.accept(p.value);
                    p = p.next;
                }
            } while (p != null || i < hi);
            // 版本变化
            if (m.modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
    public boolean tryAdvance(Consumer action) {
        int hi;
        if (action == null)
            throw new NullPointerException();
        Node[] tab = map.table;
        // 确定map初始化和参数
        if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
            while (current != null || index < hi) {
                if (current == null)
                    current = tab[index++];
                else {
                    V v = current.value;
                    // 更新当前node位置
                    current = current.next;
                    action.accept(v);
                    // 版本变化
                    if (map.modCount != expectedModCount)
                        throw new ConcurrentModificationException();
                    return true;
                }
            }
        }
        return false;
    }
    public int characteristics() {
        // 如果est等于数组长度，表示是第一个迭代器，SIZED表示数组长度可以确定
        // value是有可能重复的
        return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);
    }
}

5.2.3 EntrySpliterator 实现

static final class EntrySpliterator
    extends HashMapSpliterator
    implements Spliterator> {
    EntrySpliterator(HashMap m, int origin, int fence, int est,
                     int expectedModCount) {
        super(m, origin, fence, est, expectedModCount);
    }
    public EntrySpliterator trySplit() {
        int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
        return (lo >= mid || current != null) ? null :
            new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
                                      expectedModCount);
    }
    public void forEachRemaining(Consumer> action) {
        int i, hi, mc;
        if (action == null)
            throw new NullPointerException();
        HashMap m = map;
        Node[] tab = m.table;
        if ((hi = fence) < 0) {
            mc = expectedModCount = m.modCount;
            hi = fence = (tab == null) ? 0 : tab.length;
        }
        else
            mc = expectedModCount;
        if (tab != null && tab.length >= hi &&
            (i = index) >= 0 && (i < (index = hi) || current != null)) {
            Node p = current;
            current = null;
            do {
                if (p == null)
                    p = tab[i++];
                else {
                    action.accept(p);
                    p = p.next;
                }
            } while (p != null || i < hi);
            if (m.modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
    public boolean tryAdvance(Consumer> action) {
        int hi;
        if (action == null)
            throw new NullPointerException();
        Node[] tab = map.table;
        if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
            while (current != null || index < hi) {
                if (current == null)
                    current = tab[index++];
                else {
                    Node e = current;
                    current = current.next;
                    action.accept(e);
                    if (map.modCount != expectedModCount)
                        throw new ConcurrentModificationException();
                    return true;
                }
            }
        }
        return false;
    }
    public int characteristics() {
        // 如果est等于数组长度，表示是第一个迭代器，SIZED表示数组长度可以确定
        return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
            Spliterator.DISTINCT;
    }
}

5.3 keySet 遍历 key

可以看到，创建了一个 KeySet 对象用于遍历 key。

public Set keySet() {
    Set ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

KeySet 类中和数据相关的操作大都映射到了 HashMap 的方法，并且使用了 KeyIterator 和 KeySpliterator 迭代器。

forEach 方法遍历数据时，遍历顺序是先根据数组下标从前往后遍历，再根据 next 从前往后遍历 node，遍历完成后校验数据是否被修改。

final class KeySet extends AbstractSet {
    // 映射到HashMap的size
    public final int size()                 { return size; }
    // 使用HashMap的clear清除数据
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator iterator()     { return new KeyIterator(); }
    // 使用了containsKey比较key是否存在
    public final boolean contains(Object o) { return containsKey(o); }
    // 使用removeNode删除key对应的数据
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator spliterator() {
        return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    // 遍历数据
    public final void forEach(Consumer action) {
        Node[] tab;
        if (action == null)
            throw new NullPointerException();
        // map不为空
        if (size > 0 && (tab = table) != null) {
            // 存储当前修改次数信息
            int mc = modCount;
            // 遍历table
            for (int i = 0; i < tab.length; ++i) {
                // 遍历key
                for (Node e = tab[i]; e != null; e = e.next)
                    action.accept(e.key);
            }
            // 如果版本改变则抛出异常
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

HashMap 遍历删除时是会抛出异常的，这是因为删除后将导致 modCount 改变，HashMap 主动抛出了 ConcurrentModificationException 异常。但是从上面代码看，遍历完成后才抛出异常，那么使用 try 处理异常是否就可以正常删除数据了？

答案：在只有链表的情况下是可以的这么做的，但是如果包含红黑树结构就会导致部分数据在遍历时被遗落。

如果是链表的结构，删除数据时被删除数据的 next 引用未改变，此时删除数据不会影响遍历。

remove 方法删除数据时 movable 参数为 true，如果是红黑树结构，会移动红黑树其他节点，导致 next 引用改变，部分节点不会被遍历到。

同理，插入数据可能导致数组扩容，链表转换为红黑树等情况，也会导致异常。

5.4 values 遍历 value

创建了一个 Values 对象用于遍历 value。

public Collection values() {
    Collection vs = values;
    if (vs == null) {
        vs = new Values();
        values = vs;
    }
    return vs;
}

Values 类中和数据相关的操作大都映射到了 HashMap 的方法，使用了 ValueIterator 和 ValueSpliterator 迭代器。

forEach 方法遍历数据时，遍历顺序是先根据数组下标从前往后遍历，再根据 next 从前往后遍历 node，同样也是遍历完成之后才校验数据是否被修改。

final class Values extends AbstractCollection {
    // 映射到HashMap的size
    public final int size()                 { return size; }
    // 使用HashMap的clear清除数据
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator iterator()     { return new ValueIterator(); }
    // 使用了containsValue比较value是否存在
    public final boolean contains(Object o) { return containsValue(o); }
    public final Spliterator spliterator() {
        return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer action) {
        Node[] tab;
        if (action == null)
            throw new NullPointerException();
        // map不为空
        if (size > 0 && (tab = table) != null) {
            // 存储当前修改次数信息
            int mc = modCount;
            // 遍历table
            for (int i = 0; i < tab.length; ++i) {
                // 遍历value
                for (Node e = tab[i]; e != null; e = e.next)
                    action.accept(e.value);
            }
            // 如果版本改变则抛出异常
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

5.5 entrySet 遍历键值对

创建了一个 EntrySet 对象用于遍历 Node。

public Set> entrySet() {
    Set> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

final class EntrySet extends AbstractSet> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator> iterator() {
        return new EntryIterator();
    }
    public final boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry) o;
        Object key = e.getKey();
        // 通过key取得node
        Node candidate = getNode(hash(key), key);
        // 比较node是否相等
        return candidate != null && candidate.equals(e);
    }
    public final boolean remove(Object o) {
        if (o instanceof Map.Entry) {
            Map.Entry e = (Map.Entry) o;
            // 取得key和value
            Object key = e.getKey();
            Object value = e.getValue();
            // 通过key和value删除数据
            return removeNode(hash(key), key, value, true, true) != null;
        }
        return false;
    }
    public final Spliterator> spliterator() {
        return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer> action) {
        Node[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            // 存储当前修改次数信息
            int mc = modCount;
            // 遍历table
            for (int i = 0; i < tab.length; ++i) {
                for (Node e = tab[i]; e != null; e = e.next)
                    action.accept(e);
            }
            // 如果版本改变则抛出异常
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

六、其他方法

从数组下标从小到大，然后遍历链表和红黑树，找到与传入 value 相同的值，如果成功找到返回 true。

6.1 containsValue 方法实现

public boolean containsValue(Object value) {
    Node[] tab; V v;
    // table已经初始化完成
    if ((tab = table) != null && size > 0) {
        // 遍历数组
        for (int i = 0; i < tab.length; ++i) {
            // 通过next遍历链表或红黑树
            for (Node e = tab[i]; e != null; e = e.next) {
                // 找到相同的value了
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

6.2 compute 值计算

找到 key 对应的 value，通过 remappingFunction 接口实例进行值计算，需要传入 key 和 value，返回经过处理后的 value，如果 key 不存在计算时 value 则传入 null 进行计算。计算完成后，如果计算后的结果为 null 将删除 key，否则将更新或者新增 key。

新增 key 时采用的是头插法

public V compute(K key,
                 BiFunction remappingFunction) {
    if (remappingFunction == null)
        throw new NullPointerException();
    // hash处理
    int hash = hash(key);
    Node[] tab; Node first; int n, i;
    int binCount = 0;
    TreeNode t = null;
    Node old = null;
    // table如果未初始化则进行初始化
    if (size > threshold || (tab = table) == null ||
        (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 取得hash对应的下标
    if ((first = tab[i = (n - 1) & hash]) != null) {
        // 红黑树的方式查找值
        if (first instanceof TreeNode)
            old = (t = (TreeNode)first).getTreeNode(hash, key);
        else {
            Node e = first; K k;
            do {
                // 找到key相同的值退出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {
                    old = e;
                    break;
                }
                ++binCount;
            // 通过next引用向后查找
            } while ((e = e.next) != null);
        }
    }
    // 取得value
    V oldValue = (old == null) ? null : old.value;
    // 执行value计算
    V v = remappingFunction.apply(key, oldValue);
    // 原node不为null，表示key存在，更新或者删除node
    if (old != null) {
        if (v != null) {
            // 更新value
            old.value = v;
            // 后置处理
            afterNodeAccess(old);
        }
        else
            // 新value为null，删除node
            removeNode(hash, key, null, false, true);
    }
    // key不存在，但是处理后的value不为null，插入node
    else if (v != null) {
        if (t != null)
            // 红黑树的方式插入节点
            t.putTreeval(this, tab, hash, key, v);
        else {
            // 在链表前面插入node
            tab[i] = newNode(hash, key, v, first);
            // 转为红黑树
            if (binCount >= TREEIFY_THRESHOLD - 1)
                treeifyBin(tab, hash);
        }
        // 增加修改次数
        ++modCount;
        // 增加map大小
        ++size;
        // 后置处理
        afterNodeInsertion(true);
    }
    return v;
}

6.3 computeIfAbsent 值计算

与 compute 方法不同的是，computeIfAbsent 是专门针对空值的，原 key 不存在或对应的 value 为 null 才进行值计算，且值计算后的新 value 如果为 null 不会进行更新。

新增 key 时采用的是头插法

public V computeIfAbsent(K key,
                         Function mappingFunction) {
    if (mappingFunction == null)
        throw new NullPointerException();
    // 计算hash
    int hash = hash(key);
    Node[] tab; Node first; int n, i;
    int binCount = 0;
    TreeNode t = null;
    Node old = null;
    // table如果未初始化则进行初始化
    if (size > threshold || (tab = table) == null ||
        (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 取得hash对应的下标
    if ((first = tab[i = (n - 1) & hash]) != null) {
        // 红黑树的方式查找值
        if (first instanceof TreeNode)
            old = (t = (TreeNode)first).getTreeNode(hash, key);
        else {
            Node e = first; K k;
            do {
                // 找到key相同的值退出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {
                    old = e;
                    break;
                }
                ++binCount;
            // 通过next引用向后查找
            } while ((e = e.next) != null);
        }
        V oldValue;
    	// 原value不为null直接返回
        if (old != null && (oldValue = old.value) != null) {
            afterNodeAccess(old);
            return oldValue;
        }
    }
    // 执行value计算
    V v = mappingFunction.apply(key);
    // 计算后的值为空，直接返回
    if (v == null) {
        return null;
    } else if (old != null) {
        // 原node存在，但是value为null，直接替换value
        old.value = v;
        afterNodeAccess(old);
        return v;
    }
    else if (t != null)
        // 红黑树方式插入节点
        t.putTreeval(this, tab, hash, key, v);
    else {
        // 头插法插入节点
        tab[i] = newNode(hash, key, v, first);
        // 链表转红黑树
        if (binCount >= TREEIFY_THRESHOLD - 1)
            treeifyBin(tab, hash);
    }
    // 增加修改次数
    ++modCount;
    // 增加map大小
    ++size;
    // 后置处理
    afterNodeInsertion(true);
    return v;
}

6.4 computeIfPresent 值计算

与 compute 方法不同的是，computeIfPresent 是专门针对值存在的情况，原 key 存在且对应的 value 不为 null 才进行值计算，且值计算后的新 value 如果为 null 将会删除 key。

public V computeIfPresent(K key,
                          BiFunction remappingFunction) {
    if (remappingFunction == null)
        throw new NullPointerException();
    Node e; V oldValue;
    // 计算hash
    int hash = hash(key);
    // 查询找到key对应的node，找到value不为null
    if ((e = getNode(hash, key)) != null &&
        (oldValue = e.value) != null) {
        // 进行值处理
        V v = remappingFunction.apply(key, oldValue);
        // 处理后的新值不为null，进行更新
        if (v != null) {
            e.value = v;
            afterNodeAccess(e);
            return v;
        }
        else
            // 新值为null，进行node删除
            removeNode(hash, key, null, false, true);
    }
    return null;
}

6.5 merge 值合并

如果原先的 key 不存在，或对应的 value 为 null 则直接根据传入的 value 进行值替换，如果已经存在对应的 value 则通过 remappingFunction 接口实例进行值处理，处理后的值不为 null 则进行值更新，否则删除对应的值。

public V merge(K key, V value,
               BiFunction remappingFunction) {
    // value不允许为null
    if (value == null)
        throw new NullPointerException();
    if (remappingFunction == null)
        throw new NullPointerException();
    // 计算hash
    int hash = hash(key);
    Node[] tab; Node first; int n, i;
    int binCount = 0;
    TreeNode t = null;
    Node old = null;
    // table如果未初始化则进行初始化
    if (size > threshold || (tab = table) == null ||
        (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 查询找到key对应的node不为null
    if ((first = tab[i = (n - 1) & hash]) != null) {
        if (first instanceof TreeNode)
            // 红黑树方式查询node
            old = (t = (TreeNode)first).getTreeNode(hash, key);
        else {
            Node e = first; K k;
            do {
                // 找到key相同的值退出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {
                    old = e;
                    break;
                }
                ++binCount;
            // 通过next引用向后查找
            } while ((e = e.next) != null);
        }
    }
    // 查到到key已存在
    if (old != null) {
        V v;
        // 原value不为null，进行值计算
        if (old.value != null)
            v = remappingFunction.apply(old.value, value);
        else
            // 直接更新value
            v = value;
        // 新值不为空，进行值更新
        if (v != null) {
            old.value = v;
            afterNodeAccess(old);
        }
        else
            // 新值为null删除node
            removeNode(hash, key, null, false, true);
        return v;
    }
    if (value != null) {
        if (t != null)
            // 红黑树方式插入节点
            t.putTreeval(this, tab, hash, key, value);
        else {
            // 头插入节点
            tab[i] = newNode(hash, key, value, first);
            // 转换为红黑树
            if (binCount >= TREEIFY_THRESHOLD - 1)
                treeifyBin(tab, hash);
        }
        // 增加修改次数
        ++modCount;
        // 增加map大小
        ++size;
        afterNodeInsertion(true);
    }
    return value;
}