深入解析Java HashMap的Resize源码

2024-06-06 08:21:56 浏览数 (3)

Java中的HashMap是一个常用的数据结构，底层实现由数组和链表（或红黑树）组成。随着插入元素的增多，HashMap需要扩容以维持高效的性能。本文将深入解析HashMap的扩容机制——resize()方法，通过逐行代码解释其实现原理和背后的设计思想。

1. HashMap的基本结构

在深入resize()方法的分析之前，首先理解HashMap的基本结构和工作机制。HashMap主要由以下几个部分组成：

  1. 数组（table）：存储键值对节点的主要结构。
  2. 链表：在哈希冲突时，多个键值对存储在数组的同一个位置，以链表形式连接在一起。
  3. 红黑树：在Java 8之后，当链表长度超过一定阈值（默认是8）时，链表会转换成红黑树以提高查询效率。

2. HashMap扩容的必要性

随着HashMap中的元素增多，负载因子（元素数量/数组容量）接近或超过默认值（0.75）时，查询和插入效率会显著下降。为了保持高效操作，HashMap在元素数目超过一定阈值时进行扩容。扩容的核心是resize()方法。

3. resize()方法源码分析

以下是resize()方法的源码：

代码语言：javascript复制
final HashMap.Node<K, V>[] resize() {
    HashMap.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;
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    } else if (oldThr > 0)
        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"})
    HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap;   j) {
            HashMap.Node<K, V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                else {
                    HashMap.Node<K, V> loHead = null, loTail = null;
                    HashMap.Node<K, V> hiHead = null, hiTail = null;
                    HashMap.Node<K, V> next;
                    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);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j   oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
3.1 计算新容量和新阈值

在resize()方法的开头，首先计算新数组的容量和新的阈值。通过检查旧数组的容量和阈值，方法决定新的容量和阈值：

代码语言：javascript复制
HashMap.Node<K, V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;

接着根据旧的容量和阈值，分几种情况处理：

3.1.1 旧容量大于0

如果旧数组的容量大于0，说明不是第一次扩容：

代码语言：javascript复制
if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1;
}
  • 若旧容量大于等于最大容量，设置阈值为最大整数值，不再扩容。
  • 若旧容量小于最大容量，且旧容量大于等于默认初始容量，则新容量为旧容量的两倍，新的阈值为旧阈值的两倍。
3.1.2 旧阈值大于0

如果旧数组的容量为0，但旧阈值大于0，说明是在初始化时指定了初始容量：

代码语言：javascript复制
else if (oldThr > 0)
    newCap = oldThr;

将新容量设置为旧阈值。

3.1.3 初始默认值

如果旧数组容量和阈值都为0，使用默认值进行初始化：

代码语言：javascript复制
else {
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
3.2 计算新阈值

如果新的阈值未被设置，则根据新的容量和加载因子计算新的阈值：

代码语言：javascript复制
if (newThr == 0) {
    float ft = (float) newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
}
threshold = newThr;
3.3 创建新数组

创建一个新的数组newTab，并将其赋值给table：

代码语言：javascript复制
@SuppressWarnings({"rawtypes", "unchecked"})
HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
table = newTab;
3.4 元素迁移

将旧数组中的元素重新散列到新数组中：

代码语言：javascript复制
if (oldTab != null) {
    for (int j = 0; j < oldCap;   j) {
        HashMap.Node<K, V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            if (e.next == null)
                newTab[e.hash & (newCap - 1)] = e;
            else if (e instanceof TreeNode)
                ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
            else {
                HashMap.Node<K, V> loHead = null, loTail = null;
                HashMap.Node<K, V> hiHead = null, hiTail = null;
                HashMap.Node<K, V> next;
                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);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j   oldCap] = hiHead;
                    }
                }
            }
        }
    }
}
return newTab;

上述代码块的核心是将旧数组中的每个元素按新的容量重新散列到新数组中，确保HashMap的分布均匀性和查询效率。

