问题背景

对于一个集合进行去重操作,很多人可能会第一时间想到遍历要去重的集合,然后调用List接口的contains方法,如果不存在就加入新的集合,最后进行返回。

// 遍历后判断赋给另一个list集合,保持原来顺序
public static <T> List<T> distinct(List<T> list) {
      List<T> ret = new ArrayList<>();
      for (T str : list) {
           if (!ret.contains(str)) {
               ret.add(str);
           }
       }
      return ret;
}

这是一个很简单的思路,但是实际上效率并不高,时间复杂度是O(n^2),空间复杂度是O(n)。时间复杂度和空间复杂度都比较大,具体分析过程见后面的复杂度分析。

解决方法

那么有没有什么更加高效的方法呢?

在Java的集合框架中,一共有三大类,分别是List(可重复,有序),Set(不可重复,无序),Map(K-V对)。我们可以利用Set集合的特点来进行去重,代码如下。

//利用set集合特性进行去重
public static <T> Set<T> distinct(List<T> list) {
    if (CollectionUtils.isEmpty(data)) {
        return new HashSet<>();
    }
    return new HashSet<>(list);
}

提出疑问

接下来,来思考两个问题:

  • Set集合是怎样保证元素的唯一性?
  • Set集合通过什么判断两个元素是一样的?

通过查看HashSet的add方法的源码,我们可以发现HashSet实际上是依赖HashMap来实现的,Set集合的元素存放于HashMap的key的位置,至于value的位置则使用一个常量来进行占位(无意义)。

image-20200816153108157

image-20200816153129921

也就是说Set集合的去重是依赖HashMap的key去重而进行去重的,接下来来看一下HashMap是如何去重的,HashMap的put方法如下。

image-20200816154516229

通过这里我们看到,除了传入 keyvalue 外,第一个哈希值的参数 (hash) 是通过 HashMap 的 hash 函数实现的。

image-20200816155121855

可以看到如果 keynull ,哈希值为 0,否则将 key 通过自身 hashCode 方法计算的的哈希值和其右移 16 位进行异或运算得到最终的哈希值。这里的hashCode方法对于不同的类有不同的算法实现,但是如果两个对象是一样的,他们的hashCode必定是一样的。

回到putVal方法,我们可以发现首先通过(n-1) & hash这个公式作为数组的下标。然后判断下标对应位置是否为存在(是否为空)。

  • 如果存在,那么就实例化一个新的节点Node存放
  • 如果不存在,判断新旧元素的hash和key是否相等

    • 如果相等,利用e作为中间变量,在后续进行覆盖并返回旧元素(重点)
    • 如果不相等,否则添加红黑树节点或者链表节点

image-20200816161634236

覆盖并返回旧元素的代码如下。因此,对于HashMap来说,如果想put进来多个相同的元素,最后put的会把前面put的给覆盖掉。

image-20200816161927358

得出结论

那么上述问题就有答案了!

Q1:Set集合是怎样保证元素的唯一性?

A1:通过新元素覆盖旧元素的机制来保证元素的唯一性。

Q2:Set集合通过什么判断两个元素是一样的?

A2:通过对比新旧元素的hash值和equals方法进行判断,因此在使用自定义类对象进行存放的时候,需要重写equals方法和hashCode方法。

举个例子吧!

就拿我最近在学的权限管理系统来说,由于采用的是RBAC模型进行权限控制,每个用户拥有角色集合,每个角色拥有权限集合。这里的集合就需要进行去重操作,因此采用Set集合来维护。举个例子,因为你一个角色不可能拥有两个相同的权限。因此我们需要进行角色和权限实体类equals方法和hashCode方法的重写。

以权限Permission实体类为例,代码如下。

image-20200816163112886

复杂度分析

HashSet分析

通过HashSet进行去重是通过HashSet的构造函数完成的,我们来看一下他的代码。

image-20200816180104009

构造函数调用了addAll方法进行去重,再来看一下addAll的代码。

image-20200816180136632

调用了add方法,代码如下。

image-20200816181118557

很明显地,根据上面HashMap源码的分析,去重是根据hash算法直接定位,不需要进行遍历,因此add方法时间复杂度是O(1)。

综上所述,HashSet去重的时间复杂度是O(n),空间复杂度是O(1)

ArrayList分析

正如开篇所述,思路是遍历后判断赋给另一个list集合。

// 遍历后判断赋给另一个list集合,保持原来顺序
public static <T> List<T> distinct(List<T> list) {
      List<T> ret = new ArrayList<>();
      for (T str : list) {
           if (!ret.contains(str)) {
               ret.add(str);
           }
       }
      return ret;
}

调用了contains方法,代码如下。

image-20200816180501243

调用了indexOf方法,代码如下。

image-20200816180610584

很明显地,由于indexOf方法两个分支都有for循环,因此这个方法的时间复杂度是O(n)。

综上所述,结合最外层去重方法的for循环,相当于一共有两个for循环,因此使用ArrayList去重的时间复杂度是O(n^2),此外还开辟了一个空间来存放去重后的结果,空间复杂度是O(n)

总结

去重方式时间复杂度空间复杂度
HashSetO(n)O(1)
ArrayListO(n^2)O(n)

由下图可知,当数据量到一定程度的时候,HashSet去重时间效率远比ArrayList高。

时间复杂度对比

©著作权归作者所有

已有 2 条评论

发表评论

正在加载 Emoji