java根据集合里某个字段去重,java数组去重不用集合
00-1010前言：HashSet源代码的性能比较
00-1010，上班查慢接口的时候发现一个函数用了很长时间，最后定位到是列表去重导致的。
由于测试环境中缺乏在线早期数据，该接口的性能并未引起太多关注，直到频繁超时后才受到关注。
之前看 《阿里巴巴Java开发手册》 里面有这样一段描述：
如果你需要在线下载这本书的资源，我可以在私聊发给你。
今天我就用源码来说说Set是如何保证数据的唯一性的，为什么两种去重方法会有这么大的性能差距。
目录
先看看类注释：
看类注释上，我们可以得到的信息有：
底层实现是基于HashMap的，所以不能保证迭代时按照插入顺序或者其他顺序迭代；add、remove、contanins、size等方法的耗时性能不会随着数据量的增加而增加。这主要和HashMap底层的数组数据结构有关。无论数据量有多大，不考虑哈希冲突，时间复杂度都是O (1)。如果线程不安全，请自行锁定，或者使用Collections.synchronizedSet;在迭代过程中，如果数据结构发生变化，会很快失败，并抛出ConcurrentModificationException异常。刚刚从班级评论上看到，HashSet的实现是基于HashMap的。在Java中，有两种方法可以在基本类的基础上进行创新实现：
继承基类，重写基类的方法，比如继承HashMap的方法，重写它的add通过调用基类的方法来组合基类，重用了基类的能力。HashSet 使用的就是组合 HashMap，其优点如下：
意思是亲子类是同一个东西，而集合和地图本来是想表达两个东西，所以不适合继承。而且Java语法限制子类只能继承一个父类，这使得以后很难扩展。
组合更加灵活，现有的基本类可以任意组合，基本类的方法可以扩展和排列等。而且方法名可以任意命名，不需要和基类的方法名一致。
组合就是把HashMap当做自己的一个局部变量。下面是HashSet的组合实现：
//Combine HashMap，key是Hashset的键，value是下面的Present Private Transient Hashmap，Object Map//value private static final object present=hashmap中的new object()；从这两行代码中，我们可以看出两点：
我们使用HashSet的时候，比如add方法，只有一个参数，但是组合图的add方法有两个参数：key和value。对应Map的键是我们add的参数，值是第二行代码中的PRESENT。这里的设计非常巧妙，使用了一个缺省值来替换Map的值。
我们再来看看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)；}再看看哈希方法：
静态final int hash(对象键){ int h；return (key==null)？0 :(h=key . hashcode())^(h 16)；}可以看出，如果key为null，hash值为0，否则，key通过自己的hashCode函数计算出的hash值与其右移16位进行异或运算，得到最终的hash值。
让我们回到java.util.HashMap#putVal:
n:center">
在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 去重勉强可以接受，但是数据量增大后，接口响应时间会超慢，这 是难以忍受的，甚至造成大量线程阻塞引发故障。
到此这篇关于Java集合去重导致的线上问题的文章就介绍到这了,更多相关Java集合去重内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。