HashMap源码分析（基于JDK1.6）

HashMap 源码分析（基于 JDK 1.6）

编者注：本文为历史博文归档，主要基于 JDK 1.6 版本源码进行分析。涉及 JDK、框架与工具链版本请以当前官方文档为准。引用外链图片可能失效，阅读时请注意时效性。

在 Java 集合类中，除了 ArrayList 之外，最常用的莫过于 HashMap 了。本文旨在尽可能详细地解析 HashMap 的源码实现。水平有限，若有不足之处，欢迎指正，定当及时修正。

在深入 HashMap 源码之前，我们先简要复习一下相关的数据结构。

数据结构基础

Java 最基本的数据结构包括数组（Array）和链表（Linked List）。

数组：空间连续（大小固定）、寻址迅速。但插入和删除时需要移动元素，因此查询快，增删慢。
链表：可动态增加或减少空间以适应元素变化。但查找时只能顺着节点逐个查找，因此增删快，查询慢。

有没有一种结构能综合数组和链表的优点呢？当然有，那就是哈希表（Hash Table）。虽然说是综合优点，但实际上查找速度肯定没有数组快，插入删除也没有链表快，这是一种折中的方案。哈希表一般采用拉链法（Chaining）实现。

（图片源自网络，多处文章均有引用，因无法确认出处未申明作者）

计算机相关专业通常都会学习这些内容，此处不再赘述。铺垫了数组、链表、哈希表和拉链法，接下来进入正题：我们在什么时候用到了这些内容？具体是如何实现的？

其实我们一直在使用（想必大家对 HashMap 都不陌生），可能未曾深究其内部实现。下面主要分析 HashMap 的源码。

类定义与继承结构

HashMap 继承自 AbstractMap，实现了 Map 接口（相关内容可参考《Java 集合类》）。类的定义如下：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

Map 接口定义了所有 Map 子类必须实现的方法。Map 接口中还定义了一个内部接口 Entry（为何设计成内部接口值得探讨，此处暂不展开），Entry 将在后文详细介绍。

AbstractMap 也实现了 Map 接口，并且提供了两个实现 Entry 的内部类：SimpleEntry 和 SimpleImmutableEntry。

定义了接口，接口中又有内部接口，然后有抽象类实现接口，抽象类里面又有内部类实现接口的内部接口，结构略显复杂。暂且不管设计缘由，先看 HashMap 的具体实现。

核心属性

HashMap 中定义的关键属性如下（部分注释为原文保留）：

/**
 * 默认的初始容量，必须是 2 的幂。
 */
static final int DEFAULT_INITIAL_CAPACITY = 16;

/**
 * 最大容量（必须是 2 的幂且小于 2 的 30 次方，传入容量过大将被这个值替换）
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认装载因子，后面会做解释
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 存储数据的 Entry 数组，长度是 2 的幂。
 * 看到数组的内容了，接着看数组中存的内容就明白为什么博文开头先复习数据结构了
 */
transient Entry[] table;

/**
 * map 中保存的键值对的数量
 */
transient int size;

/**
 * 需要调整大小的极限值（容量 * 装载因子）
 */
int threshold;

/**
 * 装载因子
 */
final float loadFactor;

/**
 * map 结构被改变的次数
 */
transient volatile int modCount;

构造方法

接着是 HashMap 的构造方法：

/**
 * 使用默认的容量及装载因子构造一个空的 HashMap
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); // 计算下次需要调整大小的极限值
    table = new Entry[DEFAULT_INITIAL_CAPACITY]; // 根据默认容量（16）初始化 table
    init();
}

/**
 * 根据给定的初始容量和装载因子创建一个空的 HashMap
 * 初始容量小于 0 或装载因子小于等于 0 将报异常 
 */
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);
    
    int capacity = 1;
    // 设置 capacity 为大于 initialCapacity 且是 2 的幂的最小值
    while (capacity < initialCapacity)
        capacity <<= 1;
    
    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
    table = new Entry[capacity];
    init();
}

