HashMap 源码详解

本文主要是介绍HashMap 源码详解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

概述

HashMap 允许 null 的键和值。

Hashtable 既不允许 null 的值，也不允许 null 的键。都会抛出 NullPointerException。

get put 时间复杂度是常数级别的。

HashMap 有两个参数影响其性能：initial capacity 初始容量 和 load factor 负载因子。capacity 指的是 bucket 的数量，即数组的长度。load factor 控制可以满到什么程度，默认为 0.75，较好的权衡了时间与空间成本。

当元素的个数超过 load factor * current capacity 时，会触发扩容。应该按照实际用途指定初始容量的大小，如果预计元素只有几个，那么设置一个较小的初始容量，而不是使用默认值 16；如果预计要存储大量的元素，那么请一开始就设置一个较大的初始容量，而不是让它进行多次的扩容，扩容会影响 put 的性能。

/**
 * The default initial capacity - MUST be a power of two.
 * 默认的初始容量（桶的个数），必须为 2 的次幂
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 * 构造方法可指定的最大容量（桶的个数） <= 1<<30
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The load factor used when none specified in constructor.
 * 默认的负载因子
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap 不是 synchronized 同步的。如果多个线程同时访问一个实例，并且至少有一个线程在结构上修改了该 Map，那么它必须在外部进行同步。结构化修改是添加或删除一个或多个元素的操作；修改与现有键相关联的值并不是结构化修改。换句话说，添加、删除属于结构化修改，更新不属于。可用 Collections 包装成同步的 Map：

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

==HashMap 的集合视图都是 fail-fast。==比如 keySet()、entrySet()、values() 方法的返回值。

为什么不一直使用红黑树，而是设置一个阈值 8？

TreeNode 主要按照 hashCode 进行排序，如果 hashCode 相同的话，会按照类型取比较，参考 comparableClassFor()、compareComparables()。

因为 TreeNode 的大小大约是常规节点的两倍，所以只在容器中包含足够的节点时才使用它们，TREEIFY_THRESHOLD = 8。

当它们变得太小（由于删除或 resize），它们会被转换回普通的 Node。

hashCode 均匀分布时，很少能用到 TreeNode。

0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million

Node 的实现

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}    

hash() 方法为什么这样设计

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

之所以将 hashCode 右移 16 位再与自己异或，是为了增加扰动。int 占 4 byte = 32 bit，index = (tab.length - 1) & hash 用来取下标，当 tab.length 小于 16 位时，在计算下标时只会用到 hash 的低位，高位没有被考虑进去，hash 冲突的几率就比较大。让高 16 位 与 低 16 位先进行异或，再用结果去与上 tab.length - 1，这样高位、低位都参与了计算，增加了扰动，hash 冲突的几率就会小一些。

null 的 hash 恒等于 0。

tableSizeFor() 返回一个大于等于 cap 的 2 的次幂

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

2^N 用二进制表示就是 1 后面跟着 N 个 0。2^N - 1 就是连续的 N 个 1。

// 2 次幂 = 4
100
 11
// 4 次幂 = 16
10000
 1111
...

我们的基本思路就是：将数字 cap 最高位的 1 后面的所有位都置为 1，再将结果加一，得到 2^N 。但这种方法有个前提就是 cap 本身不能是 2^N ，因为这样会导致错误的结果 2 * cap。

// 正例：假设 cap 为 50
0011 0010
0011 1111
+
0000 0000
=
0100 0000 = 64

// 反例：假设 cap 为 16
0001 0000
0001 1111
+
0000 0001
0010 0000 = 32

为了解决 cap 本身就是 2^N 问题，我们可以让 int n = cap - 1，以 n 来进行上述运算，最后再加一。这样经过运算之后结果还是 cap。

// 假设 cap 为 16，则 n = cap - 1 = 15
0001 0000
-
0000 0001
=
0000 1111
// 将低位都置为一，实际什么都没做
0000 1111
+
0000 0001
=
0001 0000 = 16

如何将低位都置为一

n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;

n |= n >>> 1 ，n 不等于零，所以一定会有一个最高位的一，我们只考虑最高位的一，运算就相当于 1x | 01x = 11x ， x 代表任意个 0 或 1，一定能保证最高位出现相邻的两个 1：

	001xxxxxxxxxxxxx
| 	 001xxxxxxxxxxxx
=	0011xxxxxxxxxxxx

n |= n >>> 2，在上一步中已经得到了最高位的两个 1，本次运算能保证出现 4 个连续的 1，11x | 0011x = 1111x：

	0011xxxxxxxxxxxx
|	  0011xxxxxxxxxx
=	001111xxxxxxxxxx

n |= n >>> 4 也是重复上面的操作，1111x | 0000 1111x = 1111 1111x，会得到 8 个连续的 1：

	001111xxxxxxxxxx
|		001111xxxxxx
=	0011111111xxxxxx

n |= n >>> 8;n |= n >>> 16; 分别会得到 16、32 个连续的 1，由于 cap 是 int 类型，共 32 位，所以需要执行到 n |= n >>> 16。

实例变量

// 主存，大小为 2 的次幂，在第一次使用时才初始化
transient Node<K,V>[] table;

// entrySet() 方法的返回值
transient Set<Map.Entry<K,V>> entrySet;

// 存储的元素个数
transient int size;

// Map 被结构化修改的次数，实现 fail-fast 机制
transient int modCount;

// resize 的阈值 = capacity * load factor
int threshold;

// 负载因子
final float loadFactor;

构造方法

table[] 是延迟初始化的，等到 put 时才真正初始化（通过 resize() 方法初始化）。不同的构造方法会导致 resize 时进入不同的分支。

无参构造方法

// loadFactor = 0.75;
// threshold = 0; 会进入 resize 的第三个分支
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

传入初始容量、负载因子

public HashMap(int initialCapacity) {
	this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
    // 若传入的容量过大，则使用最大容量 1 << 30
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    this.loadFactor = loadFactor;
    // 取大于等于 initialCapacity 的 2 的次幂，会进入 resize 的第二个分支
    // tableSizeFor 的返回值实际是容量 capacity，将 capacity 存储到了 threshold 中
    // 从 resize 的第二个分支中的注释（initial capacity was placed in threshold）中可以看出 
    this.threshold = tableSizeFor(initialCapacity);
}

传入 Map

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

putMapEntries

putMapEntries() 会被构造方法、putAll() 方法调用。

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    // 传入的 map 中有元素
    int s = m.size();
    if (s > 0) {
        // 这个分支，说明是第一次 put 元素
        // 可能是构造方法调用的
        // 也可能是实例化之后没放过任何元素，然后调用了 putAll() 方法
        if (table == null) { // pre-size
            // 根据 loadFactor 反算容量，+ 1.0F 是为了向上取整
            float ft = ((float)s / loadFactor) + 1.0F;
            // 判断容量是否过大，过大则取最大容量
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                        (int)ft : MAXIMUM_CAPACITY);
            // threshold 是旧的阈值，重新计算容量之后可能旧阈值不适用了，需要重新计算
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        // 将指定 map 中的元素放入本
        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);
        }
    }
}

put、putIfAbsent

插入或更新键值对，并返回 key 关联的 old value。有两种情况返回 null：

• 原来不存在 key
• 原来存在 key，但与之关联的 old value 是 null

所以不能以 put() 方法的返回值判断 key 是否存在，必须使用 containsKey()。

// 先计算 hash，再调用 putVal()
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; 
    Node<K,V> p; 
    // n 是 table 数组的 length，i 是下标
    int n, i;
    // 如果 table 为 null，或者长度为 0，需要先扩容（或者初始化）才能插入元素
    // 只有首次插入才会进入这个 if
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // i = (n - 1) & hash 计算下标
    // p 为链表的头
    // 如果该位置为空，则直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    // 该位置不为空，则需要遍历链表，查找键为 key 的节点
        // 如果能找到目标节点，则直接更新 value 为新值即可
        // 如果找不到，则需要在链表的尾部追加新节点
    else {
        // e 代表最终找到的目标节点，可能为空（不存在目标节点）
        Node<K,V> e; 
        K k;
        // 判断 p（链表的头）的键是否等于 key
        // 以下判断等价于 p.hash == hash && Objects.equals(key, p.key)
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 若相等，则将 p 赋值给 e
            e = p;
        
        // 红黑树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 在第一个 if 已经判断过链表的头结点了
            // 这里从头结点的下一个节点开始遍历链表，查找键等于 key 的 Node，
                // 如果能找到目标节点，则直接更新 value 为新值即可
                // 如果找不到，则需要在链表的尾部追加新节点
            // 同时使用 binCount 记录链表中节点的个数，以便将链表升级为红黑树
            for (int binCount = 0; ; ++binCount) {
                // 遍历到链表的尾部了，最终没找到目标节点
                if ((e = p.next) == null) {
                    // 构建新节点，追加到链表的尾部（尾插法）
                    p.next = newNode(hash, key, value, null);
                    // binCount 为原链表的节点数，不包括刚刚插入的新节点，
                    // binCount + 1 才是现在链表的节点数
                    // 这个 if 判断相当于 if(binCount + 1>= TREEIFY_THRESHOLD)
                    // 既插入新节点后，长度 >= 8 才会树化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                // 判断 e 的键是否等于 key，若相等则找到了目标节点，直接跳出循环，更新 value 为新值即可
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                
                // 若不是目标节点，则继续遍历
                // p = e；等价于 p = p.next （因为 e = p.next）
                p = e;
            }
        }
        // e == null 说明没找到目标节点，在链表尾部追加了新节点，最后返回 null
        // e != null 说明找到了键等于 key 的节点，需要更新 value，最后返回 old value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent 为 true 表示只有在 key 不存在时，才执行 put，否则什么都不做
            // 换句话说就是，只插入，不更新
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 结构化修改次数加一
    ++modCount;
    // 总元素数加一
    // 若插入后超过了阈值，则执行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

resize

会在两种情况下被调用：

1. 初始化，即首次添加元素时，初始化主数组
2. 空间不足，需要扩容时

将老数组的元素 copy 到新数组时，没有进行暴力计算，而是 因为数组的大小始终是 2^N，且扩容时或将其翻倍，变成 2^N+1。所以桶中的元素要么留在原索引位置（假设索引为 i），要么右移 2^N 移动到索引为（i + 老容量）的桶中，下面举例说明：

索引计算公式 i = (table.length - 1) & hash ，在扩容后只有 table.length 发生了变化，从 2^N 变成了 2^N+1。我们知道 2^N 用二进制表示是 1 后面跟着 N 个 0。 2^N - 1 表示为二进制就是 N 个连续的 1。比如扩容前数组长度为 32，扩容后为 64：

// 32（2 的 5 次方）、64（2 的 6 次方）
取决于这一位
  ↓
0010 0000	32
0100 0000	64

0001 1111	31
0011 1111	63
  ↑
取决于这一位

31 & hash、63 & hash 结果是否一样（是否留在原索引位置）只取决于第 6 位是 0 还是 1，而这一位可以用 hash & 32 来判断，也就是源码中的 if ((e.hash & oldCap) == 0) ，若等于 0 则留在原索引位置（i），否则放入新的索引位置（i + oldCap）。比如 67 和 100：

// 67 原索引 3 新索引 3
  0100 0011
& 0001 1111	31
---------------
  0000 0011	3

  0100 0011
& 0011 1111	63
---------------
  0000 0011	3

// 100 原索引 4 新索引 36
  0110 0100
& 0001 1111	31
---------------
  0000 0100 4

  0110 0100
& 0011 1111	63
---------------
  0010 0100 36

final Node<K,V>[] resize() {
    // 老数组
    Node<K,V>[] oldTab = table;
    // 老的容量-老数组的 length
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 老的扩容阈值
    int oldThr = threshold;
    // 新的容量、新的扩容阈值（默认为 0）
    int newCap, newThr = 0;
    // 老数组不为空，即不是初始化，而是由空间不足引发的扩容
    if (oldCap > 0) {
        // 老数组已经超过允许的最大容量
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 将扩容阈值设置为 Integer 的最大值，返回老数组
            // 没有触发真正的扩容，以后也不会触发了，因为已经到最大值了
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // newCap = oldCap << 1 新容量为旧容量的 2 倍
        // newCap < MAXIMUM_CAPACITY，且 oldCap >= 16 时，将扩容阈值翻倍
        // 当 oldCap >= MAXIMUM_CAPACITY 或 oldCap < 16 时，会进入下面 if (newThr == 0) 中
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 新阈值为老阈值的 2 倍
            newThr = oldThr << 1; // double threshold
    }
    // 当调用有参构造方法，传入初始容量 initialCapacity 时，会进入这个分支，
    // 因为构造方法将计算后的容量（2 的次幂）存入了阈值中，导致了 oldCap == 0 && oldThr > 0
    // 部分代码 this.threshold = tableSizeFor(initialCapacity);
    else if (oldThr > 0) // initial capacity was placed in threshold 
        				 // 翻译：初始容量被放入了 threshold 变量中
        // 因为 oldThr 存的就是初始容量，所有直接使用即可
        newCap = oldThr;
    // 调用无参构造方法，会进入此分支
    // 因为无参构造方法，没有初始化 table[]、threshold，所以 oldCap == 0 && oldThr == 0
    else {               // zero initial threshold signifies using defaults 
        				 // 翻译：初始阈值为零表示使用默认值
        // 新容量为 16，新阈值为 12 = 0.15 * 16
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 处理上面 oldCap > 0 分支中 oldCap >= MAXIMUM_CAPACITY 或 oldCap < 16 的情况
    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;
            // 桶中有节点才操作，将桶中的链表头节点赋值给 e
            if ((e = oldTab[j]) != null) {
                // 将老数组的元素置为 null，能更好的 GC
                oldTab[j] = null;
                // 桶中只有一个节点，直接计算下标放入新数组
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 桶中有多个节点，且结构是红黑树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 桶中有多个节点，且结构是链表
                else { // preserve order
                    // 根据前面说过的原理，节点要么留在原索引位置 j，要么移动到新索引位置 j + oldCap
                    // 所以原来的一个链表会被分成两个链表，一个在索引 j，另一个在索引 j + oldCap 的位置
                    // 低位的链表，即 j 位置的链表的头尾
                    Node<K,V> loHead = null, loTail = null;
                    // 高位的链表，即 j + oldCap 位置的链表的头尾
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍历链表，根据 e.hash & oldCap 判断，等于 0 则追加到链表 lo，否则追加到链表 hi
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 将 lo 链表放入数组的 j 位置
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 将 hi 链表放入数组的 j + oldCap 位置
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

get、getOrDefault

与 put() 类似，有两种情况返回 null：

• 原来不存在 key
• 原来存在 key，但与之关联的 value 是 null

所以也不能以 get() 方法的返回值判断 key 是否存在，必须使用 containsKey()。

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

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

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 数组为空，或根据下标找不到节点，直接返回 null，否则遍历链表，寻找 key 相同的节点
    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;
        // 链表中有多个节点，则遍历查找
        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;
}

containsKey

必须用 containsKey 判断 key 是否存在

public boolean containsKey(Object key) {
	return getNode(hash(key), key) != null;
}

remove

remove(key) 删除指定 key 的关联的条目，并返回被删除条目的 value。与 put() 一样，有两种情况返回 null。

remove(key, value) 删除键为 key 且值为 value 的条目，成功删除时返回 true。

public V remove(Object key) {
    Node<K,V> 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;
}

// matchValue 是否需要匹配 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;
    // 数组为空，或根据下标找不到节点，直接返回 null，否则遍历链表，寻找目标
    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
            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，退出循环
                        node = e;
                        break;
                    }
                    // p 代表 e、node 的前一个节点
                    p = e;
                    // 找不到则继续遍历
                } while ((e = e.next) != null);
            }
        }
        // node != null 即找到了目标节点（通过 key）且（不需要匹配 value 或 value 是匹配的）
        // !matchValue 表示不需要匹配 value
        // (v = node.value) == value || (value != null && value.equals(v)) 表示 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;
            // 其他节点是目标节点，则删除目标节点 node
            else
                p.next = node.next;
            // 结构化修改次数加一
            ++modCount;
            // 元素数据减一
            --size;
            afterNodeRemoval(node);
            // 返回被删除的目标节点
            return node;
        }
    }
    return null;
}

clear

简单粗暴，直接将数组清空

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

containsValue

是否包含指定的 value。直接双重 for 循环查找。

Map 中可能包含树节点 TreeNode，为什么可以当做链表来遍历？

因为 TreeNode extends LinkedHashMap.Entry，而Entry extends HashMap.Node，红黑树节点同时还维护了一个双向链表。

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

树化的条件

树化的条件有两个：

1. 桶中的元素个数 >= TREEIFY_THRESHOLD （8），在前面的 put() 方法中已经说过
2. 数组的长度要 >= MIN_TREEIFY_CAPACITY （64），若小于 MIN_TREEIFY_CAPACITY 会触发扩容，而不是树化

这篇关于HashMap 源码详解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！