JDK1.8HashMap源码分析

概要

HashMap允许key为null,value为null，由于是hash存放，所以遍历时无序。

底层的数组称为哈希桶，每个桶（数组元素）存放的是链表，链表中每个结点就是哈希表的元素

在JDK8中，当链表长度达到8，会转化成红黑树，以提升它的查询、插入效率，它实现了Map<K,V>, Cloneable, Serializable接口。

因其底层哈希桶的数据结构是数组，所以也会涉及到扩容的问题。

当HashMap的容量达到threshold阈值时，就会触发扩容。扩容前后，哈希桶的长度一定会是2的n次方。这样在根据key的hash值寻找对应的哈希桶时，可以用位运算替代取余操作，更加高效。

而key的hash值，并不仅仅只是key对象的hashCode()方法的返回值，还会经过扰动函数的扰动，以使hash值更加均衡。因为hashCode()是int类型，取值范围是40多亿，只要哈希函数映射的比较均匀松散，碰撞几率是很小的。但就算原本的hashCode()取得很好，每个key的hashCode()不同，但是由于HashMap的哈希桶的长度远比hash取值范围小，默认是16，所以当对hash值以桶的长度取余，以找到存放该key的桶的下标时，由于取余是通过与操作完成的，会忽略hash值的高位。因此只有hashCode()的低位参加运算，产生不同的hash值，但是得到的index相同的情况的几率会大大增加，这种情况称之为hash碰撞。即，碰撞率会增大。

扰动函数就是为了解决hash碰撞的。它会综合hash值高位和低位的特征，并存放在低位，因此在与运算时，相当于高低位一起参与了运算，以减少hash碰撞的概率。（在JDK8之前，扰动函数会扰动四次，JDK8简化了这个操作）

扩容操作时，会new一个新的Node数组作为哈希桶，然后将原哈希表中的所有数据(Node节点)移动到新的哈希桶中，相当于对原哈希表中所有的数据重新做了一个put操作。所以性能消耗很大，可想而知，在哈希表的容量越大时，性能消耗越明显。

扩容时，如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置。因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位，或者扩容后的下标，即high位。 high位= low位+原哈希桶容量 如果追加节点后，链表数量>=8，则转化为红黑树

由迭代器的实现可以看出，遍历HashMap时，顺序是按照哈希桶从低到高，链表从前往后，依次遍历的。属于无序集合。

HashMap的源码中，充斥个各种位运算代替常规运算的地方，以提升效率： * 与运算替代模运算。用 hash & (table.length-1) 替代 hash % (table.length) * 用if ((e.hash & oldCap) == 0)判断扩容后，节点e处于低区还是高区。

本文部分图片来源于网络，侵删。

JDK1.7的HashMap

jdk1.7的hashmap采用数组+链表的数据结构，对于Hash碰撞冲突的解决方法采用的是链表头插移动法。

JDK1.7与JDK1.8HashMap的区别：

1.7是数组+链表，1.8则是数组+链表+红黑树结构

jdk1.7中当哈希表为空时，会先调用inflateTable()初始化一个数组；而1.8则是直接调用resize()扩容;

插入键值对的put方法的区别，1.8中采用尾插法，而1.7中是采用头插法；

jdk1.7中的hash函数对哈希值的计算直接使用key的hashCode值，而1.8中则是采用key的hashCode异或上key的hashCode进行无符号右移16位的结果，避免了只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，使元素分布更均匀；

扩容时1.8会保持原链表的顺序，而1.7会颠倒链表的顺序；而且1.8是在元素插入后检测是否需要扩容，1.7则是在元素插入前；

扩容策略：1.7中是只要不小于阈值就直接扩容2倍；而1.8的扩容策略会更优化，当数组容量未达到64时，以2倍进行扩容，超过64之后若桶中元素个数不小于7就将链表转换为红黑树，但如果红黑树中的元素个数小于6就会还原为链表，当红黑树中元素不小于32的时候才会再次扩容。

JDK1.8的HashMap

JDK1.8采用的是数组+链表+红黑树