/**
 * 根据指定容量创建一个空的 HashMap
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR); // 调用上面的构造方法，容量为指定的容量，装载因子是默认值
}

/**
 * 通过传入的 map 创建一个 HashMap
 * 容量为默认容量（16）和 (map.size()/DEFAULT_LOAD_FACTOR)+1 的较大者，装载因子为默认值
 */
public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    putAllForCreate(m);
}

上述构造方法中调用到了 init() 方法，最后一个方法还调用了 putAllForCreate(Map<? extends K, ? extends V> m)。

init() 方法是一个空方法，里面没有任何内容（留给子类重写）。
putAllForCreate 看方法名可知，是在创建时将传入的 map 全部放入新创建的对象中。该方法涉及的其他逻辑将在后面介绍。

内部类 Entry

初始化 table 时均使用了 Entry，这是 HashMap 的一个内部类，实现了 Map 接口的内部接口 Entry。

Map.Entry 接口定义的方法：

K getKey(); // 获取 Key
V getValue(); // 获取 Value
V setValue(); // 设置 Value，至于具体返回什么要看具体实现
boolean equals(Object o); // 定义 equals 方法用于判断两个 Entry 是否相同
int hashCode(); // 定义获取 hashCode 的方法

HashMap.Entry 类的具体实现：

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next; // 对下一个节点的引用（看到链表的内容，结合定义的 Entry 数组，是不是想到了哈希表的拉链法实现？！）
    final int hash; // 哈希值

    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue; // 返回的是之前的 Value
    }

    public final boolean equals(Object o) {
        if (!(o instanceof Map.Entry)) // 先判断类型是否一致
            return false;
        Map.Entry e = (Map.Entry)o;
        Object k1 = getKey();
        Object k2 = e.getKey();
        // Key 相等且 Value 相等则两个 Entry 相等
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {
            Object v1 = getValue();
            Object v2 = e.getValue();
            if (v1 == v2 || (v1 != null && v1.equals(v2)))
                return true;
        }
        return false;
    }

    // hashCode 是 Key 的 hashCode 和 Value 的 hashCode 的异或的结果
    public final int hashCode() {
        return (key == null ? 0 : key.hashCode()) ^
               (value == null ? 0 : value.hashCode());
    }

    // 重写 toString 方法，使输出更清晰
    public final String toString() {
        return getKey() + "=" + getValue();
    }

    /**
     * 当调用 put(k,v) 方法存入键值对时，如果 k 已经存在，则该方法被调用
     */
    void recordAccess(HashMap<K,V> m) {
    }

    /**
     * 当 Entry 被从 HashMap 中移除时被调用
     */
    void recordRemoval(HashMap<K,V> m) {
    }
}

核心方法分析

看完属性和构造方法，接着分析 HashMap 中的其他方法。从最常用的 put 和 get 说起。

put() 方法

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> 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;
}

当存入的 key 是 null 的时候将调用 putForNullKey 方法，暂时将这段逻辑放一边，先看 key 不为 null 的情况。

先调用 hash(int h) 方法获取了一个 hash 值。

static int hash(int h) {
    // 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);
}

这个方法的主要作用是防止质量较差的哈希函数带来过多的冲突（碰撞）问题。Java 中 int 值占 4 个字节，即 32 位。根据这 32 位值进行移位、异或运算得到一个值。

计算索引位置。

static int indexFor(int h, int length) {
    return h & (length - 1);
}

indexFor 返回 hash 值和 table 数组长度减 1 的与运算结果。为什么使用的是 length-1？因为这样可以保证结果的最大值是 length-1，不会产生数组越界问题（前提是 length 为 2 的幂）。

获取索引位置之后做了什么？探测 table[i] 所在的链表，若发现 key 值与传入的 key 值相同的对象，则替换并返回 oldValue。若找不到，则通过 addEntry(hash, key, value, i) 添加新的对象。

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

