深入解析Java HashMap的高性能扩容机制与树化优化

本文涉及的产品
云解析 DNS,旗舰版 1个月
云解析DNS,个人版 1个月
全局流量管理 GTM,标准版 1个月
简介: 深入解析Java HashMap的高性能扩容机制与树化优化

深入解析Java HashMap的高性能扩容机制与树化优化

Java中的HashMap是一个基于哈希表实现的键值对(key-value)存储数据结构。它属于Java Collections

Framework的一部分,用于高效地存储和检索数据。以下是对Java HashMap的一些详细探讨:

基本特性

  • 键值对存储:HashMap存储键值对,每个键对应一个值。键和值都可以是任意类型的对象。
  • 键的唯一性:HashMap中的键是唯一的,即不允许有重复的键。若尝试存储一个已经存在的键,其对应的值将被新的值替换。
  • 无序存储:HashMap不保证键值对的顺序,这意味着存储的顺序与遍历的顺序可能不同。

主要操作

  • put(K key, V value):将指定的键值对插入到HashMap中。如果键已经存在,则更新对应的值。
  • get(Object key):根据键获取对应的值,如果键不存在,则返回null。
  • remove(Object key):移除指定键的键值对。
  • containsKey(Object key):判断HashMap中是否包含指定的键。
  • containsValue(Object value):判断HashMap中是否包含指定的值。
  • size():返回HashMap中键值对的数量。
  • isEmpty():判断HashMap是否为空。

内部工作原理

HashMap的核心在于哈希表(hash table)实现。以下是其基本工作流程:

  • 哈希函数:通过键的hashCode()方法计算哈希值,然后用哈希值对数组长度取模,确定键值对在哈希表中的位置。
  • 冲突处理:当不同的键计算得到的哈希值相同时,会发生哈希冲突。Java使用链表法(即链地址法)来处理冲突:在哈希表的每个位置上,实际存储的是一个链表,所有哈希值相同的键值对都存储在该链表中。
  • 扩容机制(最后部分重点解释):HashMap有一个负载因子(默认0.75),当实际存储的键值对数量超过capacity * loadFactor时,HashMap会进行扩容(通常是原来容量的两倍),并重新散列所有的键值对到新的哈希表中。

优缺点

优点

  • 快速存取:在理想情况下,HashMap的插入、删除和查找操作的时间复杂度为O(1)。
  • 灵活性:HashMap允许使用null值和null键,这在某些应用场景下非常灵活。

缺点

  • 非线程安全:HashMap不是线程安全的。如果多个线程同时操作同一个HashMap实例而没有适当的同步措施,会导致数据不一致。线程安全请参考全面解读CourrentHashMap
  • 性能退化:在极端情况下(如所有键的哈希值都相同),HashMap的性能会退化为O(n)。

扩容机制(结合treeifyBin方法)

在Java 8中,HashMap在处理哈希冲突时引入了树化机制。当某个桶中的链表长度超过一定阈值时(默认是8),链表会被转换成红黑树,以提高查询效率。这一过程被称为树化(treeify),而具体的树化操作则是在treeifyBin方法中进行的。下面我们结合treeifyBin方法和扩容过程来详细讲解。


treeifyBin 方法

首先,让我们看一下treeifyBin方法的实现:

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

关键点分析
  • 树化的触发条件
    当某个桶中的链表长度超过阈值(默认8)时,会触发树化。但是,在进行树化之前,会检查哈希表的容量。如果当前哈希表的容量小于最小树化容量(默认64),则会进行扩容而不是树化:
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();

MIN_TREEIFY_CAPACITY的默认值是64。这意味着,如果当前哈希表的容量小于64,即使链表长度超过阈值,也不会进行树化,而是优先扩容。这是为了避免在容量较小的哈希表中引入树结构,进而影响性能。

  • 链表转换为红黑树

如果哈希表的容量大于或等于最小树化容量,会将链表节点转换为红黑树节点:

