Java集合去重导致的线上问题
作者:程序员段飞? 发布时间:2022-01-24 04:52:29
前言:
在工作中一次排查慢接口时,查到了一个函数耗时较长,最终定位到是通过 List 去重导致的。
由于测试环境还有线上早期数据较少,这个接口的性能问题没有引起较大关注,后面频繁超时,才引起重视。
之前看《阿里巴巴Java开发手册》里面有这样一段描述:
如果需要这本书资源的网上下载也行,私聊我发你也行
今天我就结合源码聊聊Set是怎样保证数据的唯一性的,为什么两种去重方式性能差距这么大
HashSet源码
先看看类注释:
看类注释上,我们可以得到的信息有:
底层实现基于 HashMap,所以迭代时不能保证按照插入顺序,或者其它顺序进行迭代;
add、remove、contanins、size 等方法的耗时性能,是不会随着数据量的增加而增加的,这个主要跟 HashMap 底层的数组数据结构有关,不管数据量多大,不考虑 hash 冲突的情况下,时间复杂度都是 O (1);
线程不安全的,如果需要安全请自行加锁,或者使用
Collections.synchronizedSet;
迭代过程中,如果数据结构被改变,会快速失败的,会抛出 ConcurrentModificationException 异常。
刚才是从类注释中看到,HashSet 的实现是基于 HashMap 的,在 Java 中,要基于基础类进行创新实现,有两种办法:
继承基础类,覆写基础类的方法,比如说继承 HashMap , 覆写其 add 的方法;
组合基础类,通过调用基础类的方法,来复用基础类的能力。
HashSet 使用的就是组合 HashMap,其优点如下:
继承表示父子类是同一个事物,而 Set 和 Map 本来就是想表达两种事物,所以继承不妥,而且 Java 语法限制,子类只能继承一个父类,后续难以扩展。
组合更加灵活,可以任意的组合现有的基础类,并且可以在基础类方法的基础上进行扩展、编排等,而且方法命名可以任意命名,无需和基础类的方法名称保持一致。
组合就是把 HashMap 当作自己的一个局部变量,以下是 HashSet 的组合实现:
// 把 HashMap 组合进来,key 是 Hashset 的 key,value 是下面的 PRESENT
private transient HashMap<E,Object> map;
// HashMap 中的 value
private static final Object PRESENT = new Object();
从这两行代码中,我们可以看出两点:
我们在使用 HashSet 时,比如 add 方法,只有一个入参,但组合的 Map 的 add 方法却有 key,value 两个入参,相对应上 Map 的 key 就是我们 add 的入参,value 就是第二行代码中的 PRESENT,此处设计非常巧妙,用一个默认值 PRESENT 来代替 Map 的 Value;
我们再来看看add方法:
public boolean add(E e) {
// 直接使用 HashMap 的 put 方法,进行一些简单的逻辑判断
return map.put(e, PRESENT)==null;
}
我们进入更底层源码java.util.HashMap#put
:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
再瞧瞧hash方法:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以看到如果 key 为 null ,哈希值为 0,否则将 key 通过自身hashCode函数计算的的哈希值和其右移 16 位进行异或运算得到最终的哈希值。
我们再回到 java.util.HashMap#putVal
中:
在 java.util.HashMap#putVal
中,直接通过 (n - 1) & hash
来得到当前元素在节点数组中的位 置。如果不存在,直接构造新节点并存储到该节点数组的对应位置。如果存在,则通过下面逻 辑:
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
复制代码
来判断元素是否相等。
如果相等则用新值替换旧值,否则添加红黑树节点或者链表节点。
总结:通过HashMap的key的唯一性来保证的HashSet元素的唯一性。
最后再看看:
《阿里巴巴Java开发手册》里面还有这样一段描述:
到现在是不是明白了,这个2,3点的原因
性能对比
其实HashSet和ArrayList去重性能差异的核心在于contains函数性能对比。
我们分别查看java.util.HashSet#contains
和java.util.ArrayList#contains
的实现。
java.util.HashSet#contains
源码:
public boolean contains(Object o) {
return map.containsKey(o);
}
最终也是通过HashMap判断的
如果 hash 冲突不是极其严重(大多数都没怎么有哈希冲突),n 个元素依次判断并插入到 Set 的时间复杂度接近于 O (n),查找的复杂度是O(1)。
接下来我们看java.util.ArrayList#contains
的源码:
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}--pre>
发现其核心逻辑为:如果为 null, 则遍历整个集合判断是否有 null 元素;否则遍历整个列表,通 过 o.equals
(当前遍历到的元素) 判断与当前元素是否相等,相等则返回当前循环的索引。
所以, java.util.ArrayList#contains
判断并插入n个元素到 Set 的时间复杂度接近于O (n^2)
,查找的复杂度是O(n)。
因此,通过时间复杂度的比较,性能差距就不言而喻了。
我们分别将两个时间复杂度函数进行作图, 两者增速对比非常明显:
如果数据量不大时采用 List 去重勉强可以接受,但是数据量增大后,接口响应时间会超慢,这 是难以忍受的,甚至造成大量线程阻塞引发故障。
来源:https://juejin.cn/post/7081823029533081614
猜你喜欢
- 本文实例讲述了Android编程自定义AlertDialog样式的方法。分享给大家供大家参考,具体如下:开发的时候,通常我们要自定义Aler
- 把三状态转换图放在这,方便分析方法的作用:1.Session的save()方法Session是Hibernate所有接口中最重要的接口,提供
- 在项目中有事需要对值为NULL的对象中Field不做序列化输入配置方式如下:[配置类型]:源码包中的枚举类:public static en
- 1. java 执行shelljava 通过 Runtime.getRuntime().exec() 方法执行 shell 的命令或 脚本,
- 本文实例讲述了Java后台线程操作。分享给大家供大家参考,具体如下:一 点睛有一种线程,它是后面运行的,它的任务是为其他线程提供服务,这种线
- 1.使用matlab作闭合多边形图没有找到直接画多边形的函数,只能是将各个点的坐标保存在数组中,将一个点与其相邻的点相连,并将最后一个点与第
- 无平台限制,依赖于快递api网接口 ----------------实体类 [DataContract]  
- Activiti项目是一项新的基于Apache许可的开源BPM平台,本文就来简述一下Activiti常用类。具体如下:一、为什么要使用工作流
- 前言在最近的一个项目需要用JAVA来解析DICOM图片,DICOM被广泛应用于放射医疗,心血管成像以及放射诊疗诊断设备(X射线,CT,核磁共
- Gson是Google的一个开源项目,可以将Java对象转换成JSON,也可能将JSON转换成Java对象。Gson里最重要的对象有2个Gs
- 完整代码已上传到GitHub。Web端体验地址:http://47.116.72.33/(只剩一个月有效期)apk下载地址:https://
- 1、创建控制台程序如上图所示,选择linux开发平台,我用的VS2019,.Net5.0,一直点下一步,创建。2、创建TCP服务端程序usi
- 1.监听(Listener)<!-- 配置监听 --><listener><listener-class>
- 目录背景问题解决思路其他问题小结背景关于个人,前段时间由于业务太忙,所以一直没有来得及思考并且沉淀点东西;同时组内一个个都在业务上能有自己的
- 在使用C#进行相关编程的时候,有时候我们需要获取系统相关的进程信息。那么在C#中如何获取系统的所有进程那?下面请跟小编一起来操作。1、首先新
- 本文实例为大家分享了springboot实现基于aop的切面日志的具体代码,供大家参考,具体内容如下通过aop的切面方式实现日志通切面拦截所
- 包含不重复元素的集合称为“集(set)”。.NET Framework包含两个集HashSet<
- 在有些需求中会遇到,当鼠标滑过某个UI物体上方时,为了提醒用户该物体是可以交互时,我们需要添加一个动效和提示音。这样可以提高产品的体验感。解
- Required String parameter xxx is not present类型异常异常报错学习Spring Boot的时候做一
- 对象是使用new创建的,但是并没有与之相对应的delete操作来回收对象占用的内存。当我们完成对某个对象的使用时,只需停止对该对象的引用:将