Java性能优化(三):Java基础-HashMap的设计与优化

本文涉及的产品
应用实时监控服务-用户体验监控,每月100OCU免费额度
应用实时监控服务-应用监控,每月50GB免费额度
可观测监控 Prometheus 版,每月50GB免费额度
简介: HashMap核心特性数据结构:HashMap采用哈希表数据结构来存储键值对,利用哈希函数和哈希表快速定位元素位置,提供高效的键值对查询。参数设置初始容量:HashMap允许用户根据使用场景设定初始容量,以优化性能。在预知数据量时,可以通过计算(初始容量=预知数据量/加载因子)来设定合适的初始容量,以减少扩容操作,提高效率。加载因子:加载因子定义了哈希表何时进行扩容的阈值。加载因子较小时,哈希表会更早地进行扩容,减少哈希冲突;加载因子较大时,会提高内存利用率但可能增加哈希冲突。
  • 作者简介:阿里非典型程序员一枚 ,记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法(公众号同名

  • ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论,💬支持博主,记得点个大大的关注,持续更新🤞
    ————————————————-

    引言

    在Java的集合框架中,HashMap无疑是一个非常重要的成员。它以哈希表数据结构为基础,提供了高效的键值对存储和查询功能。无论是在大型数据处理系统中,还是在日常编程的各个方面,HashMap都扮演着至关重要的角色。其设计巧妙,性能卓越,为开发者提供了极大的便利。

然而,就像任何强大的工具一样,要充分利用HashMap的优势,就需要对其内部机制和工作原理有深入的了解。在本文中,我们将深入探讨HashMap的工作原理、参数设置、冲突解决策略以及性能优化等方面,帮助读者更好地理解HashMap,并在实际开发中发挥其最大效用。

接下来,我们将从HashMap的核心特性开始,逐步展开对其的总结和探讨。

HashMap的实现结构

作为最常用的Map类,HashMap是基于哈希表实现的,继承了AbstractMap并且实现了Map接口。HashMap根据键的Hash值来决定对应值的存储位置,使得获取数据的速度非常快。

哈希表将键的Hash值映射到内存地址,即根据键获取对应的值,并将其存储到内存地址。也就是说HashMap是根据键的Hash值来决定对应值的存储位置。通过这种索引方式,HashMap获取数据的速度会非常快。

例如,存储键值对(x,“aa”)时,哈希表会通过哈希函数f(x)得到"aa"的实现存储位置。

哈希冲突

  • 当两个对象的哈希值相同时,它们的存储地址会发生冲突。
  • 解决哈希冲突的方法有:开放定址法、再哈希函数法和链地址法。
  • HashMap采用链地址法解决哈希冲突问题,即采用数组(哈希表)+ 链表的数据结构。

HashMap的重要属性

  • HashMap由一个Node数组构成,每个Node包含了一个key-value键值对。
transient Node<K,V>[] table;
  • Node类作为HashMap中的一个内部类,除了key、value两个属性外,还定义了一个next指针。
static class Node<K,V> implements Map.Entry<K,V> {
   
   
    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;
    }
}
  • HashMap还有两个重要的属性:加载因子(loadFactor)和边界值(threshold)。
int threshold;
final float loadFactor;
  • LoadFactor属性是用来间接设置Entry数组(哈希表)的内存空间大小。
  • 阈值(threshold)的计算公式为:threshold = capacity * loadFactor。当HashMap中的元素数量超过了阈值时,就会触发扩容操作。

LoadFactor属性是用来间接设置Entry数组(哈希表)的内存空间大小,在初始HashMap不设置参数的情况下,默认LoadFactor值为0.75。为什么是0.75这个值呢?

这是因为对于使用链表法的哈希表来说,查找一个元素的平均时间是O(1+n),这里的n指的是遍历链表的长度,因此加载因子越大,对空间的利用就越充分,这就意味着链表的长度越长,查找效率也就越低。如果设置的加载因子太小,那么哈希表的数据将过于稀疏,对空间造成严重浪费。

那有没有什么办法来解决这个因链表过长而导致的查询时间复杂度高的问题呢?你可以先想想,我将在后面的内容中讲到。

Entry数组的Threshold是通过初始容量和LoadFactor计算所得,在初始HashMap不设置参数的情况下,默认边界值为12。如果我们在初始化时,设置的初始化容量较小,HashMap中Node的数量超过边界值,HashMap就会调用resize()方法重新分配table数组。这将会导致HashMap的数组复制,迁移到另一块内存中去,从而影响HashMap的效率。

