你给HashMap初始化了容量,却让性能变加更糟?

简介: 你给HashMap初始化了容量,却让性能变加更糟?

前言

项目中,看到大家已经意识到初始化HashMap时给Map指定初始容量大小,甚是欣慰。但仔细一看,发现事情好像又有一些不对头。虽然指定了大小,却让性能变得更加糟糕了。

可能你也是如此,看了《阿里巴巴Java开发手册》感觉学到了很多,于是在实践中开始尝试给Map指定初始大小,并感觉自己写的代码高大上了一些。

的确,当你意识到指定初始化值时,已经比普通人更进了一步,但是如果这个值指定的不好,程序的性能反而不如默认值。

这篇文章就来从头到尾分析一下,读者多注意分析的方法和底层的原理实现。

阿里开发规范

我们先来看看阿里巴巴Java开发规范中是如何描述Map初始值大小这一规范的吧。

阿里巴巴《Java开发手册》第1章编程规范,第6节集合处理的第17条规定如下:

【推荐】集合初始化时,指定集合初始值大小。说明:HashMap 使用HashMap(int initialCapacity)初始化,如果暂时无法确定集合大小,那么指定默认值(16)即可。

正例:initialCapacity = (需要存储的元素个数 / 负载因子) + 1。注意负载因子(即loader factor)默认为0.75,如果暂时无法确定初始值大小,请设置为16(即默认值)。

反例:HashMap需要放置1024个元素,由于没有设置容量初始大小,随着元素不断增加,容量7次被迫扩大,resize需要重建hash表。当放置的集合元素个数达千万级别时,不断扩容会严重影响性能。

通过上面的规约我们大概了解到几个信息:

  • 第一,HashMap的默认容量是16;
  • 第二,容量扩容与负载因子和存储元素个数有关;
  • 第三,设置初始值是为了减少扩容导致重建hash的性能影响。

可能你看完上述规约之后,就开始在代码中进行使用指定集合初始值的方式了,这很好。但稍有不慎,这中间却会出现很多的问题,下面我们就来看看实例。

你指定的初始值对吗?

直接上一段示例代码,并思考这段代码是否有问题:

Map<String, String> map = new HashMap<>(4);
map.put("username","Tom");
map.put("address","Bei Jing");
map.put("age","28");
map.put("phone","15800000000");
System.out.println(map);

类似的代码是不是很熟悉,写起来也很牛的样子。HashMap使用了4个值,就初始化4个大小。空间完全利用,而且又满足了阿里开发手册的规约?!

上述写法真的对吗?真的没问题吗?直接看代码可能看不出来问题,我们添加一些打印信息。

如何验证扩容

很多朋友可能也想验证HashMap到底在什么时候进行扩容的,但苦于没有思路或方法。这里提供一个简单的方式,就是基于反射获取并打印一下capacity的值。

还是上面的示例我们改造一下,向HashMap中添加数据时,打印对应的capacity和size这两个属性的值。