Map的实际数量=threshold容量阈值时，会进行两倍扩容
Map中某个桶的链表长度大于树形化阈值TREEIFY_THRESHOLD=8，但Map元素数量小于树形化最小容量MIN_TREEIFY_CAPACITY=64时，会进行两倍扩容（不会转化为红黑树）
Map中某个桶链表长度大于树形化阈值TREEIFY_THRESHOLD=8，且Map元素数量大于树形化最小容量MIN_TREEIFY_CAPACITY=64时，会将链表转化为红黑树。

结构认识

HashMap仅仅实现了常规的Serializable、Cloneable、Map等接口，继承了AbstractMap抽象类。

可以看到里面的字段非常多，我们稍后一一探讨。

源码解析

我们还是按照我们字段解释->构造函数解释->主要方法解释的流程来进行。主要内容基本都在代码注释里，重点看注释！！！

字段解释

HashMap里面的字段很多，包括各种阈值以及Map的属性。每个字段上面都有英文注释，可以帮助我们很好地去理解。

// 默认初始化容量：16，必须为2的n次方。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// Map最大容量：2^30=10 7374 1824.(为什么是2^30?，因为int一共32位，最高位为符号位，所以1只能最多左移30位)
static final int MAXIMUM_CAPACITY = 1 << 30;

// 负载因子：现存元素/容量>DEFAULT_LOAD_FACTOR就进行扩容。（为什么是0.75？因为太小会导致空间浪费，太大导致提高查找成本。0.75是一个时间和空间上的一个折中，也是通过一些数学方法计算和统计出来的）
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转红黑树阈值, 9个节点开始转
static final int TREEIFY_THRESHOLD = 8;

// 红黑树转链表的阈值，6个结点开始转
static final int UNTREEIFY_THRESHOLD = 6;

// 转红黑树时, table（数组）的最小长度
static final int MIN_TREEIFY_CAPACITY = 64;
// 哈希桶数组
transient Node<K,V>[] table;
// 用来存放缓存
transient Set<Map.Entry<K,V>> entrySet;
// 元素数量
transient int size;

// modifyCount：修改次数，判断并发修改异常
transient int modCount;

// 扩容的阈值，threshold = capacity * load factor （容量*负载因子)
int threshold;

存储数据元素是用Node来存储，包含了hash值、key、value、next指针。

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

构造函数解释

了解了基本的字段意义后我们来看看HashMap的构造函数。HashMap有4个构造函数

// 自行指定初始容量和负载因子
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);
}
// 自行执行初始容量，负载因子默认0.75
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 使用默认初始容量和负载因子
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

// 将另一个哈希表m加到该哈希表中
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

无论是创建哈希表还是ArrayList，初始时能够手动指定大小就尽量手动指定大小。

主要方法解释

先看一些比较重要的方法，非接口方法。

计算hash值（key的hashcode无符号右移16位后，跟原来的hashcode做异或运算）

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

我们看一个例子

右移16位相当于把高16位移到低16位，高16位置为0，跟原来的hashcode异或后，结果高16位保持不变，低16位等于原来的高16位与低16位进行异或。

即异或后高16位没有变，只是低16位变了。

为什么要这么做呢？

我们要知道这个函数的目的是计算出散列更均匀、碰撞几率更小的hash值，所以这样做能够达到较好的效果。为什么能达到这样的效果？

计算出来的hash值会用于计算元素存储的桶位，计算公式为(capacity - 1) & hash，如果数组现在有16个桶位（槽位slot），那么计算后结果如下：

发现了吗？数组容量为16时，高16位全部为0！如果我们不将原来的hashcode右移16位，那么hashcode高16位就完全没有参与计算，相当于完全被抛弃了。只采用低16位进行计算产生Hash冲突的概率就会增加很多！

到这里也可以理解为什么容量必须是2的n次方了。因为2^n - 1可以保证产生最多的1，从而计算槽位时可以保证尽量根据hashcode的不同而均匀地散列。如果非2^n，那么会导致0非常多或者1非常多，结果也就会趋于0或着最大值，这样产生hash冲突的概率会非常大！