HashMap添加元素优化

初始化完成后,HashMap就可以使用put()方法添加键值对了。从下面源码可以看出,当程序将一个key-value对添加到HashMap中,程序首先会根据该key的hashCode()返回值,再通过hash()方法计算出hash值,再通过putVal方法中的(n - 1) & hash决定该Node的存储位置。

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

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

// 省略部分代码...

// 通过putVal方法中的(n - 1) & hash决定该Node的存储位置
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

hash()算法详述

如果你不太清楚hash()以及(n-1)&hash的算法,就请你看下面的详述。

hash()方法中的算法

如果我们没有使用hash()方法计算hashCode,而是直接使用对象的hashCode值,会出现什么问题呢?

假设要添加两个对象a和b,如果数组长度是16,这时对象a和b通过公式(n - 1) & hash运算(即(16-1)&a.hashCode(16-1)&b.hashCode),因为15的二进制为0000000000000000000000000001111,如果对象A和B的hashCode的低4位恰好都为0(这在高并发下是很有可能的),那么与运算的结果就会相同,即发生哈希冲突。

为了避免上述情况,HashMap在hash()方法中对hashCode值进行了再处理。它将hashCode值右移16位(h >>> 16代表无符号右移16位),也就是取int类型的一半,并且使用位异或运算(^),这样的做法可以尽量打乱hashCode真正参与运算的低16位,从而减少哈希冲突的可能性。

(n - 1) & hash设计

这里的n代表哈希表的长度,哈希表习惯将长度设置为2的n次方,这样恰好可以保证(n - 1) & hash的计算得到的索引值总是位于table数组的索引之内。这是因为当n是2的幂时,n-1的二进制形式中所有位都是1(例如,当n=16时,n-1=15,其二进制为00001111),与任何hash值进行与运算,都能保证结果落在0到n-1的范围内。

例如:

  • hash=15n=16时,(n - 1) & hash的结果为15
  • hash=17n=16时,(n - 1) & hash的结果为1

流程图

在获得Node的存储位置后,如果判断Node不在哈希表中,就新增一个Node,并添加到哈希表中。以下是整个流程的简化图说明(由于Markdown不支持直接绘制流程图,这里用文字描述):

  1. 输入key和value:用户向HashMap提供key和value。
  2. 计算hash值:调用hash(key)方法,得到key的hash值。
  3. 确定存储位置:使用(n - 1) & hash计算Node的存储位置i
  4. 检查位置是否已存在Node:检查table数组中索引为i的位置是否已存在Node。
  5. 添加新Node:如果位置为空,则创建一个新Node,并将其放置在table数组的相应位置。
  6. 处理哈希冲突:如果位置已有Node(即发生哈希冲突),则使用链表或红黑树(在JDK 1.8及以后版本中)来处理冲突。
  7. 完成添加:key-value对成功添加到HashMap中。

在这里插入图片描述
从图中我们可以看出:在JDK1.8中,HashMap引入了红黑树数据结构来提升链表的查询效率。

这是因为链表的长度超过8后,红黑树的查询效率要比链表高,所以当链表超过8时,HashMap就会将链表转换为红黑树,这里值得注意的一点是,这时的新增由于存在左旋、右旋效率会降低。讲到这里,我前面我提到的“因链表过长而导致的查询时间复杂度高”的问题,也就迎刃而解了。

以下就是put的实现源码:

 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)
//1、判断当table为null或者tab的长度为0时,即table尚未初始化,此时通过resize()方法得到初始化的table
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
//1.1、此处通过(n - 1) & hash 计算出的值作为tab的下标i,并另p表示tab[i],也就是该链表第一个节点的位置。并判断p是否为null
            tab[i] = newNode(hash, key, value, null);
