侧边栏壁纸
  • 累计撰写 83 篇文章
  • 累计创建 87 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

集合Set

汤圆学Java
2021-04-13 / 0 评论 / 0 点赞 / 278 阅读 / 4,958 字
温馨提示:
本文最后更新于 2022-01-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

前言

大家好啊,我是汤圆,今天给大家带来的是《Java中的集合Set - 入门篇》,希望对大家有帮助,谢谢

简介

前面介绍了集合List映射Map,最后再简单介绍下集合Set,相关类如下图所示

集合

正文

Set从外面看像List(都是存储单一数据的集合),只不过存储的数据不会有重复
但是里面却是Map映射(因为它内存存储是基于Map结构实现),这也是为什么把Set放到Map后面来说的原因。

Set和Map有什么关系呢?

因为Map的键不会有重复,所以Set就利用了Map的这个特点,将其作为内部成员变量来使用
比如我们看下HashSet内部的源码,可以看到,基本上所有操作都是基于其内部的成员变量HashMap进行的

    
    private transient HashMap<E,Object> map;
    // 这个常量只是为了适配Map的键值对结构,无实际意义
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public int size() {
        return map.size();
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

   
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

   
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

Set的种类

Set的种类类似Map
Set主要有三种类型:HashSet(常用)、TreeSet(树形结构)、LinkedHashSet(前两者的结合)

我们先来看一下Set接口主要的几个方法:

  • boolean add(E e):往Set中添加元素
  • boolean contains(Object o):查询Set是否包含指定对象
  • boolean remove(Object o):从Set中删除指定对象
  • int size():返回Set的元素数量

下面我们简单看下三者的区别

HashSetTreeSetLinkedHashSet
访问速度适中
元素是否有序无序有序,默认升序有序,默认按插入的顺序
适用场景为快速查询而设计(用的最多)需要排序的场景需要保证查询和插入顺序一致的场景

接下来我们以HashSet为例,来介绍Set接口

HashSet

HashSet是一个无序集合
因为它内部是基于HashMap实现

上面的源码我们有看到,HashSet每插入一个元素,就将该元素作为内部hashMap的key,然后常量Object作为hashMap的value,存储到hashMap中

  • 如果元素的hash值没有重复,就按照数组的方式依次排列;
  • 如果hash值有重复的,就添加到已有的值对后面,形成链表结构;

整体结构 如下图所示

HashSet结构图

下面用代码示范一下

public class SetDemo {
    public static void main(String[] args) {
        // 初始化
        Set<Integer> set = new HashSet<>();
        // 添加元素
        set.add(10);
        // 元素数量
        int size = set.size();
        System.out.println(size);
        // 查询元素是否存在
        boolean isContain = set.contains(10);
        System.out.println(set);
        // 删除
        set.remove(10);
        System.out.println(set);
    }
}

TreeSet

TreeSet在插入的时候,可以按照元素进行排序(默认升序)

它适合用在排序比较多的场景,性能会比HashSet差一些

下面用代码示范一下**(重点要来了)**

public class SetDemo {
    public static void main(String[] args) {
      
        // TreeSet
        B b = new B();
        // 初始化
        Set<B> set2 = new TreeSet<>();
        // 添加元素
        set2.add(b);
        // 元素数量
        int size2 = set2.size();
        System.out.println(size2);
        // 查询元素是否存在
        boolean isContain2 = set2.contains(b);
        System.out.println(set2);
        // 删除
        set2.remove(b);
        System.out.println(set2);
    }
}
class B{

}

这段代码看似一切正常,实则暗藏玄机

如果你运行这段代码,会报出下面的错误提示:类B不能转换为Comparable。

TreeSet报错 Comparable

可是为什么要转换呢?我也没有转换啊

那是因为内部自动转换了

TreeSet啥时候会自动将元素类转为Comparable呢?

是在你插入第一个数据开始,内部就已经开始在做比较了(第一次先自己跟自己做比较,目的就是检查你这个数据有没有实现Comparable接口);

后面每插一个数据,都要从根节点开始挨个比较排序

这其实也算也是TreeSet内部排序的工作原理

所以上面这段代码需要让B实现Comparable接口,改后如下所示

public class SetDemo {
    public static void main(String[] args) {
        // TreeSet
        B b = new B();
        // 初始化
        Set<B> set2 = new TreeSet<>();
        // 添加元素
        // 此时运行没问题
        set2.add(b);
        // 元素数量
        int size2 = set2.size();
        System.out.println(size2);
        // 查询元素是否存在
        boolean isContain2 = set2.contains(b);
        System.out.println(set2);
        // 删除
        set2.remove(b);
        System.out.println(set2);
    }
}
// 这里实现了Comparable
class B implements Comparable{
    @Override
    public int compareTo(Object o) {
        return this.hashCode()>o.hashCode() ? 1 : -1;
    }
}

此时运行就没问题了

那为什么TreeMap没有这个问题呢?

其实TreeMap也有这个问题,只是TreeMap的键key一般都是字符串或者整型,而字符串和整型对象内部已经实现了Comparable接口,所以问题不大(因为用自定义对象做键key的毕竟还是少数)

LinkedHashSet

LinkedHashSet拥有HashSet的大部分优点,且保证了插入的顺序,使得在查询的时候,可以按照插入的顺序依次读取(原理是链表)

这里要注意一点:在Java程序语言设计中,所有的链表都是双向链表,即每个节点还存放着一个指向前节点的引用

大致的结构图如下所示(之前的LinkedHashMap忘记贴图了,跟这个类似,只是元素内容不同):

LinkedHashSet结构图

三者的排序比较

参考上一篇映射Map,Set排序比较表现出来的行为与Map一致

总结

Set一般用到的有HashSet,TreeSet,LinkedHashSet,内部都是无重复元素

  • HashSet的插入和访问都很快,但是内部是无序排列

  • TreeSet的插入和访问都很慢,但是内部是有序排列,默认按升序排列

  • LinkedHashSet拥有HashSet的大部分优点,而且还可以按照元素插入的顺序来访问元素,但是性能会比HashSet差

后记

最后,感谢大家的观看,谢谢

0

评论区