根据期望容量cap，返回2的n次方形式的哈希桶的实际容量length。返回值一般会>=cap

如传入10，计算后返回16，表示数组的长度应该为16.即计算与期望容量相等或稍大的2的n次方

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

将另一个Map的所有元素加入表中，参数evict初始化时为false，其他情况为true

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            // 根据m的元素数量和当前表的加载因子，计算出阈值
            float ft = ((float)s / loadFactor) + 1.0F;
            // 修正阈值的边界 不能超过MAXIMUM_CAPACITY
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // 如果新的阈值大于当前阈值，重置为计算后2的n次方阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 如果m的大小大于阈值，进行扩容
        else if (s > threshold)
            resize();
        // 遍历 m 依次将元素加入当前哈希表中。
        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);
        }
    }
}

扩容函数resize()！！重点！！

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 如果旧容量大于最大容量，无法扩容，返回旧数组。
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 新容量=旧容量*2，如果新容量未超过最大容量且旧容量大于等于初始容量（已经初始化过旧容量）
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 新阈值=旧阈值*2
            newThr = oldThr << 1; // double threshold
    }
    // 如果当前表是空的，但是有阈值。代表是初始化时指定了容量、阈值的情况
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 新容量=旧阈值
        newCap = oldThr;
    // 如果当前表是空的，而且也没有阈值。代表是初始化时没有任何容量/阈值参数的情况 
    else {               // zero initial threshold signifies using defaults
        // 初始化哈希表
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新阈值是0，对应的是当前表是空的，但是有阈值的情况
    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;
            if ((e = oldTab[j]) != null) {
                // 显示将旧哈希表元素置为null，提醒GC
                oldTab[j] = null;
                if (e.next == null)
                    // 重新计算新表哈希值并赋值
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果发生过哈希碰撞 ,而且是节点数超过8个，转化成了红黑树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    //因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位， 或者扩容后的下标，即high位。 high位=  low位+原哈希桶容量
                    // 低位链表的头、尾结点
                    Node<K,V> loHead = null, loTail = null;
                    // 高位链表的头、尾结点
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // //这里又是一个利用位运算代替常规运算的高效点： 利用哈希值 与 旧的容量相与，可以得到哈希值去模后，是大于等于oldCap还是小于oldCap，等于0代表小于oldCap，应该存放在低位，否则存放在高位
                        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);
                    // 将低位链表存放在原index处
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 将高位链表存放在新index处
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

扩容方法比较复杂，其中比较复杂的地方在于将旧链表拆分成两条新的链表，通过 e.hash & oldCap 来计算新链表在扩容后的数组中的新下标。当 e.hash & oldCap = 0，则节点在新数组中的索引值与旧索引值相同。当e.hash & oldCap = 1，则节点在新数组中的索引值为旧索引值+旧数组容量。

为什么可以用位运算代替取模运算呢？

可以推导出e.hash & (capacity - 1) = e.hash % capacity，具体推导可以查看博客

HashMap 中的取模和扩容公式推导_Sumkor的博客-CSDN博客_hashmap 取模

为什么结果为0的时候与旧索引值相同，而结果为1则不同呢？

假设原来哈希值为15即1111，由于容量翻倍，哈希值位数也增加一位，所以重新计算，如果下图中b位为0，那么计算出来的新哈希值为01111，哈希值不变。如果b位为1，计算出来的新哈希值为11111即31，刚好等于旧索引值(15)+旧数组容量(16)。

步骤总结如下：

根据旧容量和旧阈值计算新容量和新阈值。
创建新哈希表，对旧哈希表进行遍历
如果元素不为null，重新计算元素的哈希值，存放到新哈希表中（低位链表和高位链表）
如果发生哈希冲突，且结点超过8个，转化为红黑树
返回新哈希表

putVal()，！！重点！！ onlyIfAbsent=true表示不会覆盖已存在key的value，evict=false表示在初始化时调用。

public V put(K key, V value) {
    // put操作会覆盖相同key的value
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // tab：当前哈希桶，p：临时链表结点
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果哈希表为空，那么就初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // index是 哈希值 & 哈希桶的长度-1得到的，如果该处index没有元素，直接赋值进去
    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;
                }
                // 找到了要覆盖的结点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果e不为null，说明有需要覆盖的结点
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                // 允许覆盖则覆盖
                e.value = value;
            // 这是一个空函数，用作LinkedHashMap重写使用
            afterNodeAccess(e);
            // 返回原值
            return oldValue;
        }
    }
    // 如果执行到此说明已经插入了一个新的结点
    ++modCount;
    // 更新size，判断是否需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