//1.1.1、当p为null时,表明tab[i]上没有任何元素,那么接下来就new第一个Node节点,调用newNode方法返回新节点赋值给tab[i]
        else {
   
   
//2.1下面进入p不为null的情况,有三种情况:p为链表节点;p为红黑树节点;p是链表节点但长度为临界长度TREEIFY_THRESHOLD,再插入任何元素就要变成红黑树了。
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
//2.1.1HashMap中判断key相同的条件是key的hash相同,并且符合equals方法。这里判断了p.key是否和插入的key相等,如果相等,则将p的引用赋给e

                e = p;
            else if (p instanceof TreeNode)
//2.1.2现在开始了第一种情况,p是红黑树节点,那么肯定插入后仍然是红黑树节点,所以我们直接强制转型p后调用TreeNode.putTreeVal方法,返回的引用赋给e
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
   
   
//2.1.3接下里就是p为链表节点的情形,也就是上述说的另外两类情况:插入后还是链表/插入后转红黑树。另外,上行转型代码也说明了TreeNode是Node的一个子类
                for (int binCount = 0; ; ++binCount) {
   
   
//我们需要一个计数器来计算当前链表的元素个数,并遍历链表,binCount就是这个计数器

                    if ((e = p.next) == null) {
   
   
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
// 插入成功后,要判断是否需要转换为红黑树,因为插入后链表长度加1,而binCount并不包含新节点,所以判断时要将临界阈值减1
                            treeifyBin(tab, hash);
//当新长度满足转换条件时,调用treeifyBin方法,将该链表转换为红黑树
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) {
   
    // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

结构化输出

HashMap获取元素优化

最佳情况

  • 当HashMap中只存在数组,而数组中没有Node链表时,是HashMap查询数据性能最好的时候。

哈希冲突与链表

  • 一旦发生大量的哈希冲突,就会产生Node链表。
  • 每次查询元素都可能遍历Node链表,从而降低查询数据的性能。

红黑树优化

  • 红黑树的使用解决了链表过长时性能降低的问题。
  • 使得查询的平均复杂度降低到了O(log(n))。
  • 链表越长,使用红黑树替换后的查询效率提升就越明显。

编码优化

  • 重写key值的hashCode()方法,降低哈希冲突,减少链表的产生。
  • 高效利用哈希表,提高性能。

HashMap扩容优化

JDK 1.7 扩容方式

  • 分别取出数组元素(一般是链表尾部的元素)。
  • 遍历以该元素为头的单向链表。
  • 依据每个被遍历元素的hash值计算其在新数组中的下标,然后进行交换。
  • 扩容后可能将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。

JDK 1.8 扩容优化

  • 扩容数组长度是原数组长度的2倍。
  • 使用“与运算”重新分配索引:原hash值和左移动的一位(newtable的值)按位与操作是0或1。
  • 0的话索引不变,1的话索引变成原索引加上扩容前数组长度。
  • 这种方式将哈希冲突的元素随机分布到不同的索引中。

总结

HashMap核心特性

  • 数据结构:HashMap采用哈希表数据结构来存储键值对,利用哈希函数和哈希表快速定位元素位置,提供高效的键值对查询。

参数设置

  • 初始容量:HashMap允许用户根据使用场景设定初始容量,以优化性能。在预知数据量时,可以通过计算(初始容量=预知数据量/加载因子)来设定合适的初始容量,以减少扩容操作,提高效率。
  • 加载因子:加载因子定义了哈希表何时进行扩容的阈值。加载因子较小时,哈希表会更早地进行扩容,减少哈希冲突;加载因子较大时,会提高内存利用率但可能增加哈希冲突。用户可以根据查询频率和内存使用需求调整加载因子。

冲突解决

  • 链地址法:HashMap使用链地址法解决哈希冲突。当两个或多个键的哈希值相同时,这些键值对会被存储在同一个桶(数组中的一个位置)的链表中。
  • 红黑树优化:在Java 8中,为了解决链表过长导致的查询性能下降问题,HashMap引入了红黑树。当链表长度超过一定阈值(默认为8)时,链表会转换为红黑树,将查询的时间复杂度从O(n)降低到O(log n)。

数据结构图

  • HashMap的数据结构图通常展示了一个数组(哈希表),数组的每个位置(桶)可能包含一个链表或一个红黑树。每个链表或红黑树中的节点代表一个键值对。

性能建议

  • 在预知数据量时,合理设置初始容量和加载因子,以减少扩容操作。
  • 如果查询操作频繁,考虑降低加载因子以减少哈希冲突。
  • 如果内存利用率是首要考虑因素,可以适当增加加载因子以提高内存利用率。
  • 注意HashMap不是线程安全的,在多线程环境下使用时需要额外的同步措施。

HashMap的数据结构图:
image.png

欢迎一键三连(关注+点赞+收藏),技术的路上一起加油!!!代码改变世界

  • 关于我:阿里非典型程序员一枚 ,记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法(公众号同名),回复暗号,更能获取学习秘籍和书籍等

  • ---⬇️欢迎关注下面的公众号:进朱者赤,认识不一样的技术人。⬇️---

相关文章
|
2月前
|
存储 安全 Java
Java 集合框架中的老炮与新秀:HashTable 和 HashMap 谁更胜一筹?
嗨,大家好,我是技术伙伴小米。今天通过讲故事的方式,详细介绍 Java 中 HashMap 和 HashTable 的区别。从版本、线程安全、null 值支持、性能及迭代器行为等方面对比,帮助你轻松应对面试中的经典问题。HashMap 更高效灵活,适合单线程或需手动处理线程安全的场景;HashTable 较古老,线程安全但性能不佳。现代项目推荐使用 ConcurrentHashMap。关注我的公众号“软件求生”,获取更多技术干货!
50 3
|
24天前
|
存储 移动开发 算法
【潜意识Java】Java基础教程:从零开始的学习之旅
本文介绍了 Java 编程语言的基础知识,涵盖从简介、程序结构到面向对象编程的核心概念。首先,Java 是一种高级、跨平台的面向对象语言,支持“一次编写,到处运行”。接着,文章详细讲解了 Java 程序的基本结构,包括包声明、导入语句、类声明和 main 方法。随后,深入探讨了基础语法,如数据类型、变量、控制结构、方法和数组。此外,还介绍了面向对象编程的关键概念,例如类与对象、继承和多态。最后,针对常见的编程错误提供了调试技巧,并总结了学习 Java 的重要性和方法。适合初学者逐步掌握 Java 编程。
48 1
|
2月前
|
缓存 算法 搜索推荐
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
48 6
|
2月前
|
存储 Java
Java 11 的String是如何优化存储的?
本文介绍了Java中字符串存储优化的原理和实现。通过判断字符串是否全为拉丁字符,使用`byte`代替`char`存储,以节省空间。具体实现涉及`compress`和`toBytes`方法,前者用于尝试压缩字符串,后者则按常规方式存储。代码示例展示了如何根据配置决定使用哪种存储方式。
|
2月前
|
存储 监控 算法
Java虚拟机(JVM)垃圾回收机制深度解析与优化策略####
本文旨在深入探讨Java虚拟机(JVM)的垃圾回收机制,揭示其工作原理、常见算法及参数调优方法。通过剖析垃圾回收的生命周期、内存区域划分以及GC日志分析,为开发者提供一套实用的JVM垃圾回收优化指南,助力提升Java应用的性能与稳定性。 ####
|
2天前
|
安全 Java 开发者
【JAVA】封装多线程原理
Java 中的多线程封装旨在简化使用、提高安全性和增强可维护性。通过抽象和隐藏底层细节,提供简洁接口。常见封装方式包括基于 Runnable 和 Callable 接口的任务封装,以及线程池的封装。Runnable 适用于无返回值任务,Callable 支持有返回值任务。线程池(如 ExecutorService)则用于管理和复用线程,减少性能开销。示例代码展示了如何实现这些封装,使多线程编程更加高效和安全。
|
1月前
|
监控 Java
java异步判断线程池所有任务是否执行完
通过上述步骤,您可以在Java中实现异步判断线程池所有任务是否执行完毕。这种方法使用了 `CompletionService`来监控任务的完成情况,并通过一个独立线程异步检查所有任务的执行状态。这种设计不仅简洁高效,还能确保在大量任务处理时程序的稳定性和可维护性。希望本文能为您的开发工作提供实用的指导和帮助。
100 17
|
2月前
|
Java
Java—多线程实现生产消费者
本文介绍了多线程实现生产消费者模式的三个版本。Version1包含四个类:`Producer`(生产者)、`Consumer`(消费者)、`Resource`(公共资源)和`TestMain`(测试类)。通过`synchronized`和`wait/notify`机制控制线程同步,但存在多个生产者或消费者时可能出现多次生产和消费的问题。 Version2将`if`改为`while`,解决了多次生产和消费的问题,但仍可能因`notify()`随机唤醒线程而导致死锁。因此,引入了`notifyAll()`来唤醒所有等待线程,但这会带来性能问题。
Java—多线程实现生产消费者
|
1月前
|
缓存 安全 算法
Java 多线程 面试题
Java 多线程 相关基础面试题
|
2月前
|
安全 Java Kotlin
Java多线程——synchronized、volatile 保障可见性
Java多线程中,`synchronized` 和 `volatile` 关键字用于保障可见性。`synchronized` 保证原子性、可见性和有序性,通过锁机制确保线程安全;`volatile` 仅保证可见性和有序性,不保证原子性。代码示例展示了如何使用 `synchronized` 和 `volatile` 解决主线程无法感知子线程修改共享变量的问题。总结:`volatile` 确保不同线程对共享变量操作的可见性,使一个线程修改后,其他线程能立即看到最新值。