Java集合之HashMap类源码剖析

hulingF

2023-11-22

Java集合

Java集合之HashMap类源码剖析

一、HashMap类的简介

HashMap是基于哈希表的Map接口实现，此实现提供了所有可选的map操作，并允许null值和null键。HashMap类大致相当于Hashtable，只不过它是不同步的并且允许nulls。该类不保证映射的顺序，特别是它不保证顺序随着时间的推移保持不变。

HashMap实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中桶的数量，初始容量就是创建哈希表时的容量，负载因子是衡量哈希表在其容量自动增加之前允许达到的满度的指标。当哈希表中的条目数超过负载因子与当前容量的乘积时，哈希表将被重新哈希（即重建内部数据结构），使得哈希表的桶数大约为两倍。

作为一般规则，默认负载因子 (0.75) 在时间和空间成本之间提供了良好的权衡。较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括get和put）。在设置其初始容量时应考虑映射中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。如果要在HashMap实例中存储许多映射，那么创建一个足够大的容量将允许更有效地存储映射，而不是让它根据表的增长需要执行自动重新哈希（非常耗时的操作）。

请注意，此实现不是同步的。如果多个线程同时访问哈希表，并且至少有一个线程在结构上修改了该哈希表，则必须进行外部同步。（结构修改是添加或删除一个或多个映射的任何操作；仅更改与实例已包含的键关联的值不是结构修改。）这通常是通过在自然封装映射的某个对象上进行同步来完成的。如果不存在这样的对象，则应使用Collections.synchronizedMap方法“包装”映射。最好在创建时完成此操作，以防止意外地不同步访问Map：

1	Map m = Collections.synchronizedMap(new HashMap(...));

此类的所有“集合视图方法”返回的迭代器都是fail-fast的：如果在创建迭代器后的任何时间对哈希表进行结构修改，除了通过迭代器自己的删除方法之外的任何方式，迭代器都会抛出ConcurrentModificationException。因此，面对并发修改，迭代器会快速而干净地失败，而不是在未来不确定的时间冒任意、非确定性行为的风险。

二、HashMap类的底层结构

JDK8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK8以后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值（默认为8）（将链表转换成红黑树前会判断，如果当前数组的长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。HashMap 默认的初始化大小为 16，之后每次扩充，容量变为原来的2倍。并且，HashMap总是使用2的幂作为哈希表的大小。

三、HashMap类的常量字段

// 默认初始化容量，必须是2的幂次
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 哈希表的最大容量，准确说是table数组的最大长度
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;

上面定义的常量字段都是围绕哈希表的容量、负载因子和树化指标的，哈希表的默认初始化容量是16，默认负载因子是0.75，最大容量是2^30^，考虑链表长度增加会降低查找性能，因此如果链表长度超过8并且当前table数组长度不小于64(如果table数组长度还不足64的话，优先考虑数组扩容)，就进行链表的树化。

四、HashMap类的静态工具

hash方法计算key.hashCode()并将散列的高位扩展到低位做异或运算。由于哈希表大小始终是2的幂次，且最大为2^30^，因此仅在当前二进制位上方的位上变化的哈希集将始终发生冲突。因此，我们应用一种转换来向下分散较高位的影响。

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

tableSizeFor方法根据指定的cap参数计算该哈希表的容量，哈希表的容量就是散列数组table的长度，是大于等于cap值的最小2的幂次(当然，不能超出最大容量限制)。