3.5 拆分链表

在迁移过程中，如果遇到链表或树节点，需要分别处理：

  • 链表：拆分成两个链表，一个放在低位索引，另一个放在高位索引。
  • 树节点：调用TreeNode的split方法进行处理。
代码语言：javascript复制
else if (e instanceof

 TreeNode)
    ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else {
    HashMap.Node<K, V> loHead = null, loTail = null;
    HashMap.Node<K, V> hiHead = null, hiTail = null;
    HashMap.Node<K, V> next;
    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);
    if (loTail != null) {
        loTail.next = null;
        newTab[j] = loHead;
    }
    if (hiTail != null) {
        hiTail.next = null;
        newTab[j   oldCap] = hiHead;
    }
}
3.6 重新分布元素

在处理元素迁移时，通过计算新索引，将元素放置在新数组的适当位置：

  • 对于单个元素，直接根据新容量计算新的索引位置。
  • 对于链表，拆分成两个子链表，分别放置在低位索引和高位索引。
  • 对于红黑树，调用TreeNode的split方法，按照新容量重新组织树结构。

4. 深度分析与优化

4.1 扩容策略

HashMap的扩容策略是当元素数量超过阈值时，将数组容量翻倍。这种策略有效地减少了哈希冲突，提高了查找效率。阈值的更新逻辑也确保了HashMap在扩容后的负载因子保持在合理范围内。

4.2 重新散列

重新散列（rehash）是扩容过程中最重要的步骤。通过对旧数组中的每个元素重新计算哈希值，并将其放置到新数组中的适当位置，确保了数据的均匀分布。重新散列的计算通过e.hash & (newCap - 1)进行，利用了哈希值的低位特性，使得散列结果更加均匀。

4.3 树化和退化

在迁移过程中，HashMap还考虑了链表的长度。如果链表长度超过阈值（8），链表会转换成红黑树，以提高查找效率；如果链表长度减少到6以下，红黑树会退化成链表。这种设计确保了HashMap在不同负载情况下都能保持高效。

4.4 内存管理

扩容过程中，新旧数组的内存管理也是关键。通过重新分配新数组，并将旧数组的元素迁移到新数组，HashMap在扩容后仍能保持高效的内存使用。

5. 性能优化建议

5.1 优化哈希函数

HashMap依赖哈希函数将键散列到数组的不同位置。优化哈希函数可以减少哈希冲突，提高查找效率。确保哈希函数生成的哈希值均匀分布在整个数组范围内，是优化HashMap性能的关键。

5.2 动态调整阈值

在实际应用中，不同的使用场景可能需要不同的负载因子。通过动态调整阈值，可以在不同负载下优化HashMap的性能。例如，在高并发环境下，可以适当降低负载因子，以减少扩容频率。

5.3 并发扩容

在多线程环境下，HashMap的扩容可能会导致性能瓶颈。引入并发扩容机制，例如分段锁或CAS操作，可以提高HashMap在高并发场景下的性能。Java的ConcurrentHashMap就是通过分段锁机制实现了高并发下的高效扩容。

6. 总结

通过对HashMap的resize()方法的详细分析，可以看出其设计的精妙之处。在扩容过程中，既考虑了性能优化，又保证了数据的正确性。整个过程分为计算新容量和阈值、创建新数组、迁移旧元素三个主要步骤。每一步都精确地考虑了各种可能的情况，使得HashMap在面对不同负载和容量需求时能够高效运作。

HashMap作为Java中重要的数据结构，其内部实现充分展示了数据结构与算法的巧妙结合。理解其扩容机制，对于实际应用中优化性能、合理使用内存具有重要意义。通过不断优化哈希函数、动态调整阈值和引入并发扩容机制，可以进一步提升HashMap的性能，使其在各种复杂应用场景中表现出色。

resize 数组 源码 java hashmap

0 人点赞