专栏首页Java后端技术栈cwnait精解四大集合框架:Set核心知识总结

精解四大集合框架:Set核心知识总结

关注“Java后端技术全栈”

回复“面试”获取全套面试资料

Set继承于Collection接口,是一个不允许出现重复元素,并且无序的集合,主要有HashSet和TreeSet两大实现类,另外LinkedHashSet也有一定的使用频率。

在判断重复元素的时候,Set集合会调用hashCode()和equal()方法来实现。

类图UML

Set常用方法

与List一样都是接口,Set接口也提供了集合操作的基本方法。Java四大集合之一,但与List不同的是,Set还提供了equals(Object o)和hashCode(),供其子类重写,以实现对集合中插入重复元素的处理;

public interface Set<E> extends Collection<E> {
    //添加
    boolean add(E e);
    boolean addAll(Collection<? extends E> c);

    //删除
    boolean remove(Object o);
    boolean removeAll(Collection<?> c);
    void clear();

    //长度
    int size();
    //是否为空
    boolean isEmpty();

    //是否包含
    boolean contains(Object o);
    boolean containsAll(Collection<?> c);
    boolean retainAll(Collection<?> c); 

    //获取Set集合的迭代器:
    Iterator<E> iterator();

    //把集合转换成数组
    Object[] toArray();
    <T> T[] toArray(T[] a);

    //判断元素是否重复,为子类提高重写方法
    boolean equals(Object o);
    int hashCode();
}

接口里知识定义了方法,具体的实现请看下面两个常用实现类。

HashSet

HashSet 是用来存储没有重复元素的集合类并且是无序的。实现了 Set 接口。底层其实主要是使用 HashMap 机制实现,所以也是线程不安全

部分源码:

public class HashSet<E>  extends AbstractSet<E>  implements Set<E>, Cloneable, java.io.Serializable{
    private transient HashMap<E,Object> map;
    //这里这个PRESENT就是作为HashMap中的key
    private static final Object PRESENT = new Object();
    public HashSet() {
        map = new HashMap<>();
    }

特征:

  1. 不可重复
  2. 无序
  3. 线程不安全,若多个线程同时操作HashSet,必须通过代码实现同步;
  4. 集合元素可以是 null,但只能放入一个 null

使用场景:去重、不要求顺序

原理:HashSet底层由HashMap实现,插入的元素被当做是HashMap的key,根据hashCode值来确定集合中的位置,由于Set集合中并没有角标的概念,所以并没有像List一样提供get()方法。当获取HashSet中某个元素时,只能通过遍历集合的方式进行equals()比较来实现;

常用方法

    //添加
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    //移除
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
    //清空
    public void clear() {
        map.clear();
    }
    //获取迭代器
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }
    //判断是否为空
    public boolean isEmpty() {
        return map.isEmpty();
    }
    //求集合大小
    public int size() {
        return map.size();
    }

正如上面所说,底层使用 HashMap 的 key 不能重复机制来实现没有重复的 HashSet。

TreeSet

TreeSet 实现了 SortedSet 接口,意味着可以排序,它是一个有序并且没有重复的集合类,底层是通过 TreeMap 实现。TreeSet 并不是根据插入的顺序来排序,而是字典自然排序。线程不安全。从名字上可以看出,此集合的实现和树结构有关。与HashSet集合类似,TreeSet也是基于Map来实现,具体实现TreeMap(后面讲解),其底层结构为红黑树(特殊的二叉查找树)。

TreeSet 支持两种排序方式:自然升序排序自定义排序

部分源码

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable{

    private transient NavigableMap<E,Object> m;

    private static final Object PRESENT = new Object();

    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

常用方法

 //求集合大小
 public int size() {
     return m.size();
 }
 //判断是否为空
 public boolean isEmpty() {
     return m.isEmpty();
 }
 //判断是否包含
 public boolean contains(Object o) {
     return m.containsKey(o);
12 }

特征:

  1. 不可重复
  2. 有序,默认自然升序排序
  3. 线程不安全,若多个线程同时操作HashSet,必须通过代码实现同步;
  4. 集合元素不可以为 null
  5. 对插入的元素进行排序,是一个有序的集合(主要与HashSet的区别);
  6. 底层使用红黑树结构,而不是哈希表结构;

原理:

TreeSet 底层是基于 treeMap(红黑树结构)实现的,可以自定义比较器对元素进行排序,或是使用元素的自然顺序。

使用场景:去重、要求排序

LinkedHashSet

LinkedHashSet 是使用 HashSet 机制实现,它是一个可以保证插入顺序或是访问顺序,并且没有重复的集合类。线程不安全

数据结构:数组 + 双向链表,Entry 结构:before|hash|key|value|next|after,before 和 after 用于维护整个双向链表。

部分源码

public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable {

    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }

    public LinkedHashSet() {
        super(16, .75f, true);
    }

常用方法

从这里可以看出,这家伙基本上都是使用HashSet来实现的,所以常用方法和HashSet相同。

特征:

  1. 集合元素不可以为 null;
  2. 线程不安全。

原理:

LinkedHashSet 底层使用了 LinkedHashMap 机制(比如 before 和 after),加上又继承了 HashSet,所以可以实现既可以保证迭代顺序,又可以达到不出现重复元素。

使用场景:去重、需要保证插入或者访问顺序

HashSet、TreeSet、LinkedHashSet 的区别

  • HashSet 只去重
  • TreeSet 去重并排序
  • LinkedHashSet 去重并保证迭代顺序。

本文分享自微信公众号 - Java后端技术全栈(jjs-2018),作者:田老师

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 快速掌握模板方法模式

    模板模式就是定义一个操作中的算法骨架,然后将一些步骤延迟到子类中。模板方法使得子类在不改变算法的结构即可重定义该算法的某些步骤。

    田维常
  • SpringBoot如何使用注解装配Bean

    在日常开发中,项目中大量的Bean的装配。今天就来聊聊如何使用注解装配Bean。这里与其说是SpringBoot装配Bean还是不如说是Spring注解来装配B...

    田维常
  • 再聊Java 之synchronized

    Java synchronized块将方法或代码块标记为已同步。Java synchronized块可用于避免竞争条件。

    田维常
  • Java 多线程编程(上)

    https://blog.csdn.net/weixin_44510615/article/details/102617286

    润森
  • 阶段01Java基础day14常用对象03

    声明:本文为原创,作者为 对弈,转载时请保留本声明及附带文章链接:http://www.duiyi.xyz/c%e5%ae%9e%e7%8e%b0%e9%9b%...

    对弈
  • Java基础笔记14

    dreamkong
  • ABP入门系列(2)——领域层创建实体

    这一节我们主要和领域层打交道。首先我们要对ABP的体系结构以及从模板创建的解决方案进行一一对应。网上有代码生成器去简化我们这一步的任务,但是不建议初学者去使用。...

    圣杰
  • 几种常见设计模式在项目中的应用<Singleton、Factory、Strategy>

      前几天阅读一框架文档,里面有一段这样的描述 “从对象工厂中………” ,促使写下本文。尽管一些模式简单和简单,但是常用、有用。

    梁规晓
  • Java开发GUI之GridLayout网格布局

        GridLayout是简单的网格布局,使用其可以方便的实现多行多列的布局样式。

    珲少
  • MyBatis 核心配置概述之 Executor

    上一篇我们对 SqlSession 和 SqlSessionFactory 的创建过程有了一个详细的了解,可以去是看 MyBatis 基础搭建及架构概述但上述的...

    cxuan

扫码关注云+社区

领取腾讯云代金券