前言

在工作中一次排查慢接口时，查到了一个函数耗时较长，最终定位到是通过 List 去重导致的。

因为测试环境还有线上晚期数据较少，这个接口的性能问题没有引起较大关注，前面频繁超时，才引起器重。.

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 是上面的 PRESENTprivate transient HashMap<E,Object> map;// HashMap 中的 valueprivate 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); }