static final int tableSizeFor(int cap) {
    // 1.cap容量参数的二进制表示类似于0b1xxxx...xx共n位,如果后面的xx不全为0,那么计算cap-1二进制的前导零位数是32-n,-1的二进制表示是1111...111共32位,无符号右移32-n位后的二进制数是0b1111...11共n位
    // 2.cap容量参数的二进制表示类似于0b1xxxx...xx共n位,如果后面的xx全为0,那么计算cap-1二进制的前导零位数是32-(n-1),-1的二进制表示是1111...111共32位,无符号右移32-(n-1)位后的二进制数是0b1111...11共n-1位
    // 3.如果计算后的num不超出最大容量限制,数组长度为num+1即2的幂次0b10000...00
    int num = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (num < 0) ? 1 : (num >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : num + 1;
}

计算哈希数组长度的逻辑就是计算大于等于cap的最小2的幂次方，具体方法是通过计算前导零位数+二进制移位实现，例如对于一个二进制n位的数字其前导零位数就是32-n，那么-1(二进制表示形式为全1)无符号右移32-n位得到低位为连续n位的1的数字，该数字加一后就是大于等于cap的最小2的幂次方。不过需要注意cap本身就是2的幂次方的情况，此时按照这种计算方式得不到最小的2幂次方，因此需要统一做cap-1的处理！

五、HashMap类的重要内部类

Node是继承自Map.Entry接口的静态内部类，是哈希表中最重要的基本内部类，封装了键的哈希值hash、键key、值value、Node的后继节点next这四个属性字段，并实现了Map.Entry接口的方法。

static class Node<K,V> implements Map.Entry<K,V> {
    // 键的哈希值，由键的hashCode经过扰动得到的冲突更少、分布更均匀的哈希值
    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 V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    /**
     * 下面的hashCode和equals方法就是经典的重写方式，非常规范，两个方法中都使用了且仅使用了key和value字段
     */
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    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类的重要字段

// 散列数组即哈希表的主体结构，会延迟初始化，并在需要时扩容，其长度保持为2的幂次
transient Node<K,V>[] table;
// 实际键值对的数量
transient int size;
// 结构性修改次数，描述Map的数量变化或扩容等操作的次数，在迭代器的快速失败机制会使用到
transient int modCount;
// 下一次扩容的阈值，等于哈希表容量*负载因子
int threshold;
// 负载因子，基本不需要改变
final float loadFactor;

HashMap主体就是一个散列数组，其中数组的每个元素都可能是一个单链表或红黑树，HashMap中最重要的两个字段就是扩容阈值和负载因子，而且需要注意：出于性能考虑散列数组推迟到第一次使用时才会初始化，这种延迟初始化的思想很多地方都会使用到，如操作系统的写时复制、Spring中Bean对象的懒加载、MyBatis中分步查询的懒加载、AQS同步队列的延迟初始化等等。

七、HashMap类的构造方法

HashMap类的构造方法有四个，首先前两个属于同一种情况，只是简单的复用：

// 这个构造函数我们基本不怎么使用，因为负载因子使用默认的即可
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);
}

不过，我们最常用的还是HashMap的无参构造函数，构造的HashMap实例拥有默认初始容量16和默认负载因子0.75，在后面resize方法进行哈希表初始化时会看到通过无参构造函数创建的HashMap对象的threshold为0，初始化散列数组时长度为默认初始化容量16。

1
2
3

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

最后，我们也不得不提拷贝构造函数，其负载因子为默认的0.75，初始容量足以容纳Map对象的所有映射键值对，其中putMapEntries的逻辑需要等最后才说。

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

八、HashMap类的put方法

首先看一下JDK注释：插入指定的键值对，如果键已经存在，则用新值更新与之关联的旧值。返回与键关联的旧值，如果不存在则返回null(注意，null同时也能表明与键关联的值就是null值，这在HashMap中是允许的)。

下面，我们重点关注putVal方法的逻辑：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 散列数组未初始化，需要先初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 1.键关联的散列数组桶位为null，可以直接就地放置该键值对的Node节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // e为哈希表中找到的键匹配的Node节点，直接更新即可
        Node<K,V> e; K k;
        // 2.桶位对应的链表或红黑树的第一个元素的键与传入的键匹配，更新e表示已找到匹配Node
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 3.桶位对应于一颗红黑树，则从红黑树中寻找匹配Node并更新e
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 4.桶位对应于一个单链表，则从单链表中寻找匹配Node并更新e
        else {
            // p表示当前节点e的父节点，用于单链表添加时充当尾节点
            for (int binCount = 0; ; ++binCount) {
                // 5.到达链表末尾，表明链表中不存在键匹配的Node
                if ((e = p.next) == null) {
                    // 链表中没有键匹配的Node，需要在链表末尾后新添加一个Node
                    p.next = newNode(hash, key, value, null);
                    // 链表长度>树化阈值8时需要转换成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        treeifyBin(tab, hash);
                    break;
                }
                // 链表遍历过程中找到键匹配的Node，直接退出，其中e为匹配Node
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 父节点后移，链表继续向后遍历
                p = e;
            }
        }
        // 根据前面e的定义，表明找到了键匹配的Node，更新其value字段即可
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 如果onlyIfAbsent为true，对于已存在的键值对(值不能为null)不会覆盖更新
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 扩展处理逻辑，LinkedHashMap中有所体现
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构修改次数递增，更新Node不算做结构性修改
    ++modCount;
    // 哈希表中映射键值对数量超过扩容阈值，则进行扩容操作
    if (++size > threshold)
        resize();
    // 扩展处理逻辑，LinkedHashMap中有所体现
    afterNodeInsertion(evict);
    return null;
}