这就是在一个链表头部插入一个节点的过程。获取 table[i] 的对象 e，将 table[i] 的对象修改为新增对象，让新增对象的 next 指向 e。之后判断 size 是否到达了需要扩充 table 数组容量的界限并让 size 自增 1，如果达到了则调用 resize(int capacity) 方法将数组容量拓展为原来的两倍。

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    // 这个 if 块表明，如果容量已经到达允许的最大值，即 MAXIMUM_CAPACITY，则不再拓展容量
    // 而将装载拓展的界限值设为计算机允许的最大值。不会再触发 resize 方法
    // 而是不断的向 map 中添加内容，即 table 数组中的链表可以不断变长，但数组长度不再改变
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    // 创建新数组，容量为指定的容量
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    // 设置下一次需要调整数组大小的界限
    threshold = (int)(newCapacity * loadFactor);
}

结合上面给出的注释，调整数组容量的内容仅剩下将原 table 中的内容复制到 newTable 中并将 newTable 返回给原 table。即上面代码中的 transfer(newTable); table = newTable;。来看 transfer(Entry[] newTable) 方法。

void transfer(Entry[] newTable) {
    // 保留原数组的引用到 src 中
    Entry[] src = table;
    // 新容量是新数组的长度
    int newCapacity = newTable.length;
    // 遍历原数组
    for (int j = 0; j < src.length; j++) {
        // 获取元素 e
        Entry<K,V> e = src[j];
        if (e != null) {
            // 将原数组中的元素置为 null
            src[j] = null;
            // 遍历原数组中 j 位置指向的链表
            do {
                Entry<K,V> next = e.next;
                // 根据新的容量计算 e 在新数组中的位置
                int i = indexFor(e.hash, newCapacity);
                // 将 e 插入到 newTable[i] 指向的链表的头部
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

从上面的代码可以看出，HashMap 之所以不能保持元素的顺序有以下几点原因：

插入元素的时候对元素进行哈希处理，不同元素分配到 table 的不同位置；
容量拓展的时候又进行了 hash 处理；
复制原表内容的时候链表被倒置。

一个 put 方法带出了这么多内容，接着看看 putAll 吧。

public void putAll(Map<? extends K, ? extends V> m) {
    int numKeysToBeAdded = m.size();
    if (numKeysToBeAdded == 0)
        return;
    // 为什么判断条件是 numKeysToBeAdded，不是 (numKeysToBeAdded+table.length)>threshold???
    if (numKeysToBeAdded > threshold) {
        int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
        if (targetCapacity > MAXIMUM_CAPACITY)
            targetCapacity = MAXIMUM_CAPACITY;
        int newCapacity = table.length;
        while (newCapacity < targetCapacity)
            newCapacity <<= 1;
        if (newCapacity > table.length)
            resize(newCapacity);
    }

    for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
        Map.Entry<? extends K, ? extends V> e = i.next();
        put(e.getKey(), e.getValue());
    }
}

先回答上面的问题：为什么判断条件是 numKeysToBeAdded，而不是 (numKeysToBeAdded + table.length) > threshold？

这是一种保守的做法。明显地，我们应该在 (numKeysToBeAdded + table.length) > threshold 的时候去拓展容量，但是考虑到将被添加的元素可能会有 Key 与原本存在的 Key 相同的情况（覆盖而非新增），所以采用保守的做法，避免拓展到过大的容量。

接着是遍历 m 中的内容，然后调用 put 方法将元素添加到 table 数组中。遍历的时候涉及到了 entrySet 方法，这个方法定义在 Map 接口中，HashMap 中也有实现，后面会解释 HashMap 的这个方法。

putForNullKey 方法

下面介绍在 put 方法中被调用到的 putForNullKey 方法。

private V putForNullKey(V value) {
    for (Entry<K,V> 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;
}

这是一个私有方法，在 put 方法中被调用。它首先遍历 table 数组，如果找到 key 为 null 的元素，则替换元素值并返回 oldValue；否则通过 addEntry 方法添加元素，之后返回 null。

putAllForCreate 与 putForCreate

还记得上面构造方法中调用到的 putAllForCreate 吗？一口气将 put 操作的相关方法看完。

private void putAllForCreate(Map<? extends K, ? extends V> m) {
    for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
        Map.Entry<? extends K, ? extends V> e = i.next();
        putForCreate(e.getKey(), e.getValue());
    }
}

先将遍历的过程放在一边，因为它同样涉及到了 entrySet() 方法。剩下的代码很简单，只是调用 putForCreate 方法逐个元素加入。

private void putForCreate(K key, V value) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            e.value = value;
            return;
        }
    }
    createEntry(hash, key, value, i);
}