else if ((e = tab[index = (n - 1) & hash]) != null) {
    TreeNode<K,V> hd = null, tl = null;
    do {
        TreeNode<K,V> p = replacementTreeNode(e, null);
        if (tl == null)
            hd = p;
        else {
            p.prev = tl;
            tl.next = p;
        }
        tl = p;
    } while ((e = e.next) != null);
    if ((tab[index] = hd) != null)
        hd.treeify(tab);
}

这里,首先遍历链表,将每个普通节点(Node)转换为红黑树节点(TreeNode)。然后,将转换后的树节点构建成一个双向链表,最后调用红黑树节点的treeify方法将链表转换为红黑树。

  • replacementTreeNode 方法
  • 该方法用于将普通节点转换为红黑树节点:
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next, null);
}
  • treeify方法
    红黑树节点的treeify方法将链表转换为红黑树:
final void treeify(Node<K,V>[] tab) {
    // Implementation details...
}


扩容与树化的关系

在HashMap中,扩容与树化是两种不同的性能优化手段。当哈希表的容量不足时,扩容是首选的优化手段,而当哈希表容量足够大且某个桶中的链表过长时,才会进行树化操作。扩容的主要目的是减少哈希冲突,从而降低链表长度,而树化则是通过将链表转换为红黑树来提高查找效率。


扩容过程中处理树节点

  • 在扩容过程中,如果旧哈希表中某个桶已经是红黑树结构,那么在将这些节点重新哈希到新哈希表时,需要保持红黑树结构。这一点在扩容的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;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;
    }
    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"})
    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) {
                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
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    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;
}

TreeNodesplit 方法

TreeNodesplit方法将当前红黑树节点分割为两个链表,一个保留在原位置,另一个移动到新位置:

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // 两个新的链表头
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
    if (loHead != null)
        tab[index] = loHead;
    if (hiHead != null)
        tab[index + bit] = hiHead;
    // 将链表转换为红黑树
    if (lc <= UNTREEIFY_THRESHOLD)
        tab[index] = loHead.untreeify(map);
    else if (loHead != null)
        loHead.treeify(tab);
    if (hc <= UNTREEIFY_THRESHOLD)
        tab[index + bit] = hiHead.untreeify(map);
    else if (hiHead != null)
        hiHead.treeify(tab);
}

在扩容过程中,split方法会将当前红黑树节点分成两部分,然后判断链表长度是否低于树化阈值(UNTREEIFY_THRESHOLD,默认6)。如果低于阈值,则将红黑树退化为链表;否则,保持红黑树结构。


总结

通过treeifyBin方法和resize方法的源码分析,可以看出Java 8中HashMap在处理哈希冲突和扩容方面的优化手段:

  • 树化:当桶中链表长度超过阈值时,将链表转换为红黑树,以提高查询效率。
  • 扩容优先:如果哈希表容量不足,则优先进行扩容,而不是树化,以避免在小容量时引入树结构。
  • 扩容处理树节点:在扩容过程中,保留红黑树结构,并根据新链表长度决定是否退化为链表。
    这些机制共同保证了HashMap在处理大量数据时的高效性。理解这些实现细节有助于在实际使用中优化HashMap的性能。
