前言工作中查看界面慢的时候，发现了一个耗时很久的函数，最后通过List去重定位。由于缺乏早期测试环境和线上的数据，这个接口的性能问题一直没有引起太多关注，后来频繁超时才引起关注。之前《阿里巴巴Java开发手册》里有这么一段描述：你看，阿里前辈免费总结出来了，不过你还是会看到有人会用List的contains函数去重...不记得了，你抄袭会被罚10如果需要本书资源在线下载，也可以私聊发给你。今天就来聊聊Set是如何基于源码来保证数据的唯一性，以及为什么这两种去重方式性能差距如此之大。HashSet源码先看类注解：查看类注解，可以得到如下信息：底层实现是基于HashMap的，所以不能保证迭代时是按插入顺序还是其他顺序迭代；add、remove、contanins、size等方法的耗时性能不会随着数据量的增加而增加。这主要和HashMap底层的数组数据结构有关。不管数据量有多大，不管哈希冲突，时间复杂度都是O(1)；线程不安全，如果需要安全，请自行加锁，或者使用Collections.synchronizedSet；在迭代过程中，如果改变了数据结构，会很快失败，抛出ConcurrentModificationException。刚才从类注解上看到HashSet的实现是基于HashMap的。在Java中，基于基类实现创新有两种方式：继承基类，重写基类的方法，例如继承HashMap，重写其add方法；结合基类，通过调用基类的方法，复用基类的能力。HashSet使用了HashMap的组合，它的优点有：继承就是父类和子类是同一个东西，而Set和Map本来就是想表达两个东西，所以继承不合适，Java语法受限，子类只能继承一个父类，以后很难扩展。组合更灵活。现有的基础类可以任意组合，可以基于基础类的方法进行扩展、编排等，方法名可以任意命名，不需要和基础类的方法名保持一致.组合就是将HashMap作为自己的一个局部变量。下面是HashSet的组合实现：//组合HashMap，key是Hashset的key，value是下面的PRESENTprivatetransientHashMapmap;//valueprivatestaticfinalObjectPRESENTinHashMap=newObject();从这两行代码我们可以看出两点：当我们使用HashSet时，比如add方法只有一个入参，但是组合Map的add方法有两个入参，key和value对应，Map的key就是我们add的入参，value就是第二行代码中的PRESENT。这里的设计很巧妙，用一个默认值PRESENT代替了Map的Value；再来看看add方法：publicbooleanadd(Ee){//直接使用HashMap的put方法做一些简单的逻辑判断returnmap.put(e,PRESENT)==null;}我们进入下层源码codejava.util.HashMap#put:publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}再看hash方法：staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h>>>16);}可以看到，如果key为null，则hash值为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)))判断元素是否相等。如果相等，则用新值替换旧值，否则添加红黑树节点或链表节点。总结：HashSet元素的唯一性是由HashMap的key的唯一性来保证的。最后我们来看一下：《阿里巴巴Java开发手册》里面还有一段描述：现在你明白了吗，第2点和第3点的原因的性能对比其实是HashSet和ArrayList去重性能差异的核心在于contains函数的性能比较。我们分别看java.util.HashSet#contains和java.util.ArrayList#contains的实现。java.util.HashSet#contains源码：publicbooleancontains(Objecto){returnmap.containsKey(o);}最后通过HashMap进行判断。如果hash冲突不是特别严重（大部分根本没有hash冲突），n个元素依次判断插入Set的时间复杂度接近O(n)，查找复杂度为O(1).接下来看java.util.ArrayList#contains的源码：publicbooleancontains(Objecto){returnindexOf(o)>=0;}publicintindexOf(Objecto){if(o==null){for(inti=0;i