该方法先计算需要添加的元素的 hash 值和在 table 数组中的索引 i。接着遍历 table[i] 的链表，若有元素的 key 值与传入 key 值相等，则替换 value，结束方法。若不存在 key 值相同的元素，则调用 createEntry 创建并添加元素。

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    size++;
}

这个方法的内容就不解释了，上面都解释过。至此所有 put 相关操作都解释完毕了。

get() 方法

put 之外，另一个常用的操作就是 get，下面就来看 get 方法。

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

该方法分为 key 为 null 和不为 null 两块。先看不为 null 的情况：先获取 key 的 hash 值，之后通过 hash 值及 table.length 获取 key 对应的 table 数组的索引，遍历索引的链表，若找到 key 相同的元素，则返回元素的 value，否则返回 null。key 为 null 的情况调用了 getForNullKey() 方法。

private V getForNullKey() {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

这是一个私有方法，只在 get 中被调用。该方法判断 table[0] 中的链表是否包含 key 为 null 的元素，包含则返回 value，不包含则返回 null。为什么是遍历 table[0] 的链表？因为 key 为 null 的时候获得的 hash 值都是 0。

判断元素是否存在

添加（put）和获取（get）都结束了，接着看如何判断一个元素是否存在。

HashMap 没有提供判断元素是否存在的方法，只提供了判断 Key 是否存在及 Value 是否存在的方法，分别是 containsKey(Object key)、containsValue(Object value)。

containsKey(Object key)

containsKey(Object key) 方法很简单，只是判断 getEntry(key) 的结果是否为 null，是则返回 false，否返回 true。

public boolean containsKey(Object key) {
    return getEntry(key) != null;
}

final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

getEntry(Object key) 也没什么内容，只是根据 key 对应的 hash 值计算在 table 数组中的索引位置，然后遍历该链表判断是否存在相同的 key 值。

containsValue(Object value)

public boolean containsValue(Object value) {
    if (value == null)
        return containsNullValue();

    Entry[] tab = table;
    for (int i = 0; i < tab.length; i++)
        for (Entry e = tab[i]; e != null; e = e.next)
            if (value.equals(e.value))
                return true;
    return false;
}

private boolean containsNullValue() {
    Entry[] tab = table;
    for (int i = 0; i < tab.length; i++)
        for (Entry e = tab[i]; e != null; e = e.next)
            if (e.value == null)
                return true;
    return false;
}

判断一个 value 是否存在比判断 key 是否存在还要简单，就是遍历所有元素判断是否有相等的值。这里分为两种情况处理，value 为 null 和不为 null 的情况，但内容差不多，只是判断相等的方式不同。

这个判断是否存在必须遍历所有元素，是一个双重循环的过程，因此是比较耗时的操作。

删除操作

接着看 HashMap 中“删除”相关的操作，有 remove(Object key) 和 clear() 两个方法。

remove(Object key)

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

看这个方法，removeEntryForKey(key) 的返回结果应该是被移除的元素，如果不存在这个元素则返回为 null。remove 方法根据 removeEntryForKey 返回的结果 e 是否为 null 返回 null 或 e.value。

final Entry<K,V> removeEntryForKey(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }

    return e;
}

上面的这个过程就是先找到 table 数组中对应的索引，接着就类似于一般的链表的删除操作，而且是单向链表删除节点，很简单。在 C 语言中就是修改指针，这个例子中就是将要删除节点的前一节点的 next 指向被删除节点的 next 即可。

clear()

public void clear() {
    modCount++;
    Entry[] tab = table;
    for (int i = 0; i < tab.length; i++)
        tab[i] = null;
    size = 0;
}