目录
相关文章
|
17小时前
|
安全 Java 数据处理
Java并发编程:线程同步与协作的深度解析
在探索Java并发编程的海洋中,线程同步与协作的灯塔指引着航向。本文将深入挖掘线程同步机制的核心原理,揭示锁、条件变量等工具如何确保数据的一致性和线程间有序的通信。通过案例分析,我们将解码高效并发模式背后的设计哲学,并探讨现代Java并发库如何简化复杂的同步任务。跟随文章的步伐,您将获得提升多线程应用性能与可靠性的关键技能。 【7月更文挑战第24天】
11 5
|
1天前
|
安全 Java 编译器
Java内存模型深度解析
【7月更文挑战第23天】在探索Java的高效与稳定性之谜时,我们不可避免地要深入其核心——Java内存模型(JMM)。本文将揭开JMM的神秘面纱,从基本概念到底层实现机制,再到并发编程中的应用实践,全面剖析这一确保Java程序正确性的基石。通过理解JMM的设计哲学和运作原理,开发者能够更好地编写出既高效又线程安全的代码,避免那些隐藏在多线程环境下的陷阱。
|
2天前
|
缓存 安全 算法
Java内存模型深度解析与实践应用
本文深入探讨Java内存模型(JMM)的核心原理,揭示其在并发编程中的关键作用。通过分析内存屏障、happens-before原则及线程间的通信机制,阐释了JMM如何确保跨线程操作的有序性和可见性。同时,结合实例代码,展示了在高并发场景下如何有效利用JMM进行优化,避免常见的并发问题,如数据竞争和内存泄漏。文章还讨论了JVM的垃圾回收机制,以及它对应用程序性能的影响,提供了针对性的调优建议。最后,总结了JMM的最佳实践,旨在帮助开发人员构建更高效、稳定的Java应用。
|
7天前
|
存储 监控 算法
Java 内存管理与垃圾回收机制深度解析
本文深入探讨了Java的内存管理与垃圾回收(GC)机制,从JVM内存结构出发,详细分析了堆、栈、方法区的职能及交互。文章重点讨论了垃圾回收的核心概念、常见算法以及调优策略,旨在为Java开发者提供一套系统的内存管理和性能优化指南。 【7月更文挑战第17天】
|
7天前
|
Java 编译器 开发者
Java 内存模型深度解析
本文旨在深入探讨Java内存模型的复杂性及其对并发编程的影响。通过揭示内存模型的核心原理、JMM的结构,并结合具体案例和数据分析,本文将帮助读者理解Java内存模型如何确保多线程程序的正确性和性能,以及如何在实际应用中有效利用这一模型进行高效的并发编程。 【7月更文挑战第17天】
16 4
|
20天前
|
存储 安全 Java
深度长文解析SpringWebFlux响应式框架15个核心组件源码
以上是Spring WebFlux 框架核心组件的全部介绍了,希望可以帮助你全面深入的理解 WebFlux的原理,关注【威哥爱编程】,主页里可查看V哥每天更新的原创技术内容,让我们一起成长。
|
21天前
|
关系型数据库 分布式数据库 数据库
PolarDB-X源码解析:揭秘分布式事务处理
【7月更文挑战第3天】**PolarDB-X源码解析:揭秘分布式事务处理** PolarDB-X,应对大规模分布式事务挑战,基于2PC协议确保ACID特性。通过预提交和提交阶段保证原子性与一致性,使用一致性快照隔离和乐观锁减少冲突,结合故障恢复机制确保高可用。源码中的事务管理逻辑展现了优化的分布式事务处理流程,为开发者提供了洞察分布式数据库核心技术的窗口。随着开源社区的发展,更多创新实践将促进数据库技术进步。
25 3
|
22天前
|
前端开发 开发者
深入解析Vite.js源码
【7月更文挑战第1天】Vite.js 深入解析:以其无bundle开发、动态ES模块加载提升开发效率;本地HTTP服务器配合WebSocket实现热更新;按需加载减少资源占用;预构建优化生产环境性能;基于Rollup的插件系统增强灵活性。Vite,一个创新且高效的前端构建工具。
23 0
|
1月前
|
Java Spring
深入解析Spring源码,揭示JDK动态代理的工作原理。
深入解析Spring源码,揭示JDK动态代理的工作原理。
28 0
|
1月前
|
XML Java 数据格式
深度解析 Spring 源码:从 BeanDefinition 源码探索 Bean 的本质
深度解析 Spring 源码:从 BeanDefinition 源码探索 Bean 的本质
35 3

推荐镜像

更多