需要关注的是，哈希表的初始化过程会延迟到第一次调用put方法时，对于哈希表中不存在键匹配的Node的情况，需要往桶位链表末尾添加新键值对Node，并且可能会树化(链表长度达到9且散列数组长度不小于64)；对于哈希表中存在键匹配的Node的情况，需要根据onlyIfAbsent参数决定是否覆盖更新。

九、HashMap类的resize方法

resize方法内处理初始化逻辑和哈希表扩容逻辑，扩容策略是在不超过最大容量限制的情况下直接扩容为原来的两倍，当散列数组的长度达到最大容量限制时无法再继续扩容，设置扩容阈值为Integer.MAX_VALUE。对于扩容逻辑，哈希表需要Rehash运算：

final Node<K,V>[] resize() {
    // 旧散列数组
    Node<K,V>[] oldTab = table;
    // 旧散列数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 旧扩容阈值(通过无参构造函数创建的哈希表对象的threshold初始为0,通过指定容量的构造函数创建的哈希表对象的threshold初始为预存的散列数组的长度)
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 散列数组已经初始化：
    if (oldCap > 0) {
        // 情况1.散列数组的长度已经达到最大容量限制，无法再继续扩容，修改扩容阈值为Integer.MAX_VALUE并直接返回旧散列数组
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 情况2：散列数组的长度还没有达到最大容量限制，可以直接两倍扩容
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 扩容后的散列数组还没有达到最大容量限制，并且旧散列数组的长度大于等于16，扩容阈值也随之两倍增大
            newThr = oldThr << 1; // double threshold
    }
    // 散列数组还未初始化：
    // 情况3.使用指定容量的有参构造函数创建的哈希表实例，其扩容阈值threshold预存了散列数组的长度，因此直接赋值给newCap
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 情况4.使用无参构造函数创建的哈希表实例，初始化容量为默认容量16，负载因子为16*0.75=12
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 一旦扩容后的散列数组长度达到最大容量限制，扩容阈值需要变为Integer.MAX_VALUE，否则使用计算公式newCap * loadFactor
    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;
    
    // 重新rehash的过程，分为两种情况：低位保持和高位扩散
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 进行链表或红黑树的遍历，重新rehash运算
            if ((e = oldTab[j]) != null) {
                // help GC
                oldTab[j] = null;
                // 单个Node节点直接rehash
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 红黑树的rehash
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 单链表的rehash
                else { // preserve order
                    // 低位保持的Node链表
                    Node<K,V> loHead = null, loTail = null;
                    // 高位扩散的Node链表
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍历单链表，构造低位保持的Node链表和高位扩散的Node链表
                    do {
                        next = e.next;
                        // 低位保持的Node节点的情况：
                        if ((e.hash & oldCap) == 0) {
                            // 更新维护低位保持的Node链表的首尾节点
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 高位扩散的Node节点的情况：
                        else {
                            // 更新维护高位扩散的Node链表的首尾节点
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 低位保持的Node链表不为空，直接放置在新散列数组的原位置
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 高位扩散的Node链表不为空，需要放置在新散列数组的[原位置后移原散列数组长度的位置处]
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

十、HashMap类的get方法

重点的还是getNode方法，根据键的哈希值和键查找对应的值：

final Node<K,V> getNode(int hash, Object key) {
    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) {
        // 首节点就是查找的目标节点，直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 桶位的红黑树或链表长度大于1，需要遍历查找
        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);
        }
    }
    // 找不到符合的目标节点，返回null值
    return null;
}

十一、HashMap类的remove方法

重点的还是removeNode方法，

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表示待删除的目标节点
        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);
            }
        }
        // 找到待删除的目标节点且其中的value值匹配
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 红黑树删除目标节点
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 首节点就是待删除的节点
            else if (node == p)
                tab[index] = node.next;
            // 删除链表中的目标节点，其中p是父节点
            else
                p.next = node.next;
            // 结构修改次数递增
            ++modCount;
            // 哈希表中映射键值对数量递减
            --size;
            // 扩展处理逻辑，LinkedHashMap中有所体现
            afterNodeRemoval(node);
            // 返回待删除的节点
            return node;
        }
    }
    // 不存在待删除的目标节点，直接返回null
    return null;
}