clear() 方法删除 HashMap 中所有的元素，这里就不用一个个删除节点了，而是直接将 table 数组内容都置空，这样所有的链表都已经无法访问，Java 的垃圾回收机制会去处理这些链表。table 数组置空后修改 size 为 0。

这里为什么不直接操作 table 而是通过 tab 呢？若有了解其原因的读者，欢迎指点。

集合视图方法

主要方法看的差不多了，接着看一个上面提到了好几次但是都搁在一边没有分析的方法：entrySet()。

entrySet()

public Set<Map.Entry<K,V>> entrySet() {
    return entrySet0();
}

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

为什么会有这样的方法，只是调用了一下 entrySet0，而且 entrySet0 的名称看着就很奇怪。再看 entrySet0 方法中为什么不直接 return entrySet != null ? entrySet : (entrySet = new EntrySet) 呢？

上面的疑问还没解开，但是先看 entrySet 这个属性吧，在文章开头的属性定义中并没有给出这个属性，下面先看一下它的定义：

private transient Set<Map.Entry<K,V>> entrySet = null;

它是一个内容为 Map.Entry<K,V> 的 Set。看看在哪些地方往里面添加了元素。

为什么上面的那句话我要把它标成红色？因为这是一个陷阱，在看代码的时候我就陷进去了。

仔细看 EntrySet 这个类。

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator();
    }
    public boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<K,V> e = (Map.Entry<K,V>) o;
        Entry<K,V> candidate = getEntry(e.getKey());
        return candidate != null && candidate.equals(e);
    }
    public boolean remove(Object o) {
        return removeMapping(o) != null;
    }
    public int size() {
        return size;
    }
    public void clear() {
        HashMap.this.clear();
    }
}

看到了什么？这个类根本没属性，它只是个代理。因为它是内部类，可以访问外部类的内容，debug 的时候能看到的属性都是继承或者外部类的属性，输出的时候其实也是调用到了父类的 toString 方法将 HashMap 中的内容输出了。

keySet()

public Set<K> keySet() {
    Set<K> ks = keySet;
    return (ks != null ? ks : (keySet = new KeySet()));
}

是不是和 entrySet0() 方法很像！

private final class KeySet extends AbstractSet<K> {
    public Iterator<K> iterator() {
        return newKeyIterator();
    }
    public int size() {
        return size;
    }
    public boolean contains(Object o) {
        return containsKey(o);
    }
    public boolean remove(Object o) {
        return HashMap.this.removeEntryForKey(o) != null;
    }
    public void clear() {
        HashMap.this.clear();
    }
}

同样是个代理类，contains、remove、clear 方法都是调用的 HashMap 的方法。

values()

public Collection<V> values() {
    Collection<V> vs = values;
    return (vs != null ? vs : (values = new Values()));
}

private final class Values extends AbstractCollection<V> {
    public Iterator<V> iterator() {
        return newValueIterator();
    }
    public int size() {
        return size;
    }
    public boolean contains(Object o) {
        return containsValue(o);
    }
    public void clear() {
        HashMap.this.clear();
    }
}

values() 方法也一样是代理。只是 Values 类继承自 AbstractCollection 类，而不是 AbstractSet。

总结

还有一个重要的内容没有进行说明，那就是迭代器。HashMap 中的 entrySet()、keySet()、values() 等方法都使用到了迭代器 Iterator 的知识。其他集合类也有使用到迭代器，将另写博文总结讨论集合类的迭代器。

说明：本文基于 JDK 1.6 版本源码进行分析。JDK 1.8 及后续版本中 HashMap 引入了红黑树优化链表过长的问题，底层结构与扩容机制有较大变化，阅读新版本源码时请注意区别。

本文地址：https://1diff.fun/archives/hashmap-yuan-ma-fen-xi--ji-yu-jdk16.html

如果对本文有什么问题或疑问都可以在评论区留言，我看到后会尽量解答。

HashMap源码分析（基于JDK1.6）