public class MapTest {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>(4);
        map.put("username", "Tom");
        print(map);
        map.put("address", "Bei Jing");
        print(map);
        map.put("age", "28");
        print(map);
        map.put("phone", "15800000000");
        print(map);
    }
    public static void print(Map<String, String> map) {
        try {
            Class<?> mapType = map.getClass();
            Method capacity = mapType.getDeclaredMethod("capacity");
            capacity.setAccessible(true);
            System.out.println("capacity : " + capacity.invoke(map) + "    size : " + map.size());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

其中print方法通过反射机制,获取到Map中的capacity和size属性值,然后进行打印。在main方法中,每新增一个数据,就打印一下Map的容量。

打印结果如下:

capacity : 4    size : 1
capacity : 4    size : 2
capacity : 4    size : 3
capacity : 8    size : 4

发现什么?当第4个数据put进去之后,HashMap的容量发生了一次扩容。

想想最开始我们指定初始容量的目的是什么?不就是为了避免扩容带来的性能损失吗?现在反而导致了扩容。

现在,如果去掉指定的初始值,采用new HashMap<>()的方式,执行一下程序,打印结果如下:

capacity : 16    size : 1
capacity : 16    size : 2
capacity : 16    size : 3
capacity : 16    size : 4

发现默认值并没有扩容,理论上性能反而更高了。是不是很有意思?你是不是也走进了这个使用误区了?

原理分析

之所会出现上述问题,最主要的是我们忽视了总结规约中的第二条,就是扩容机制。

HashMap的扩容机制,就是当达到扩容条件时会进行扩容。扩容条件就是当HashMap中的元素个数(size)超过临界值(threshold)时就会自动扩容。在HashMap中,threshold = loadFactor * capacity。其中,默认的负载因子为0.75。

套入公式我们来算一下,负载因子为0.75,示例中capacity的值为4,得出临界值为4 * 0.75 = 3。也就说,当实际的size超过3之后,就会触发扩容,而扩容是直接将HashMap的容量加倍。这跟我们打印的结果一致。

JDK7和JDK8的实现是一样的,关于实现源码的分析,我们不放在本篇文章中进行分析。大家知道基本的原理及试验效果即可。

HashMap初始化容量设置多少合适

经过上面的分析,我们已经看到隐含的问题了。这时不禁要问,HashMap初始化容量设置多少合适呢?是不是随意写一个比较大的数字就可以了呢?

这就需要我们了解当传入初始化容量时,HashMap是如何处理的了。

当我们使用HashMap(int initialCapacity)来初始化容量时,HashMap并不会使用传入的initialCapacity直接作为初始容量。

JDK会默认帮计算一个相对合理的值当做初始容量。所谓合理值,其实是找到第一个大于等于用户传入的值的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;
}

也就是说,当创建HashMap时,传入了7,则初始化的容量为8;当传入了18,则初始化容量为32。

此时,我们得出第一条结论:设置初始容量时,采用2的n次方的数值,即使不这么设置,JDK也会帮忙取下一个最近的2的n次方的数值。

上面的值看似合理了,但对于最初的实例,我们已经发现并不是存多少数据就设置多少的初始容量。因为还要考虑到扩容。

根据扩容公式可得出,如果设置初始容量为8,则8乘以0.75,也就6个值。在存储小于等于6个值的时候,不会触发扩容。

那么是否可以通过一个公式来反推呢?对应值的计算方法如下:

return (int) ((float) expectedSize / 0.75F + 1.0F);

比如,计划向HashMap中放入7个元素,通过expectedSize/0.75F + 1.0F计算,7/0.75 + 1 = 10,10经过JDK处理之后,会被设置成16。

那么此时,16就是比较合理的值,而且能大大减少了扩容的几率。

所以,可以认为,当明确知道HashMap中元素个数时,把默认容量设置成expectedSize / 0.75F + 1.0F是一个在性能上相对好的选择,但是,同时也会牺牲些内存。

其他相关知识

了解上述知识,最后再补充一些HashMap相关的知识点:

  • HashMap在new后并不会立即分配bucket数组;
  • HashMap的bucket数组大小是2的幂;
  • HashMap在put的元素数量大于Capacity * LoadFactor(默认16 * 0.75)时会进行扩容;
  • JDK8在哈希碰撞的链表长度达到TREEIFY_THRESHOLD(默认8)后,会把该链表转变成树结构,提高性能;
  • JDK8在resize时,通过巧妙的设计,减少了rehash的性能消耗。

小结

本篇文章介绍了使用HashMap中的一些误区,得出最大的结论可能就是不要因为对一个知识点一知半解而导致错误使用。同时,也介绍了一些分析方法和实现原理。

可能有朋友会问,要不要设置HashMap的初识值,这个值又设置成多少,真的有那么大影响吗?不一定有很大影响,但性能的优化和个人技能的累积,不正是由这一点点的改进和提升而获得的吗?

目录
相关文章
|
算法 Java 开发者
为啥HashMap的默认容量是16?
为啥HashMap的默认容量是16?
219 0
|
存储 安全 算法
【JAVA】HashMap扩容性能影响及优化策略
【JAVA】HashMap扩容性能影响及优化策略
|
12月前
|
机器学习/深度学习 C# 索引
HashMap的容量为什么一定是2^n?
`HashMap` 的容量设计为 `2^n` 主要出于三个考虑:1) 位运算效率高,通过 `(hash & (capacity - 1))` 快速计算索引;2) 元素分布均匀,减少哈希冲突,提高性能;3) 扩容时只需检查最高位,简化重分布过程,提升扩容效率。初始容量为 `1 &lt;&lt; 4`(16),扩容以2倍递增。
289 0
HashMap的容量为什么一定是2^n?
|
存储 安全 Java
Java面试题:请解释Java内存模型,并说明如何在多线程环境下使用synchronized关键字实现同步,阐述ConcurrentHashMap与HashMap的区别,以及它如何在并发环境中提高性能
Java面试题:请解释Java内存模型,并说明如何在多线程环境下使用synchronized关键字实现同步,阐述ConcurrentHashMap与HashMap的区别,以及它如何在并发环境中提高性能
129 0
|
Java
Java为什么建议初始化HashMap的容量大小?
【5月更文挑战第3天】Java中初始化HashMap容量能提升性能。默认容量16,扩容按当前的1/2进行。预估元素数量设定合适容量可避免频繁扩容,减少性能损耗。过大浪费内存,过小频繁扩容,需权衡。Java 8后扩容策略调整,但核心仍是预估初始容量以优化性能。
205 1
|
存储 安全 算法
如何优化Java中的HashMap性能?
如何优化Java中的HashMap性能?
|
存储 缓存 安全
Java HashMap:哈希表原理、性能与优化
Java HashMap:哈希表原理、性能与优化
682 1
|
Web App开发 存储 数据可视化
VisualVM【实践 01】工具VisualVM下载使用及插件Visual GC示例说明HashMap初始化容量initialCapacity的影响(源码及visualvm_215.zip分享)
VisualVM【实践 01】工具VisualVM下载使用及插件Visual GC示例说明HashMap初始化容量initialCapacity的影响(源码及visualvm_215.zip分享)
290 0
|
4月前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
200 3
|
12月前
|
Java
让星星⭐月亮告诉你,HashMap中保证红黑树根节点一定是对应链表头节点moveRootToFront()方法源码解读
当红黑树的根节点不是其对应链表的头节点时,通过调整指针的方式将其移动至链表头部。具体步骤包括:从链表中移除根节点,更新根节点及其前后节点的指针,确保根节点成为新的头节点,并保持链表结构的完整性。此过程在Java的`HashMap$TreeNode.moveRootToFront()`方法中实现,确保了高效的数据访问与管理。
88 2