十二、HashMap类的entrySet方法

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    // 返回HashMap的键值对集合，是Map的键值对的Set视图封装，因此两者的修改会互相影响彼此
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public final int size()                 { return size; } // 返回Map中键值对个数
    public final void clear()               { HashMap.this.clear(); } // 清空Map结构
    public final Iterator<Map.Entry<K,V>> iterator() {
        // 返回entrySet迭代器
        return new EntryIterator();
    }
    // 查看是否包含给定的键值对
    public final boolean contains(Object o) {
        // 首先查看传入的对象是不是Map.Entry及其子类
        if (!(o instanceof Map.Entry))
            return false;
        // 根据Entry的Key和Hash值查找键值对节点
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;
        Object key = e.getKey();
        Node<K,V> candidate = getNode(hash(key), key);
        // 返回查找结果
        return candidate != null && candidate.equals(e);
    }
    // 删除给定的键值对
    public final boolean remove(Object o) {
        // 首先查看传入的对象是不是Map.Entry及其子类
        if (o instanceof Map.Entry) {
            // 根据Entry的Key和Hash值删除键值对节点
            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;
    }
	// 遍历Map中的所有键值对
    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();
        }
    }
}

根据上面的代码可知，entrySet方法返回的Set集合直接操作的是关联的Map对象，我们重点看一下entrySet迭代器的实现：

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        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<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        removeNode(p.hash, p.key, null, false, false);
        expectedModCount = modCount;
    }
}

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

可见，HashMap的EntryIterator遍历的顺序是散列数组从前往后，其中散列数组每个元素对应的单链表也是从前往后。

十三、HashMap类的其他方法

十四、HashMap类的一点小补充

HashMap的字段中出现了一个Java关键字transient，它有什么作用嘞？

首先，transient修饰的字段不参与序列化，因为HashMap内部的散列数组可能存在未使用的桶位，没有被使用到的空间被序列化没有意义，所以需要手动使用 writeObject() 方法，只序列化实际存储元素。

更重要的是，HashMap的底层是一些包含“键值”项的散列桶数组，到底一个项（key）被放在哪个桶中，这是该键的hashCode确定的(准确说是经过扰动的hash值)，一般情况下，不同的JVM实现不保证会有相同的hashCode。实际上，即使是相同的JVM实现中，也无法保证每次运行都一样。因此，对于HashMap而言，接受默认的序列化形式将会导致一个严重的bug：对HashMap对象进行序列化和反序列化操作所产生的的对象，其约束关系会遭到严重的破坏。

实际上，HashMap的序列化与反序列化都是使用writeObject和readObject完成的，其中readObject方法会针对每一个Entry调用putVal重新从头构建HashMap对象，因为hashCode不能保证与序列化前的一致。

HashMap存在线程安全问题吗？

毫无疑问，HashMap就是线程不安全的，因为内部没有使用任何同步措施如synchronized、CAS等等，举例来说：当HashMap进行扩容时，其实就是把旧散列表中每个桶位的元素(链表或红黑树)做ReHash操作到新散列表中，如果在这个过程中新插入一个Entry或删除了一个Entry，并且这个Entry所在的散列表桶位已经完成了同步迁移，那么这次的修改就无法同步到新散列表中，由此产生了线程安全问题！