网上看到一张put操作的流程图，觉得很清晰，放在下面

如果觉得看不明白还有一张，侵删

情况总结如下：

如果对应桶位置为空，直接插入
如果对应桶位置存在元素，发生哈希冲突
- 如果存在相同key，不需要新插入，直接覆盖
- 如果不存在相同key，判断是否为树结点
  - 如果非红黑树结构，插到链表尾部，插入后如果长度大于8，转为红黑树
  - 如果为红黑树结构，插入到红黑树

put操作至此应该解读得比较清晰了

删除元素remove()，matchValue=false：不要求必须key、value都相等才可删除，movable=true：删除元素后，可以移动其他结点

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

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 {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

remove操作也有一张流程图：

按照流程图可以对照源码进行研究。

get()查询元素

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 哈希表不为空，且根据key计算的的hash值然后计算的索引处的元素不为空。
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // first表示对应哈希桶的第一个Entry
        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;
}

流程图如下：

jdk1.8新增方法

以key为条件，找到了返回value。否则返回defaultValue

@Override
public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}

entrySet缓存

我们用EntrySet一般是为了获取Iterator

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }

    public final Iterator<Map.Entry<K,V>> iterator() {
        return new EntryIterator();
    }
    // 最终还是调用getNode()
    public final boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;
        Object key = e.getKey();
        Node<K,V> candidate = getNode(hash(key), key);
        return candidate != null && candidate.equals(e);
    }
    // 最终还是调用removeNode()
    public final boolean remove(Object o) {
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Object value = e.getValue();
            return removeNode(hash(key), key, value, true, true) != null;
        }
        return false;
    }
    public final Spliterator<Map.Entry<K,V>> spliterator() {
        return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (Node<K,V> e : tab) {
                for (; e != null; e = e.next)
                    action.accept(e);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

另外HashMap还提供了很多迭代器，Splitearot：可分割迭代器，为了并行遍历数据源中的元素而设计的迭代器，这个可以类比最早Java提供的顺序遍历迭代器Iterator，但一个是顺序遍历，一个是并行遍历。

为什么有了Iterator还要Spliterator呢？

从最早Java提供顺序遍历迭代器Iterator时，那个时候还是单核时代，但现在多核时代下，顺序遍历已经不能满足需求了，如何把多个任务分配到不同核上并行执行，才是能最大发挥多核的能力，所以产生了Spliterator

补充

HashMap和HashTable的区别

与之相比HashTable是线程安全的，且不允许key、value是null。
HashTable默认容量是11。
HashTable是直接使用key的hashCode(key.hashCode())作为hash值，不像HashMap内部使用static final int hash(Object key)扰动函数对key的hashCode进行扰动后作为hash值。
HashTable取哈希桶下标是直接用模运算%.（因为其默认容量也不是2的n次方。所以也无法用位运算替代模运算）
扩容时，新容量是原来的2倍+1。int newCapacity = (oldCapacity << 1) + 1;
Hashtable是Dictionary的子类同时也实现了Map接口，HashMap是Map接口的一个实现类；

小结

文中关于红黑树的具体操作部分没有展开描述，具体想了解的读者可自行查阅资料。

阅读HashMap源码的过程中不仅仅学习到了大佬代码的思考，更有一种亲身体会大佬们在设计和实现这些想法时候的取舍。对于我来说源码阅读能力自我感觉也有一定提升，当然还有一些细节部分没有具体去探究，只求能将学习到的知识进行内化固化就可！

源码分析

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

MySQL高级（索引、查询优化、主从复制）上一篇

Docker 学习笔记下一篇

HashMap源码通俗解读